CS/Algorithm
[백준(파이썬/Python)] 2225_합분해 - DP
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP를 맨 처음에 공부할 때 즈음에 배우는 피보나치 수를 DP로 구하기가 떠오르는 문제였습니다. 탑다운 방식으로 DP를 해결하는 방식인데, 이 문제 역시 문제 풀이의 로직만 생각해낸다면 구현은 탑다운으로 거의 똑같이 할 수 있는 것 같습니다. 이 문제가 DP의 정당성을 가지는 이유(부분 최적해가 전체 최적해를 보장하는 이유)는 각 자릿수가 하나라도 다르면 다른 경우의 수로 취급하기 때문이입니다. 예를 들어 어떤 수 N을 3개의 숫자로 표현한다고 해보죠. N = 0 + _ _ N = 1 + _ _ N = 2 + _ _ .....
CS/Algorithm
[백준(파이썬/Python)] 8983_사냥꾼 - 이분탐색
https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 모든 사대에서 사격 가능한 영역을 구하고, 그 영역 안에 동물들이 있는지를 확인하는 방식으로 풀었을 때 시간복잡도가 O(M*N*L)이 소요됩니다. 비효율적이죠. 따라서 이분탐색을 통해 각 동물의 위치에서 가장 가까운 사대의 위치를 찾고 그 거리가 사정 거리 안에 있는지를 확인해주는 방식으로 문제를 풀었습니다. 각 동물의 위치에서 가장 가까운 사대의 위치는 x좌표가 가장 가까운 사대이기 ..
CS/Algorithm
[백준(파이썬/Python)] 두 용액 - 이분탐색, 투포인터
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net '맞왜틀'을 엄청 반복했던 문제입니다... 이 문제에서 약간 트릭(?)이었다고 생각하는 부분은 산성과 알칼리 용액이 모두 존재했을 때에도 한 종류의 용액 두 개를 골라 혼합했을 때가 최적해가 될 수 있다는 것입니다. 예를 들어 -100, -50, 1, 2라고 주어졌을 때 정답은 1+2 = 3이 되어야 하는데, 잘못 생각하면 abs(-50 + 2) = 48 이라고 ..
CS/Algorithm
[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS + DP를 이용한 문제입니다. 우선 이 문제를 DFS로만 풀려면 가능한 모든 경로의 수를 다 세야하기 때문에 정말 많은 경우의 수가 나오게 됩니다. 그러면 시간초과가 뜨겠죠? 500 * 500 배열에서 계속해서 상하좌우로 이동이 가능한 상황을 떠올려 보면 직관적으로 느낄 수 있습니다. 따라서 이 문제는 DP를 이용해서 불필요한 연산을 줄여야하는데, 이를 위해서는 우선 DP의 사용 정당성에 대해 ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 튜플 - 문자열 처리
https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 처음에 주어진 문자열 s를 리스트로 바꿔서 처리하기 위해 크게 1) 여는 대괄호, 2) 쉼표, 3) 닫는 대괄호, 4) 숫자일 때로 조건을 나누어 처리했습니다. 위 과정을 통해 주어진 문자열 s를 리스트 형태로 바꾸고 나면, 해당 이차원 리스트를 길이 순으로 정렬하고 길이가 짧은 리스트의 앞에서부터 결과 리스트..
CS/Algorithm
[백준(파이썬/Python)] 15683_감시 - 구현, 시뮬레이션
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 이 문제에서 핵심적인 부분은 어떻게 모든 카메라의 관찰 방향의 조합을 다 찾아서 그 때의 감시를 받지 않는 구역의 개수를 체크할 것인가입니다. 저같은 경우에는 카메라마다 감시 방향도 깔끔하게 떨어지지가 않아서 카메라 1~5번 마다 cam{n}_direction이라는 방향을 입력해주었고, 감시 방향을 순회하기 위해 [[방향1의 방향들], [방향2의 방향들]...] 식으로 3차원 리스트를 ..
CS/Algorithm
[백준(파이썬/Python)] 10282_해킹 - 다익스트라
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제의 조건 중에서 "d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다." 라는 표현이 있습니다. 이 부분을 주의해서 각 노드(컴퓨터)의 방향성을 정해줘야 합니다. 즉, a에서 b로 방향이 생기는 것이 아니라, b에서 a로..
CS/Algorithm
[백준(파이썬/Python)] 11779_최단경로 구하기2 - 다익스트라
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 통해 최단거리를 구한 후, 최단 거리에 대한 경로를 출력을 요구하고 있습니다. 따라서, 일반적인 다익스트라 구현에 경로를 출력하기 위한 구현이 추가로 필요한데 이 부분은 아래 코드에서 parents라는 딕셔너리로 구현햇습니다. 현재 지점에서 다른 지점으로 넘어가면서 최단거리를 갱신할 때 다음 지점의 부모를 현재 지점으로 설정해주는 것..
CS/Algorithm
[백준(파이썬/Python)] 2665_미로만들기 - BFS, 우선순위 큐
https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 얼마 전에 풀었던 백준 1261번(알고스팟, https://www.acmicpc.net/problem/1261) 문제와 동일하게 풀 수 있었던 문제입니다. BFS와 우선순위 큐를 이용하는데, 검은 방에서 흰 방으로 바꾸는 횟수를 최소화해야 하므로 우선순위 큐의 첫번째 원소를 '지금까지 흰색으로 바꾼 검은 방의 갯수'로 지정해주면 됩니다. 이렇게 하는 이유는 매번 우선순위 큐에서 원소를 뽑을 때마다..
CS/Algorithm
[백준(파이썬/Python)] 4485_녹색 옷 입은 애가 젤다지? - 다익스트라
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 이차원 배열을 이용해야 하는 다익스트라 문제였고, 우선순위 큐를 활용해서 O(N^2*logN)의 시간복잡도 안에 해결할 수 있습니다. 많이 풀어봤던 노드와 간선 형태의 그래프 문제에서 상하좌우로 탐색해주는 부분만 조금 다르게 구현하면 어려운 부분은 없습니다. 추가적으로, 여러 개의 테스트 케이스에 대한 답을 연속해서 출력해야 하기 때문에 tc = 1로 초기화하고 출력을 할 때마다..
