Algorithm
[BOJ] 백준 16929 Two dots - Python/Java
문제 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 해설 이 문제에서 정의하는 싸이클을 판단하는 기준은 여러가지가 있는 것 같습니다. 저같은 경우에는 [1] '시작 노드와 연결된 간선(최대 4개)에 대해 동일한 간선을 이용하지 않고 다시 시작 노드로 돌아올 수 있다면, 싸이클이 형성된다' 라고 생각했습니다. 그런데 다른 분들의 풀이를 보니 [2] '시작 노드에 대해서는 방문 체크를 하지 않은 채 DFS 탐색을 하다가, 그 경로의 길이..
Algorithm
[백준(파이썬/Python)] 4485_녹색 옷 입은 애가 젤다지? - 다익스트라
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 이차원 배열을 이용해야 하는 다익스트라 문제였고, 우선순위 큐를 활용해서 O(N^2*logN)의 시간복잡도 안에 해결할 수 있습니다. 많이 풀어봤던 노드와 간선 형태의 그래프 문제에서 상하좌우로 탐색해주는 부분만 조금 다르게 구현하면 어려운 부분은 없습니다. 추가적으로, 여러 개의 테스트 케이스에 대한 답을 연속해서 출력해야 하기 때문에 tc = 1로 초기화하고 출력을 할 때마다..
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)] 16198_에너지 모으기
https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 문제에서 N값이 10이하로 매우 작기 때문에, 재귀 함수를 통해 모든 경우의 수에 대한 완전 탐색을 해주면 됩니다. 완전 탐색을 하기 위해서는 현재 구슬 중에서 i번째 구슬을 선택했을 때 그 구슬을 제외한 리스트에서 다시 임의의 i번째를 선택하는 식으로 진행해야 합니다. 이를 위해 반복문 안에서 재귀함수를 호출하는 형식으로 구현했습니다. 문제에서는 copy 라이브러리를 이용하였는데, pop(..
