문제https://www.acmicpc.net/problem/28283문제 설명네트워크 안에 N개의 컴퓨터가 존재하며 서로 다른 두 컴퓨터 쌍을 연결하는 M개의 통신망이 존재한다. i번째 통신망은 $S_i$번과 $E_i$번 컴퓨터를 잇고 있다. 두 컴퓨터 쌍을 연결하는 통신망은 최대 1개이다.X개의 컴퓨터를 동시에 해킹하여 돈을 얻고자 한다.i번 컴퓨터를 해킹하면 1분 뒤부터 매분 $A_i$의 돈을 가져올 수 있다.해킹 후 0.5분부터 $B_1, B_2...B_Y$번 컴퓨터에 보안 시스템이 설치 된다. 보안 프로그램이 설치되고 난 후부터는 돈을 가져올 수 없다.보안 시스템은 통신망을 통해 1분마다 연쇄적으로 전파된다.보안 시스템을 피해 최대한 많은 돈을 얻을 방법을 찾아 최대 금액을 구한다. 풀이다익스트..

문제https://www.acmicpc.net/problem/25195문제 설명N개의 정점과 M개의 간선으로 이루어진 DAG가 주어진다.곰곰이는 1번 정점부터 출발해 간선을 따라 이동한다. 더 이상 이동할 수 없는 경우 여행을 종료한다.곰곰이의 팬은 그래프 위의 정점 일부에서 잠복한다.곰곰이가 해당 정점을 지날 때 잠복한 팬이 존재한다면 서로 만나게된다.투어리스트 곰곰이가 어떻게 이동하더라도 팬을 만난다면 "Yes" 만나지 않고 여행할 수 있는 방법이 존재한다면 "yes"를 출력한다.풀이우선 그래프 탐색 문제이기 때문에 BFS 혹은 DFS로 접근했다. BFS의 시간 복잡도는$O(V+E)$이다.이 문제의 범위는 최악의 경우 $V = 10^5, E = 10^5$이므로 충분히 탐색이 가능하다고 판단했다. 다음..

문제https://www.acmicpc.net/problem/1263문제 설명N개의 할일이 입력으로 주어진다.$S_i, T_i$가 입력으로 주어지는데 이는 각각 $T_i $시간이 걸리고, $S_i$시 까지 일을 처리해야 한다는 의미다.0시부터 활동을 시작할 수 있고 동시에 두 개 이상의 일은 같은 시간에 처리할 수 없다.최대한 늦게 일을 시작할 수 있는 시간을 구한다. 풀이그리디와 정렬을 이용해서 문제를 풀이했다. 먼저 입력으로 주어지는 각 일을 $[T_i, S_i]$ 형태로 저장했다. 여기서 $T_i$는 일을 처리하는 데 걸리는 시간이고, $S_i$는 해당 일을 반드시 끝내야 하는 마감 시간이다. time 리스트에 모든 일을 저장한 뒤 정렬을 진행했다. 마감 시간이 빠른 작업부터 처리하기 위해 마감 시..

문제https://www.acmicpc.net/problem/25585문제 설명대각선 네 방향으로 이동이 가능한 저거노트와 레기온이 2차원 배열로 주어진다.빈 공간 : 0, 저거노트 : 1, 레기온 : 2저거노트의 현재 위치가 (r,c)라면 (r-1, c-1), (r-1, c+1), (r+1, c-1), (r+1, c+1)로 이동이 가능하다.저거노트가 모든 레기온을 해치우는데 걸리는 최소 시간을 계산한다. 풀이처음에는 DFS로 푸는 문제라고 생각해서 꽤 오랜 시간 동안 삽질을 했다. 문제의 배열 크기가 100×100이기 때문에 단순히 DFS로 풀이하게 되면 탐색 가능한 위치가 약 5000개 정도가 된다. 이 모든 위치를 탐색한다고 가정하면 경우의 수는 대략 5000! 수준이 되는데, 이는 현실적으로 불가..

문제https://www.acmicpc.net/problem/1513문제 설명N*M 크기의 직사각형 도시가 존재한다.세준이의 집은 (1,1)에 있고, 학원은 (N,M)에 있고, 오락실은 C개 있다.집에서 학원까지 이동해야 한다. 이 때 오락실은 (1,1) 혹은 (N,M)에 존재할 수 있다.현재 위치가 (r,c)일 때 (r+1, c) 혹은 (r, c+1)로 이동이 가능하다.이 때 오락실을 방문한다면 오락실 번호가 증가하는 순서대로 방문해야 한다.1번 -> 2번 -> 3번 : 가능2번 -> 1번 : 불가능오락실을 0번부터 C번 방문했을 때 까지의 모든 경우의 수를 출력한다. 풀이세준이는 현재 위치를 기준으로 r이 증가하거나, c가 증가하는 방향으로만 이동한다. 그럴 경우에 학원에 도착하는 경우의 수를 모두 ..

