본문 바로가기

C

(13)
[백준] 2002 - 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 너비우선 탐색(BFS)로 풀어야 하는 문제다. '벽을 최소 1회는 뚥을수 있다'는 조건이 문제를 어렵게 만드는데, 이부분은 벽을 최소 1회 뚥었는지, 안뚥었는지에 대한 조건 여부를 방문 여부에 차이를 두고 기록해야한다. #include #include using namespace std; #include typedef struct _loc { int y; int x; int distan..
[백준] 2573 - 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net DFS(깊이우선탐색) 응용문제다. 섬의 얼음을 녹인 후에 빙산이 둘로 쪼개졌는지를 알아내기 위해 DFS를 쓰는데, 사실 DFS말고 BFS(깊이우선탐색)으로도 풀이가 가능하다. 주의할 점은 1년이 지나 빙산의 얼음을 녹일때, 다른 copy_map을 만들어서 녹은 빙산의 지도를 만들어야지, 기존 map에서 그냥 주변 0의 갯수만큼 차감하다보면, 이전에 차감해서 0이된 지역을 오인해서 과다차감을 하게될 수 있다..
[백준] 2458 - 키 순서 www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제만 읽어서는 감이 잘 오질 않는데, 결과적으로 본인의 키가 몇번째인지를 알려면 기술되어있는 N명의 '학생중 자신보다 키가 작은 학생의 수 + 자신보다 키가 큰 학생의 수 = N-1'이 되면 되는데, 이건 플로이드-워셜 알고리즘을 조금 응용하면 문제를 풀 수 있다. 알고리즘에 대한 설명은 나보다는 위키가 훨씬 더 잘 알려주니... ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9..
[백준] 3830 - 교수님은 기다리지 않는다. www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net Union Find를 응용해서 푸는 문제다. !로 시작하는 두 물체간의 무게 비교 결과가 주어질때는 union을 해주고 'diff[a] = a의 무게 - root의 무게'로 정의해서 계산해준다. 두 물체간 비교를 묻는 질의가 들어올때는 두 정점이 서로 Union이 아니면 'UNKNOWN', Union이면 diff[b] - diff[a]의 결과를 출력해주면 된다. #include in..
[백준] 2098 - 외판원 순회 www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 컴공 전공필수 과목인 알고리즘 수업을 들으면 동적계획법/DP을 배우게되면 대표적으로 배우게 되는 사례가 피보나치 수열과 외판원 순회 TSP(Travelling salesman problem)이다. 그런데 대학 졸업한지가 이미 10년이 넘은 시점에 이 문제를 보니, 전형적인 외판원 순회 문제라면서 문제 설명이 이것도 친절하지가 않다;;; 외판원 순회 문제에 대한 설명은 내가 ..
[백준] 5626 - 제단 www.acmicpc.net/problem/5626 5626번: 제단 첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명이 너무 불친절하다. 이해하는데만 한참이 걸렸다. 동적계획법/DP 문제다. DP는 점화식을 세우는게 관건인데, 이게 문제마다 점화식을 도출하는 방식이 워낙 다양하다보니 잘하는데에 왕도가 없다. -_-;;; 그냥 많이 풀어보는 것 밖에는 답이 없는 듯... 이 문제는 DP의 사이즈를 제단의 사이즈만큼 모두 잡아버리게 되면 10000 x 5000 x 4 바이트의 저장공간이 필요하게 되는데 이러면 메모리 초과가 난다. 그래서 점화식을 세우면서 메모리를 절약하는 방법에 대한 고민을 해결하는게 포인트다. N번째 제단 열에서 가..
[백준] 1339 - 단어수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 그리디(탐욕 알고리즘)로 풀 수 있는 문제다. 그리디가 보통 잘 나오지 않는 편인데 그리디로 된다. #include #include #include int count[28]; int compare(const void *a, const void *b) { return *(int*)b - *(int*)a; } int main(){ int N; memset(count, 0x00, sizeof(count)); s..
[백준] 2580 - 스도쿠 www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠 맵을 입력받아 말그대로 프로그램이 스도쿠 맵을 완성하도록 하는 문제이며 백트래킹 문제다. 백트래킹보다는 스도쿠 맵에서 숫자 후보군의 정합성을 판단하는 로직의 구현력이 더 중요한 문제같다. #include using namespace std; #include #include int map[9][9]; bool col[9][9]; bool row[9][9]; bool squ[9][9]; void solve(..
[백준] 1806 - 부분합 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투포인터 문제다. 특별히 주의해야할 사항은 없고 left, right 두 인덱스를 이동시키면서 부분의 합을 S이상을 넘기면서, 가장 짧은 길이를 갱신해나가면 된다. 시간 복잡도는 O(N) #include #include using namespace std; unsigned int arr[100001]; int main() { int n, m; scanf("%d%d", &n, &m); for (in..
[백준] 1759 - 암호만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 일전에 풀었던 N-Queen 문제와 비슷한 백트래킹을 이용한 문제이다. (N-Queen 문제가 순수 백트래킹 알고리즘만을 이용하는 것이므로 백트래킹에 대해서 좀더 높은 이해를 원한다면 이전글을 참고할 것.) [Dev/Algorithm] - [백준] 9663 - N-Queen [백준] 9663 - N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen ..