알고리즘 문제풀이 (58) 썸네일형 리스트형 [ 백준 16953 ] A → B (C++) https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 재귀함수로 쉽게 해결할 수 있는 문제다. 재귀함수가 정말 직관적이면서도 짜기 어려운 코드 같다. 그런데 꾸준한 연습으로 충분히 극복 가능한 영역이라고 생각한다. 예전에는 재귀함수 정말 어려워 했었는데 이 문제는 거의 10분 만에 푼 것 같다. 딱히 설명할 게 많이 없다. 문제 조건대로 2를 곱해주거나 끝자리에 1을 더해 주는 것을 반복하면 된다. 종료 조건은 숫자가 일치하거나, 초과하거나 이렇게 두 가지다. Min 함수를 선언해줘서 최소값을 계속 갱신하면 된다. 코드를 보면 어렵지 않게 이해할 수 있을 것이다. 주의할 점.. [ 백준 1743 ] 음식물 피하기 (C++) https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 이차원 배열 map을 만들고 음식물 위치에 모두 1을 대입해준다. 모든 경로를 탐색하면서 아직 방문하지 않았고, map의 값이 1이면 bfs를 통해 연속된 1을 찾아주면 된다. 이때 bfs는 연속된 1의 개수를 반환해주는데, 마지막에 최대값을 출력해주기만 하면 된다. #include #include #include #include using namespac.. [ 백준 2178 ] 미로 탐색 (C++) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS 문제!! 이제 경로 탐색은 어느정도 숙달된 것 같다. 이 문제는 딱히 예외 상황이 없어서 한 번에 해결할 수 있었다. visit 배열이 방문 배열이면서 해당 위치까지 도달하기 위한 최소의 칸 수가 된다. 큐에 push 할 때 visit 배열 초기화를 아래와 같이 해주면 된다. visit[new_row][new_col] = visit[row][col] + 1 #include #include #include using nam.. [ 백준 1303 ] 전쟁 - 전투 (C++) https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net BFS로 해결할 수 있는 문제다. 이차원 문자 배열을 map이라고 했을 때 문자값이 'W'인지 'B'인지에 따라 케이스를 나눠 탐색을 진행하야 한다. 나는 type 변수를 두어 1일 때 'W'를, 2일 때 'B'를 탐색하도록 코드를 짰다. 방법은 간단하다. 각 군집 벡터 w, b를 생성한 뒤에 map을 처음부터 끝까지 탐색하면서 'W'면 문자에 맞는 군집을 찾아주고 w에 .. [ 백준 1260 ] DFS와 BFS (C++) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS의 원리만 알면 쉬운 문제다. 주의할 점은 노드간 간선 연결을 할 때 양방향이기 때문에 둘 다 연결해줘야 한다. 또한 작은 숫자부터 방문해야 하기 때문에 노드를 오름차순으로 정렬해줘야 한다. 벡터 또는 배열을 사용할 수 있는데 나는 벡터를 사용해서 풀었다. #include #include #include #include using namespac.. [ 백준 17070 ] 파이프 옮기기 1 (C++) https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제를 읽고 dfs로 해결할 수 있겠다는 생각을 했다. 파이프는 가로, 세로, 대각선 모양만 허용되고 각 경우마다 움직일 수 있는 방법이 정해져 있다. 이를 각 케이스마다 구현해주면 된다. 목표 지점이 벽인 경우만 주의하면 된다. DFS 함수 형태 void dfs(int row, int col, int type, int* cnt) row: 이동 방향 머리의 행 인덱스 co.. [ 백준 1038 ] 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 문제를 읽고 그냥 감소하는 수를 다 구하고 오름차순 정렬하면 될 것 같았다. 재귀 함수로 구현할 수 있는 문제다. 아래의 아이디어를 아주 약간만 응용하면 된다. 현재 숫자는 X X의 1의 자리 숫자는 k X * 10 + (k - α) 는 항상 감소하는 수다. 이제 감소하는 수를 구하는 함수 get_dec()를 살펴보자. void get_dec(long now, int last){ f.. [ 백준 2667 ] 단지번호붙이기 (C++) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 경로 탐색 문제로, bfs와 dfs로 어렵지 않게 풀 수 있다. 두 가지 방법으로 모두 풀어 보았다. 그냥 단순히 모든 경로를 검사하면서 1이 적힌 위치에 가면 그 위치부터 bfs 또는 dfs를 돌리면 된다. 이때 count라는 변수를 두어 단지 안에 번호가 몇 개 있는지 세어준다. 모든 번호를 answer라는 벡터에 저장한 후, 마지막에 벡터를 정렬하고 출력해주기만 하면 된다. bfs 풀이 #in.. 이전 1 2 3 4 5 6 7 8 다음