문제https://www.acmicpc.net/problem/19590문제 설명구슬의 종류 N과 $x_1,x_2,x_3....x_N$총 N개의 i번째 종류의 구슬의 개수 $x_i$가 주어진다.구슬 두 개를 부딪히면 서로 깨져 없어진다.현재 가지고 있는 구슬의 개수를 최소로 했을 때 남은 구슬의 개수를 출력한다.풀이처음에는 단순하게 힙을 사용한 시뮬레이션 방식으로 접근했다.가장 큰 값에서 작은 값을 순차적으로 빼면 정답이 나오지 않을까 생각하며 코드를 작성했다.하지만 결과는 틀렸고, 반례가 존재했다. 예를 들어 구슬의 개수가 [6, 4, 4]라고 해보자. 내가 처음 생각했던 방식대로라면 6에서 4를 빼서 [4, 2]가 되고, 다시 4에서 2를 빼면 결과는 2가 된다. 따라서 정답이 2라고 생각할 수 있다...

문제https://www.acmicpc.net/problem/33633문제 설명길이가 N인 우박수열 $A_1,A_2,,A_3,..., A_N$을 만들려고 한다.우박수열은 다음 조건을 만족하는 수열 A이다.$ 1 ≤ i $A_N = 1$이다. 또한 $1 ≤ i N이 주어질 때 가능한 길이가 N인 우박수열의 개수를 구하고, 가능한 우박수열의 $A_1$을 오름차순으로 출력한다. 풀이처음에 문제를 잘못 이해해서 시간이 꽤 걸렸다.그래서 헷갈리지 않도록 먼저 문제를 정확히 이해하고 넘어가자. 헷갈렸던 부분은 A의 각 원소가 양의 정수인가? 하는 점이었다. 문제에서는 “양의 정수 i에 대하여”라고만 나와 있고,$A_i$가 양의 정수인지 명확하게 적혀 있지 않았다.그래서 분수나 음수도 가능한가 고민했다. 하지만 문제..

문제https://www.acmicpc.net/problem/1790문제 설명1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.1234567891011121314151617181920212223...이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.이 때 수의 길이가 K보다 작아서 K번째 자리 숫자가 없는 경우는 -1을 출력한다.풀이알고리즘을 풀다 보면 1부터 N까지의 수를 나열한다던가, N이 엄청 클 때 K번째 숫자 자리 등등을 구한다던가의 유형의 문제들을 많이 볼 수 있다. 이런 문제들의 풀 때 공통점은 규칙이 존재한다는 것이다. 예를 들면 이런 것이다.1~9 = 9개 (n = 1)10~90 = 90개 (n = 2)10..

총 학습 시간공부 기록알고리즘 문제 풀이문제 명(블로그 링크)소요 시간난이도노드 사이의 거리10분 Gold 5 사과나무37분Gold 5 회고사실 첫 문제로 플래티넘 5 문제를 풀어보려고 했다.하지만 문제가 정말 너무 어려웠던 것이다.. 1시간 정도 고민을 했는데 계속 한 문제만 붙잡고 있자니 어제와 같은 상황이 발생할 것 같아서, 해답을 봤는데도 너무 어려웠다. 그래서 이 문제는 잠깐 킵하도록 하고 다른 문제로 넘어왔다. 랜덤 골드 문제로 총 두 문제를 풀이했는데 하나는 정석 BFS, 하나는 2차원 누적합이었다. 골드 5 정도의 BFS, DFS 문제는 거의 대부분 정석적인 탐색 문제이기 때문에 이제 그냥 매크로처럼 코드가 쳐지는 느낌이다. 누적합 문제를 정말 오랜만에 풀어보는 거 같은데, 기억이 날 듯..

문제https://www.acmicpc.net/problem/1240문제 설명N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받는다.두 노드 사이의 거리를 구하여라. 풀이어렵지 않게 BFS 탐색 알고리즘을 사용하여 풀이했다. 문제에서 주어지는 노드 간 정보를 통해서 그래프를 생성한다. 이때 주어진 거리 정보도 그래프에 함께 저장한다.그래프 생성 후 M개의 노드 쌍이 입력되면, start 위치에서 BFS 탐색을 진행하고 end위치에 도달했을 때 dist를 반환 후 출력한다. 정말 전형적인 BFS문제이기 때문에 그래프 탐색 문제를 많이 풀어봤다면 쉽게 풀 수 있는 문제였다.코드import sysfrom collections import dequeinput = sys.stdin.readline..