아무거나

문제 내용 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 풀이 시간 50분 풀이 과정 처음에 문제를 제대로 안 읽어서 비활성 바이러스를 제외한 빈칸중 M개를 골라서 나오는 최소 값인줄 알았다. 하지만 비활성 바이러스중 M개를 활성화 시켜서 나올수 있는 최소 값이었다. 문제 풀이는 조합 + BFS를 이용해서 풀었다. 정답 코드 import java.io.BufferedReader; import java.io.InputStreamReader; impor..

문제 내용 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 시간 50분 풀이 과정 각각의 땅을 체크하는 과정이나, 다리 길이를 구하는 과정에서는 BFS를 이용하였다. 하지만 땅에서 바다로 바뀌는 지점을 찾는 과정에서 시간이 많이 소요 되었다. 이 지점은 간단하게 서로 인접한 두 위치의 값만 비교하면 되는것이었다. (Sliding window 느낌) 둘다 땅이거나 둘다 바다인 경우에는 두 지점의 합은 한 지점의 합의 2배와 같을 것이다. 하지만 ..

문제 내용 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 시간 45분 풀이 과정 문제에 써있는 방식 그대로 각 벽마다 BFS를 실행하였다. -> 시간초과 역으로 생각해서 빈곳들의 크기를 구하고 빈곳의 값을 개수로 넣어줬다. 이후 각 벽마다 사방의 빈곳의 개수의 합+1을 넣었다.-> 오답 => 벽 주위의 빈곳들이 서로 연결되어 있는 경우를 고려하지 못했다. Map을 사용해서 각 빈 그룹별 개수를 넣었다. 이후 빈곳의 ..

문제 내용 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 과정 -그래프 탐색이라고 판단하여 이를 이용해 문제를 풀이,python의 특성상 BFS를 이용하였음. 풀이중 문제점 1. 코드의 복잡함 문제점 해결 과정 1. 최대한 간략하게 코드를 수정함. 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 3..

문제 내용 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 풀이 과정 -유니온 파인드와 그래프탐색(BFS) 이렇게 두가지 방향성을 생각함. -유니온 파인드 같은 경우는 유니온 과정에서 적절하지 않다고 판단하여 BFS로 진행하기로 했음. 풀이중 문제점 1.deque 사용의 미숙함 문제점 해결 과정 1.deque에 대해 학습을 진행한후 풀이 진행. => 차후 deque관련 포스트 작성..

문제 내용 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include #incl..

문제 내용 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 ..

문제 내용 https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #include //tie ..

문제 내용 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 6..