컴굥일지

문제 링크&사진 문제 내용 1이 배추가 심어진 곳, 0이 그렇지 않은 곳이다. 지렁이가 있으면 배추를 해충으로부터 보호할 수 있는데, 인접한 배추들끼리는 지렁이 하나로도 충분하다. 배추가 심어져 있는 위치를 입력받아, 지렁이가 최소 몇 마리나 필요한지를 출력하면 된다. 문제 풀이 이 문제는 bfs, dfs 둘 모두로 풀 수 있는 문제이다. 코드 BFS 풀이 #include #include #include using namespace std; int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, 1, -1}; int m, n, k; void bfs(vector &arr, vector &visited, int r, int c) { queue q; q.push({r, c}); vi..

문제 https://www.acmicpc.net/problem/1074 문제 내용 사진에 보이는 것처럼 방문을 한다고 할 때, r, c를 방문했을 때의 값을 구하면 된다. 문제 풀이 2^N * 2^N 크기의 2차원 배열을 4등분하여 r, c가 어느 사분면에 속해있는지 체크하고 똑같이 재귀적으로 계산해 나가면 된다. 코드 #include using namespace std; int visit(int N, int r, int c) { if (N == 0) { // N이 0인경우 배열 자체가 없음 return 0; } int length = (1 = length) { // 2사분면 return visit(N - 1, r, c - length) + length * length; } else if (r >= le..

문제 https://www.acmicpc.net/problem/11729 문제 내용 하노이 탑을 하는데, n개의 원판을 3번 기둥으로 옮기는 최소 이동 횟수와 수행 과정을 출력하면 된다. 문제 풀이 먼저 수행 과정은 재귀를 통해 풀 수 있다. n개의 원판을 1에서 3으로 옮긴다면, 1. n-1개의 원판을 기둥 1에서 2로 옮긴다. 2. n번 원판을 기둥 3으로 옮긴다. 3. n-1개의 원판을 기둥 2에서 3으로 옮긴다. 원판이 1개일 때는 당연히 기둥에서 기둥으로 옮길 수 있다. n==1일 때도 성립하고, n개일 때도 성립하니 n+1일 때도 성립한다고 볼 수 있다. (== 재귀로 풀 수 있다) 이동 횟수를 구하는 부분은 수학적 지식이 조금 필요하다. 이동 횟수는 n-1개의 원판을 1에서 2로 옮길 때 A..

문제 https://www.acmicpc.net/problem/2178 문제 내용 N*M크기의 미로 배열이 주어지고, (1,1)에서 (N, M)까지 이동할 때 지나가게 되는 최소의 칸 수를 구하면 되는 문제이다. 1은 이동할 수 있는 칸이고 0은 벽이며, 서로 인접한 칸으로만 이동할 수 있다. 문제 풀이 bfs를 활용하여 문제를 풀면 되는데, 방문 여부를 bool 값으로 저장하지 말고 거리를 저장하면 된다. 이때 주의할 점은 입력이 공백 없이 주어진다는 점이다. 코드 #include #include using namespace std; int arr[101][101]; int dist[101][101]; int n, m; int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, ..

문제 https://www.acmicpc.net/problem/10431 문제 내용 학생들의 키 순서대로 줄을 세우려고 한다. 결과적으로 오름차순을 만들어야 하지만, 아래 과정을 따라야 한다 1. 먼저 아무나 한 명을 맨 앞 줄에 세운다. 2. 그다음부터는 한 명씩 줄의 맨 뒤에 서며, 매번 아래 과정을 거친다. 3-1. 자기보다 키가 큰 사람이 앞에 없으면 그 자리에 서 있는다. 3-2. 자기 앞에 키 큰 사람이 한 명 이상 있다면, 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때 A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러선다. 문제에서 학생들이 총 얼마나 뒤로 물러섰는지를 구하면 된다. 문제 풀이 3-2 조건에서, 자기 앞에 키 큰 사람이 한 명 이상 있으면, 그중..

문제 https://www.acmicpc.net/problem/1697 문제 내용 수빈이가 동생이 있는 곳까지 가장 빠르게 갈 수 있는 시간을 구하면 된다. 수빈이는 1초 후에 x-1, x+1, 2x 의 위치로 이동할 수 있다. 문제 풀이 bfs를 통해 문제를 풀면 된다. while문을 돌면서 배열에 방문했다는 표시를 true/fasle로 남기는 것이 아니라, 그 위치까지 몇 초 걸리는지를 남기면 된다. 코드 #include #include using namespace std; int arr[100001]; int n, k; int returnNextPosition(int type, int num) { if (type == 0) return num - 1; else if (type == 1) return..

문제 https://www.acmicpc.net/problem/17298 문제 내용 수열이 주어지고, 수열의 각 원소의 오큰등수를 구하면 되는 문제이다. 오큰등수란 자신보다 오른쪽에 있으면서, 자신보다 커야 하며, 그중에서 가장 왼쪽에 있는 수이다. 즉, 자신보다 오른쪽에 있는 수들 중에 가장 가까운 큰 수를 찾으면 되는 문제이다. 문제 풀이 n의 범위가 10^6이기 때문에, 이중 for문으로 돌리면 시간초과가 나게 된다. 그래서 stack을 사용하여 문제를 풀었는데, 수열을 역순으로 탐색하며 문제를 풀면 된다. 기본적으로 모든 원소를 stack에 push하며 나가되, 자신보다 작은 수는 pop을 하고 자신을 push 하는 과정을 진행하면 된다. 아래 글에 풀이가 정말 잘 설명이 되어있다. https:/..

문제 https://www.acmicpc.net/problem/1874 문제 내용 스택에 1~n 숫자를 push와 pop을 할 수 있다. 단, 이때 반드시 오름차순으로 push를 해야만 한다. 우리는 입력으로 주어진 수열을 만들기 위해, 어떤 순서로 push와 pop을 하면 되는지를 구하면 된다. push/pop을 통해 수열을 만들 수 없으면 "NO"를 출력하면 된다. 문제 풀이 예제 1을 순서대로 표시해 보았다. 스택의 가장 위에 있는 값보다 input의 값이 더 작으면 "NO"를 출력하고 끝내야 한다는 점을 주의하면 된다. 코드 #include #include #include using namespace std; int main() { int n; cin >> n; stack st; vector re..

문제 https://www.acmicpc.net/problem/5648 문제 내용 숫자를 여러 개 입력받아, 각 숫자를 거꾸로 뒤집고, 이 숫자들을 정렬하여 출력하면 된다. 이때 주의해야 할 점은, 숫자는 10^12의 범위까지이므로 long long 자료형을 사용해야 하며, 뒤집었을 때 앞에 0이 오면 그 0은 생략해야 한다는 점이다. 문제 풀이 아래 과정을 거치면 된다. 1. 숫자를 "문자열"로 입력받는다. (숫자로 입력받아도 되지만, 어차피 문자열로 다시 바꿔야 한다.) 2. reverse()를 통해 문자열을 뒤집고, 그 문자열을 숫자로 바꾼다. 3. 배열에 집어넣는다. 각 원소별로 위의 과정을 거친 후, 배열에 모든 원소가 들어가면 정렬 후 출력하면 된다. 코드 #include #include #i..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42885 문제 내용 입력으로 사람들의 몸무게 정보를 담은 배열과 구명보트의 무게 제한을 받는다. 구명보트에는 최대 2명까지 탈 수 있으며, 이때 사람들의 몸무게 합이 구명보트의 무게 제한보다 같거나 작아야 한다. 우리는 필요한 구명보트의 최솟값을 구하면 된다. 문제 풀이 먼저 사람들의 몸무게 정보를 담은 배열을 정렬해야 한다. 그리고 양쪽 끝에서부터 차례로 몸무게를 더해서 limit보다 작으면 그 둘을 한 보트에 태운다. 만약 더한 몸무게가 limit보다 큰 경우, 몸무게가 큰 쪽은 혼자 타야 한다. 몸무게가 작은 사람은, 오른쪽-1 위치의 사람과 함께 탈 수도 있겠지만, 몸무게가 큰 큰 사람은..