알고리즘 문제풀이/추천 문제 (55) 썸네일형 리스트형 [ 백준 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.. [ 백준 2294 ] 동전2 (C++) https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제를 읽고 bfs로 풀면 되겠다고 생각해 bfs로 풀었다. 아이디어는 간단하다. 모든 동전마다 몇 개의 동전이 필요한지 저장해주는 map이라는 1차원 배열을 생성한다. 만약에 사용 가능한 동전이 1,3원 이라고 가정하면, map[5] = 5원을 만드는 최소 동전(1,3원) 개수 map[8] = 8원을 만드는 최소 동전(1,3원) 개수 map[n] = n원을 만드는 .. [ 백준 2293 ] 동전1(C++) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 정답률이 높아서 좀 당황했던 문제다. 다들 천잰가...? Dp 문제다. 점화식만 잘 세우면 되는데 항상 이게 어렵다. 우선 점화식부터 알아보자. dp[make] = dp[make] + dp[make - use] dp[i] : 동전 i를 만드는 모든 경우의 수 dp[0] = 1 은 고정 이 점화식을 가지고 고민을 해보자. 점화식의 의미를 이해하는 것이 핵심이다. 아래 예시를 보면 이해하는 데 도움이 .. [ 백준 3085 ] 사탕 게임 (C++) https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 제한 시간이 1초로 널널해서 모든 경우의 수를 다 고려해줬다. 모든 칸에 대해 가로/세로 다 swap 해주고 그때의 연속 사탕 수를 확인했다. 코드에서 check() 함수는 최대 연속 사탕수를 반환해주는 함수다. 유의할 점은 swap 해주고 다시 원위치 시켜줘야 하므로 다시 swap을 해줘야 한다. #include #include using namespace std; int N; char map[50][50]; int check() { int Max = 0; char now; int cnt; // 1. 가로 for.. 이전 1 2 3 4 5 6 7 다음
