문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 각 N에 대해 N → X → N 최단 경로를 구하고, 각 최단 경로 중 최댓값을 구하는 문제였다. 문제 풀이 N이 1000까지여서 플로이드 워셜 알고리즘을 이용해 풀었다. 최댓값은 이전 문제를 풀 때 정한 값이다. 이 문제에서는 100 * 10000보다 큰 값이면 돼서 이전에 사용하던 값을 그대로 사용했다. #define _CRT_SECURE_NO_WARNING..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1 → u → v → N (혹은 1 → v → u → N)의 최단 경로의 길이를 찾는 문제였다. 문제 풀이 플루이드 워셜 알고리즘을 이용해 풀었다. 처음에 1 → u → v → N 경우에 대해서만 최솟값을 찾아줘서 틀렸는데 1 → v → u → N 경우와도 비교해 최솟값을 구해서 맞췄다. MAX_INT 값은 간선의 최대 길이인 1000 * 간선의 ..
문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 노드와 노드 사이의 최장 길이를 찾는 문제였다. 문제 풀이 처음에 모든 정점에서 dfs를 돌려서 Max 값을 구했는데 그랬더니 시간 초과가 났다. V가 최대 100,000이어서 시간 초과가 나는 것은 당연했고 다른 방법을 찾았다. 첫 번째의 dfs로 1번 노드와 비교했을 때 가장 멀리 있는 정점을 찾았고, 그 정점에서 다시 dfs를 해서 최장 길이를 구했다. 솔직히 이 문제가..
문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 구라쟁이 지민이를 위해 그룹을 만들어 해결하는 문제였다. 문제 풀이 처음 문제를 봤을 때는 진실을 아는 사람들을 vector에 집어넣고 while로 더 이상 들어가지 않을 때까지 돌린 후, 마지막에 각 파티마다 확인하는 방법을 생각했다. 코드로 옮기기 전부터 너무 비효율적인 것 같아 고민하던 찰나에 유니온 파인드가 생각났고, parent를 만들어서 푸는 방법을 떠올렸다. 진실을 아는 사람들의 paren..
문제 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net dfs를 이용해 장애물 설치의 모든 경우의 수를 다 해보고 감시를 피할 수 있는지 확인하는 문제였다. (백트래킹) 문제 풀이 처음에는 빈 칸의 좌표를 따로 저장하지 않고, 상하좌우로만 이동하며 장애물을 설치했는데 비효율적인 것 같아서 빈 칸의 좌표를 map 입력받을 때 같이 저장해줬다. 그리고 엄청난 실수를 했는데, dfs에서 count+1과 i+1을 넘겨줘야 했는데 count+1과..
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net dfs를 이용해 모든 경우의 수를 다 계산해 최솟값과 최댓값을 찾아내는 문제였다. 성공 떠있길래 보니까 1년 전에 풀었던 문제였는데 푼 기억이 없고 처음 보는 문제같았다. 만약 1년쯤 뒤에 또 이 문제를 보면 처음 보는 문제같을까..? 문제 풀이 dfs를 이용해서 연산자 4개에 대해 모든 경우에 다 적용해주었고, 종료 조건에 도달했을..
문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 사과를 먹으면 몸이 길어지는 뱀을 이동시키면서 자신의 몸에 닿거나 벽에 닿으면 종료되는 게임의 끝나는 시간을 구하는 문제였다. 문제 풀이 뱀의 머리가 먼저 이동하고 꼬리와 닿는지 확인 후에 꼬리를 이동해야 했고, 범위 지정을 N보다 클 때만 break하도록 했는데 이부분을 나중에 깨달아서 시간이 조금 걸렸다. 전체 map이 있고, 사과가 있다면 2, 뱀이 있으면 1, 아무것도 없으면 0으로 지정했다..
c++의 STL을 사용해서 풀었다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; bool VPS() { int i; char x[51]; int flag = 0; stack s; scanf("%s", x); for (i = 0; i < strlen(x); i++) { if (x[i] == '(') { s.push(x[i]); } else if (!s.empty()) { s.pop(); } else { flag = 1; break; } } if (s.empty() && flag == 0) { return true; } else return false; } int main() { int N; i..
