코딩테스트

[백준] 최소 스패닝 트리

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 문제 제목에서 의미하는 것과 같이, 최소 신장 트리의 cost를 return 해야 하는 문제입니다. 최소 신장 트리는 Kruskal 알고리즘이나 Prim알고리즘을 사용한다고 합니다. Prim 알고리즘의 경우 아직 한번도 구현해 본적이 없어서 예전에 파이썬으로 구현해본 Kruskal알고리즘으로 구현하였습니다. 실제 구현..

[백준] 벡터 매칭

https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 점들이 N(짝수) 개 찍혀 있고, 이 점들을 둘씩 이으면 벡터가 생기게 됩니다. 이런 벡터들의 합의 최솟값을 구하는 문제입니다. 어렵게 생각하지 말고, 벡터의 합은 각각의 성분들을 더하면 되는 것을 생각해봅시다. 만약 이렇게 두개의 벡터가 있다면, 벡터의 합은 이 되고 이 길이가 우리가 구하는 벡터의 합의 길이입니다. 한마디로, N개의 점들중 시작점 N/..

[백준] 알파벳

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 보드의 각 칸에 알파벳 대문자가 적혀있는 상황입니다. 이 때, 알파벳이 겹치지 않게 가장 좌측 위에서 이동을 할 때, 총 몇개의 알파벳을 최대로 밟고 지나갈 수 있는지를 구하는 문제입니다. bfs나 dfs를 사용해야 할 것으로 짐작할 수 있습니다. 여기에서 만약 bfs를 사용하게 되면, 저장해야 하는 상태로 판의 상태도 있을 것이기 때문에 관리가 어렵습니다..

[백준] 녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제부터 간단하게 요약하면, N*N의 모양의 동굴을 통과하는데, 각 칸에서 돈을 빼앗기게 됩니다. 가장 왼쪽 상단에서 출발해서 가장 오른쪽 하단에 도달할 때 까지 최소한으로 돈을 빼앗길 때, 얼마를 빼앗기는지 구해야 하는 문제입니다. bfs를 이용하여 문제를 해결할 수 있습니다. 동굴 모양과 같은 비용 저장 array를 둡니다. 그리고 매번 상하좌우를 체크해보고, 해당 칸으로 진..

[백준] 알고스팟

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 우선 문제부터 요약하면, 미로에 사람들이 갇혀있는데, 미로의 어떤 부분은 빈 방이 아니라 벽이라고 합니다. 벽을 부시는 횟수를 최소화 해서 가장 왼쪽 상단에서 가장 오른쪽 하단으로 이동하려 할 때, 최소로 벽을 부시는 횟수를 구해야 하는 문제입니다. 많이 나오는 미로 찾기 문제 유형입니다. bfs를 이용하였고, bfs의 상태가 발전하는경우 (즉 queue에 넣는 경우)는 해당..

[백준] IOIOI

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 우선 문제부터 요약하면, I와 O로만 이루어진 문자열이 주어질 때, 해당 문자열에서 IOI가 반복되는 패턴을 반복수에 따라 P1, P2등으로 정의할 때, PN이 주어진 문자열에서 몇번 등장하는지 카운팅을 하는 문제입니다. 일단 문자열의 길이가 100만개 까지 가능하기 때문에 O(N)이나 O(NlogN) 정도 까지의 복잡도만 사용이..

[백준] Σ

https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 우선 문제부터 요약하면, 기약 분수들을 여러개 더하게 되면 통분 등으로 인해 분모등이 원하는 범위 안에서 유지되도록 관리하기가 어렵습니다. 그래서 페르마 소정리를 이용한 역원을 통해 다르게 표현하여 좀더 간단하게 더하려고 하는데, 이렇게 다르게 표현한 것들을 더한 결과를 구하는 문제입니다. 실제로 문제를 한번 읽어보는 것이 정확합니다. 사실 수학적인 지식 보다는 문제에서 무엇을 우리에게 구하라고 이야기하는 지만 정확하게 파악하면 되는 문제입니다. 문..

[백준] 파이프 옮기기 1

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net DP를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 문제에서 주어진 규칙대로 파이프를 움직여서 파이프의 한쪽 끝이 가장 오른쪽 아래에 올 때까지 이동시켜야 합니다. 이 때, 목표 지점에 도달할 수 있는 경우의 수를 return 해야하는 문제입니다. 특정 칸에 도달할 때, 어떤 방식을 통해 도달하는지를 이용해 dp table을 구성하면 됩니다. 무슨 이야기인지 그..