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와 우선순위 큐를 이용하는데, 검은 방에서 흰 방으로 바꾸는 횟수를 최소화해야 하므로 우선순위 큐의 첫번째 원소를 '지금까지 흰색으로 바꾼 검은 방의 갯수'로 지정해주면 됩니다. 이렇게 하는 이유는 매번 우선순위 큐에서 원소를 뽑을 때마다..
Algorithm
[백준(파이썬/Python)] 4485_녹색 옷 입은 애가 젤다지? - 다익스트라
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 이차원 배열을 이용해야 하는 다익스트라 문제였고, 우선순위 큐를 활용해서 O(N^2*logN)의 시간복잡도 안에 해결할 수 있습니다. 많이 풀어봤던 노드와 간선 형태의 그래프 문제에서 상하좌우로 탐색해주는 부분만 조금 다르게 구현하면 어려운 부분은 없습니다. 추가적으로, 여러 개의 테스트 케이스에 대한 답을 연속해서 출력해야 하기 때문에 tc = 1로 초기화하고 출력을 할 때마다..
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와는 다르게 우선순위 큐를 이용해야 하는 이유는 벽을 깨는 횟수를 "최소한"으로 하기 위해서인데, 다음 방문할 곳 중에서 벽이..
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번 문제로 나왔을만큼 어렵지 않은 문제입니다. 다만, 이 문제에서 가장 중요한 포인트는 "문제를 잘 읽어야 한다"는 점입니다. 알고리즘..
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..
Algorithm
[백준(파이썬/Python)] 5639_이진 검색 트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이 문제는 시간초과 때문에 고통받았던 문제입니다. 아래는 기존의 풀이이고 이렇게 하면 (전위순회를 통해 트리를 생성하는 시간) + (후위순회를 하는 시간(덤으로 재귀까지))때문에 시간초과가 발생합니다. 기본적인 트리 순회는 스택이나 재귀를 이용해서 하면 되지만 이 문제에서는 효율적인 탐색을 요구한 것이죠. // 시간초과 import sys sys.setrecursionlimit(10 ..
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'라는 조건은 아마 시간 복잡도를 맞추기 위한 설정이거나 약간의 구현(?)을 유도하기 위한 것 같습니다. 하지만 기본적으로 단어의 개수나 알파벳의 수가 크지 않기 때문에 완전 탐색을 해야겠다는 생각을 할 수 있었고, 다만 조금이나마 효율적인 완전탐색을 하기 위한 ..
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..
Algorithm
[백준(파이썬/Python)] 2638_치즈
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제의 핵심은 내부 치즈인가 아닌가를 어떤 방식으로 판단할 것인가입니다. 처음 문제에 접근했을 때는"모든 지점에 대하여 내부 치즈인가를 BFS 탐색을 하였고, 만약 가장자리에 도착할 수 있으면 내부 치즈가 아니다"라고 생각했습니다. 하지만 그렇게 되면 모든 위치마다 일일이 체크를 해줘야 하기 때문에, 시간복잡도에서 불리할 수밖에 없습니다. 이를 해결하기 위해서는 반대로 "가장 자리..
Algorithm
[백준(파이썬/Python)] 2096_내려가기
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net - 풀이 자체는 어렵지 않은데 문제의 메모리 제한이 상당히 타이트합니다. - 현재 계단에서 점수의 최대, 최소는 그 전 계단까지의 최대 최소에만 영향을 받기 때문에 모든 계단의 점수값을 미리 배열로 만들어두면 메모리 초과가 발생합니다. - 따라서, 계속해서 각 시점에서 인풋값을 읽고 최적해를 갱신해나가는 방향으로 문제를 풀어야합니다. 문제 풀이의 DP 로직은 첫번째, 두번째, 세번째 계단에 있을 때를 따로 생각..
