링크 https://www.acmicpc.net/problem/1541 난이도(solved.ac 참고) 실버2 풀이 숫자 외에 연산자가 들어간 input값 처리는 거의 해본 기억이 없어서 좀 헤맸다. 여기서 내가 생각하는 키포인트는, -를 기준으로 나누면 + 연산자를 끼고 있는 숫자들은 전부 리스트의 원소로 따로 들어가게 된다는 점이다. 여기에서 최소값을 만들려면 + 연산자로 묶여있는 두 수는 무조건 빼야 한다. -를 기준으로 split 메소드를 사용해 나눈 것이므로 무조건 빼주더라도 출력을 구하는 데 지장이 없다. 이제 문제는, ['50+40']의 형태로 되어있는 리스트를 [50, 40]으로 쪼개는 방법이었는데, 이 또한 +를 기준으로 split을 한 결과를 새로운 리스트에 저장한 뒤, 그 리스트를 돌..

링크 https://www.acmicpc.net/problem/1976 난이도(solved.ac 참고) 골드4 풀이 input값으로 인접 행렬 형태가 들어갈 거라고는 생각도 안하고 있다가 시간을 좀 날렸다. 핵심은 27행~31행인데, i에 대한 for문을 진행할때마다 list input을 받아서 j에 대한 for문을 다시 돈 다음, j-1번째 인덱스의 값이 1인지 아닌지 여부를 판단하였다. 이게 1이라면, 예를들어 (1, 2) 좌표가 1이라면 도시 1과 도시 2는 연결이 되어있는 것이다. 따라서 union으로 이 두 개를 합집합 처리를 한다. 이제 이렇게 할 경우 1로 들어간 부분에 대해서는 전부 합집합 처리가 되어, 연결이 되어있는 상태가 되었다. 이제 최상위 부모 노드를 찾는 find_parent를 ..

링크 https://www.acmicpc.net/problem/1647 난이도(solved.ac 참고) 골드4 풀이 최소 스패닝 트리와 크루스칼 알고리즘을 공부한 뒤에 가볍게 풀어본 문제인데, 재밌었다. 최소 스패닝 트리는 하나의 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이며 가중치의 합이 최소인 그래프이다. 그리고 이 최소 스패닝 트리에 관한 알고리즘으로는 크루스칼 알고리즘이 있다. 크루스칼 알고리즘은 그래프에서 A와 B를 선택했을 때 A에서 B로 가는 경로가 반드시 존재하도록 최소 비용으로 간선을 배치하는 경우의 수에 관한 알고리즘이다. 이 알고리즘의 지향점은 당연히 최소 스패닝 트리를 만족하면서 가중치의 합이 최소가 되게끔 하는 것이다. 일반적인 크루스칼 알고리즘의 기본 ..

링크 https://www.acmicpc.net/problem/22846 난이도(solved.ac 참고) 골드3 풀이 처음에는 링고와 칼리가 보는 모니터가 각각 따로 있는 줄 알았다. 그랬는데, 다시 보니까 두명이 같은 모니터를 보고 있었고, 그 상황에서 약수를 더해주는 것이었다. 문제가 감이 안와서 유형을 봤는데 게임 이론이었다. 내가 경제시간에 배운 게임이론은 매 상황마다 자신에게 최대한으로 유리한 결정을 내리는 것에 대한 이론으로 기억했다. 일단 트리를 그려봤다. 첫 시작은 칼리이므로 칼리는 무조건 1을 더해 2가 될 것이다. 이제 그 다음부터가 시작이다. 각자는 K가 무엇인지 알고있다고 가정했다. 그래야 그에 맞는 최선의 전략을 선택한다는 말이 맞기 때문이다. K가 2일 경우부터 생각해보자. 그러..

링크 https://www.acmicpc.net/problem/1238 난이도(solved.ac 참고) 골드3 풀이 다익스트라 이론을 접하고 백준에서 기본 문제들(1753 최단경로, 1916 최소비용구하기, 18352 특정거리의도시찾기)을 풀었는데, 이론만 알면 그냥 풀 수 있는 문제였어서 재미가 없었다. 그래서 더 난이도가 높은 문제들 중 제출 횟수가 많은 이 문제를 선택했다. 다익스트라 함수의 기본 틀은 거의 같다. 다익스트라 함수를 어떻게 활용하는지가 중요한 문제였다고 생각한다. 물론 이 문제도 다익스트라의 기본 개념만 알면 어렵진 않다. N개의 숫자로 구분된 각각의 마을에 한 명씩 살고 있다고 했다. 그러므로 1부터 n의 범위를 갖는 for문을 돌면서 다익스트라 함수를 실행한다. 여기서 중요한 부..

링크 https://www.acmicpc.net/problem/18352 난이도(solved.ac 참고) 실버2 풀이 1: BFS 활용 일반적인 BFS문제와 같으나 방문하지 않았을 경우 방문처리 하고 그 위치까지의 거리를 +1을 해준다. 그 뒤 +1해준 거리가 목표 거리 K와 같아질 경우 answer라는 리스트에 넣은 뒤 오름차순으로 정렬하고 while문 밖 if문에서 프린트 해주도록 했다. 풀이 2: 다익스트라 알고리즘 활용 13행 for문 내부 append에서 가중치를 1로 두고 넣었다. 거리와 현재 노드의 위치를 순서대로 힙에서 빼낸 뒤 cost에 현재까지의 거리(dist) + 가중치 를 넣는다. 여기서는 가중치가 1이므로 +1씩만 더해졌다. 현재 distance의 기본값이 10^9이므로 모든 위치..

링크 https://www.acmicpc.net/problem/2579 난이도(solved.ac 참고) 실버3 풀이 세번째 계단까지는 명확하다. 첫 번째 계단: 그냥 한 칸 오르는 게 최대값 두 번째 계단: 두칸을 차례대로 오르는 게 최대값 세 번째 계단: 첫 번째 계단과 두 번째 계단 중 더 큰 값을 갖고 있는 계단에서 올라오는 게 최대값 이제 네번째 계단부터는 일반화를 해야한다. 세 개의 계단을 동시에 오를 수 없으므로, 두 번째 계단에서 두 칸을 오르는 것과 세 번째 계단에서 두 칸을 오르고 첫 번째 계단에 도달한 뒤 거기에서 한 칸을 오르는 것 중에서 더 큰 값이 최대값이 된다. 이를 도식화한 것이 아래의 코드이다. for i in range(3, n): dp[i] = max(dp[i-2], dp..

링크 https://www.acmicpc.net/problem/1793 난이도(solved.ac 참고) 실버1 풀이 어제 포스팅한 바닥 공사 문제와 같아서 title 함수에 대한 코드는 별로 필요없을 것 같고, while True만 보면 될 것 같다. 이 문제는 특이하게 n이라는 값을 따로 지정해주거나 하지 않고, input값이 들어올 때마다 그에 따른 반환값을 계속 출력하도록 하였다. 이부분은 몰라서 구글링한 동아리원한테 들어서 그대로 썼다. while True: try: print(title(int(f()))) except: break try 블록 수행 중 오류가 발생하면 except 블록이 수행된다. 하지만 try 블록에서 오류가 발생하지 않는다면 except 블록은 수행되지 않는다. 즉 별 일이 ..

링크 https://www.acmicpc.net/problem/1932 난이도(solved.ac 참고) 실버1 풀이 이 문제를 풀 때 처음에 좀 막막했다. 예제 입력에서 제일 꼭대기층 7에 대해 그 아래층의 3과 8중에 어디를 가야될지를 고민을 많이 했다. 그리디처럼 생각을 하고 가장 큰 값만 집어넣자니 범위 설정이 되어있어서 그렇게 할 수 없었다. 근데 생각해보니까, 최종합이 가장 큰 경로로 가기 위해 꼭 매 층마다 어떤 수를 넣어야될지 고려할 필요는 별로 없었다. 단지, 쭉쭉 직접 값을 구하면서 내려가면서 더 큰 값을 집어넣기만 하면 되는 것이었다. 예를 들면 7 3 8 이 2층짜리 삼각형이 있다고 한다면 아래로 내려가면서 각각을 더해주는 것이다. 7 10 15 이렇게 말이다. 이런식으로 더해나가는 ..

링크 https://www.acmicpc.net/problem/18353 난이도(solved.ac 참고) 실버2 풀이 앞서 포스팅한 LIS 문제를 이해했으면 어렵지 않게 풀 수 있는 문제다. 다만 차이가 있다면, a[i]의 값이 더 작은 경우에 dp의 값을 배정해 줬다는 것이다. 그 이유는 여기에서는 증가하는 부분수열이아니라 감소하는 부분수열이기 때문이다. 여기에서 우리가 구해야하는 것은, 최대 부분수열의 길이가 아니라 전체에서 최대 부분수열의 길이만큼 빼준 값이기 때문에 대상이 되는 리스트 a의 길이에서 감소하는 최대 부분수열의 길이만큼을 빼준 값이 정답이 된다.