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로 초기화하고 출력을 할 때마다..
CS/Algorithm
[백준(파이썬/Python)] 1261_알고스팟
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net BFS와 우선순위큐(heapq)를 동시에 활용해서 푸는 문제입니다. 현재까지 부순 벽의 수를 count라는 변수에 저장하고, 상하좌우로 이동을 하며 벽이면 count+1, 벽이 아니면 count값을 그대로 우선순위 큐에 넣어주면 됩니다. 일반적인 bfs와는 다르게 우선순위 큐를 이용해야 하는 이유는 벽을 깨는 횟수를 "최소한"으로 하기 위해서인데, 다음 방문할 곳 중에서 벽이..
CS/Algorithm
[프로그래머스(파이썬/Python)] 상호 평가
https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 올 해 네이버 공채 코딩테스트에서 봤던 문제랑 똑같은 문제입니다. 프로그래머스에 네이버 문제도 오픈되는 것 같네요. 본론으로 들어가서, 이 문제는 당시 코딩테스트에서 1번 문제로 나왔을만큼 어렵지 않은 문제입니다. 다만, 이 문제에서 가장 중요한 포인트는 "문제를 잘 읽어야 한다"는 점입니다. 알고리즘..
CS/Algorithm
[백준(파이썬/Python)] 10830_행렬 제곱
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 거듭제곱의 연산 수가 100,000,000,000까지 갈 수 있기 때문에 일일이 계산하는 것은 불가능한 문제입니다. 따라서 분할 정복 개념을 바탕으로 거듭제곱근으로 나눠나가는 아이디어를 떠올려야 합니다. 예를 들어 A^100 = A^50 * A^50이고, A^5 = A^2 * A^2 * A처럼 차수를 2의 제곱근으로 떨어뜨릴 수 있는 것이죠. 한편, 행렬의 곱셈 연산은 multyplyMatrix(m1, m..
CS/Algorithm
[백준(파이썬/Python)] 5639_이진 검색 트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이 문제는 시간초과 때문에 고통받았던 문제입니다. 아래는 기존의 풀이이고 이렇게 하면 (전위순회를 통해 트리를 생성하는 시간) + (후위순회를 하는 시간(덤으로 재귀까지))때문에 시간초과가 발생합니다. 기본적인 트리 순회는 스택이나 재귀를 이용해서 하면 되지만 이 문제에서는 효율적인 탐색을 요구한 것이죠. // 시간초과 import sys sys.setrecursionlimit(10 ..
CS/Algorithm
[백준(파이썬/Python)] 1062_가르침
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 이 문제에서 'a','n','t','i','c'는 반드시 가르쳐야 하고, 모든 단어의 맨 처음 네 글자가 'anta', 'tica'라는 조건은 아마 시간 복잡도를 맞추기 위한 설정이거나 약간의 구현(?)을 유도하기 위한 것 같습니다. 하지만 기본적으로 단어의 개수나 알파벳의 수가 크지 않기 때문에 완전 탐색을 해야겠다는 생각을 할 수 있었고, 다만 조금이나마 효율적인 완전탐색을 하기 위한 ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 점프와 순간 이동
https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr Greedy하게 접근하면 쉽게 풀 수 있는 문제입니다. 아래 풀이의 주석에서 설명한 것처럼 (짝수번 째 칸 * 2)한 지점까지의 에너지 소모량은 0이고, 홀수 칸에서 짝수칸을 가기 위해서는 +1을 점프해주면 되기 때문에 이를 역으로 구현해주었습니다. ps. 처음에는 DP라고 생각해서 풀었는데, 정답은 맞지만 n이 1억 이하의 범위라서 DP..
