컴굥일지

문제 https://www.acmicpc.net/problem/15650 문제 내용 1~N까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열은 오름차순이어야 하며, 사전 순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M (1)과 다르게 N과 M (2)는 수열이 오름차순이어야 한다는 조건이 추가되었다. N과 M (1)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 되었지만, N과 M (2)는 오름차순 수열을 만들어야 하기 때문에, 이전에 어떤 값을 선택했었는지에 대한 정보도 넘겨주어야 한다. 또한, 오름차순을 유지하기 위해 이전에 선택한 값을 받아, 그 이후 값부터 for문을 돌기 때문에 used 배열도 필요 없다. [BOJ/백준 15649][C++] N과 M (..

문제 https://www.acmicpc.net/problem/15649 문제 내용 1~N 까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전 순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M은 백트래킹의 대표적인 문제이다. N과 M (1)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 된다. 코드 #include #include using namespace std; int n, m; vector used(9, false); vector result(8, 0); void back(int cnt) { // 몇개를 선택했는지 if (cnt == m) { for (int i = 0; i < m; i++) { cout m; back(0); }

문제 상황 노션에서 가끔 글을 쓰다 보면 왼쪽 위에 버퍼가 뜨고 한글 입력이 지연되는 경험을 할 수 있다. 이는 윈도우 노션 앱에서 쓸 때 일어나는 현상이다. 문제 해결 방법 문제 해결 방법은 매우 간단하다. 키보드의 window 키를 두 번 눌러주면 된다. 근본적인 해결방법은 키보드를 삭제하고 다시 설치해야 하는 것 같은데, 개인적으로 좀 번거롭다고 생각해서 그냥 윈도우 키 두 번 눌러주는 방식을 사용하려 한다.

문제 https://www.acmicpc.net/problem/1182 문제 내용 N개의 정수로 이루어진 수열의, 크기가 양수인 부분집합 중에 합이 S인 경우의 수를 구하면 된다. 문제 풀이 모든 원소는 2가지로 구분된다. 부분수열에 포함되거나, 포함되지 않거나. 각 원소에 대해 포함된 경우와 포함되지 않는 경우를 계산해보면 된다. 단, 합이 0일 때는 모든 원소를 포함시키지 않는 경우(공집합)도 포함되므로, 개수에서 -1을 해줘야 한다. 코드 #include using namespace std; int arr[20]; int n, s; int cnt = 0; void back(int current, int ssum) { if (current == n) { if (ssum == s) { cnt++; } ..

문제 링크&사진 문제 내용 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..