노는 게 제일 좋아

나는 재귀가 아직도 헷갈린다. 이 문제를 분석하며 한 번 더 배워가자 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 이 문제는 또 재귀다. 결과를 보고 과정을 생각해내는 것이다. 해보자. 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의..

하노이 탑의 근본을 알려주는 문제다 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이 탑하면 재귀문제가 떠오른다. 하지만 감은 전혀 안 온다. 아니 감이 안 온다기보다는 코딩을 못하는 것이다. 머리로는 이해가 가는데.. 코딩을 어떻게 해야하지?? 나도 그렇다. 아직 재귀가 익숙치 못하다. 하나씩 알아보자 여기 링크 들어가서 알아보자 https://www.mathsisfun.com/games/towerofhanoi.html Pl..

재귀나 숫자 범위에 대해 기본적인 문제 좋은 것 같다. https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 음.. 처음 봤을 때 당황 많이했다. int, 4바이트 long long 8바이트 재귀함수까지... 재귀함수는 항상 그게 중요하다. 점화식을 찾는 것... 1번, n번 n+1번까지의 식만 찾으면 굿 맞는 풀이( 틀린 풀이도 집어넣어놨다.) #include using namespace std; using ll = long long; ll remain(ll a, ll b, ll c){ //n = 1일 때 if(..

구현하라는 대로 그냥 구현만 해주는 문제다. 메모리가 아주 적다. https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 범위가 0부터면 쉽겠는데..? 역시 문제를 어렵게 하려면 입력을 드럽게 주면 된다. 하지만 우리가 중요한 것은 연도다. 연도는 해가 한 바퀴 도는 것이 중요하지 연도가 중요하진 않다. 다같이 -1을 해주자 # 맞는 풀이 #include using namespace std; int main(){ int E,S,M; int e,s,m;..

BFS의 응용문제로 BFS라고 생각지 않지만 의외로 BFS라서 놀라는 초보인 나에게는 놀라움의 대상이었던 문제다. https://www.acmicpc.net/problem/1697 이 문제도 내가 풀긴 풀었지만 왠지 더 잘 풀수 있을 것 같다. #1 뭔가 틀린 풀이 #include #include #include using namespace std; int dist[100001]; // 0 m >> n; queue Q; fill(dist, dist+100000, -1); // 0~ 100000까지 -1 dist[m] = 0; Q.push(m); while(!Q.empty()){ int cur = Q.front(); Q.pop(); if(cur-1 >= 0 && dist[cur-1] < 0){ dist[c..

BFS의 응용문제다. 어렵진 않지만 응용하는 첫번째 단계라고 할 수 있다. www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제도 BFS를 이용한다는 감이 온다. 고려해야 할 조건이 몇가지 있다. 1. 지훈이의 탈출 조건 2. 불이 있는 곳에 지훈이 있을 수 없다. 우선 지훈이는 문제에서 가장자리에 있으면 탈출 할 수 있다. 즉, [ i ][ j ] 위치에서 i 또는 j 가 0을 가지거나 최댓값을 가지면 탈출한 것이다. -> 다시 말해서 가..

이것도 BFS의 기본이라고 볼 수 있다. www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전 문제의 최단경로의 경로문제라고 해도 무방하다. 하지만 약간 꼬아놨으니 BFS의 시작점이 여러군데다. 근데 뭐 별다를 거 없다. 시작점을 큐에 다 넣고 시작하는 것과 같이 얘도 똑같이 해주면 된다. #맞는 풀이 다만 최적화는 되어있지 않은 풀이 #include #include #define X first #define Y second using nam..

이 문제도 이전 문제와 형제문제라고 할 정도로 BFS의 기본을 알려준다 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 바로 이 문제가 BFS가 탐색한 노드의 수를 알려주는 것인데 뭐 메모리랑 관련이 있다고만 해두겠다. **사실 큐에 쌓이는 노드가 더 메모리랑 관련있지만..뭐 그렇다. # 맞는 풀이 #include #include using n..

경로 탐색의 핵심은 탐색 방법이다. 그 중 얘는 BFS다. www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 왜 BFS일까?는 최단경로를 찾아야하기 때문이다. DFS는 최단경로를 보장하는 방법이 아니다. 어떠한 경우에 대해서도 최단경로를 찾기 위해서는 BFS를 쓸 수 있다. 일반적으로 메모리는 DFS보다 BFS가 많이 먹을 수 있는..가능성이 높다 나는 이것을 논리가 맞다고 생각하고도 엄청 많이 틀렸다. 바로 입력에 대해서 확인을 소홀히 해서 그렇다. 이 문제에서 입력은 공백없이 주어졌다. ..

음 0.5초에 추가 시간이 없네 ㅎ 문제 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력 첫째 줄에 분수를 출력한다. 음 보면 행렬의 행과 열을 맞춘 느낌이다 ㅎ 분수로 위장한 행렬느낌 즉, 분자가 행 분모가..