KEEP GOING

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제의 경우 대표적으로 DFS를 사용하여 순열을 구하는 문제입니다. DFS를 사용하여 조합을 구하는 문제가 궁금하다면 아래 링크를 참고하시면 됩니다. https://dogsavestheworld.tistory.com/269 [python] 백준 15650번 : N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 삼성 코딩테스트 같은 경우, itertools 모듈을 사용할 수 없습니다. 그래서 permutations(순열)이나 combinations(조합) 같은 기능을 사용하지 못하는데, 이를 대비하기 위해 DFS를 이용하여 조합을 구할 수 있는 대표적인 문제입니다. [dfs] def dfs(arr, idx): if len(arr) == M: print(*arr) return for i in range(..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제의 경우, 벽을 부술 수 있는 기회 한 번이 주어진다. 테스트 케이스로 주어지지 않았지만 0,0 좌표에서 n-1,m-1 좌표까지 갈 때 벽을 부수지 않고 이동하는 최단 경로도 있다. 나는 벽인 좌표들을 walls라는 배열에 넣어 벽을 하나씩 부숴가며 bfs를 돌려주었다. 하지만 한 번도 벽을 부수지 않고 이동하는 경우에 대해서는 검사하지 않았다. 따라서 벽을 부수는..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 우선 1부터 N까지 구성된 수열을 복구하기 위해서는 N보다 큰 숫자는 제외하고 N까지만 찾아야 하기 때문에 N이 무엇일지 알아야 한다. N은 주어진 문자열 kriii = '4111109876532' 의 길이를 통해 찾을 수 있다. 문자열의 길이가 10보다 작은 경우 N = len(krii) 문자열의 길이가 10보다 클 경우 N = 9 + (len(krii)-9)//2 예를들어,..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 맥주는 총 20병이 있고 50미터에 1병씩 맥주를 까서 마신다. 즉, 시작 지점(상근이네 집)과 도착지점(맥주 페스티벌)의 거리가 1000미터 이내이면 행복하게 한잔씩 까면서 무사히 도착할 수 있다. - 상근이네 집과 페스티벌 장소까지의 거리가 1000m 이내이면 : True - 1000m이내가 아닐 경우 편의점에 들리면 맥주가 다시 20병까지 채워진다. 즉 상근이네 집부터 편의점까지 거리가..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 그래프 탐색 문제이다. 1번 컴퓨터를 통해 웜 바이러스에 걸릴 컴퓨터의 개수를 구하라고 문제에서 제시해 주었다. 즉, 1번 노드와 연결된 노드의 개수를 구하면 된다. 따라서 DFS로도 BFS로도 구현할 수 있는 문제이다. * 문제에서 연결된 컴퓨터의 정보를 제시할 때 언제가 1번부터 등장한다는 언급이 없다. 따라서 6 5 6 5 5 4 4 3 3 2 2 1 다음과 같은 input 값이 주어진 경우에는 ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 정답 코드) def dfs(r, c, idx, total): global ans if ans >= total + max_val * (3 - idx): return if idx == 3: ans = max(ans, total) return else: for nr, nc in move: nr += r; nc += c if 0

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 구현 from collections import deque n = int(input()) bridge = [list(map(int, input().split())) for _ in range(n)] last_x, last_y = 0, 0 for i in range(n): for j in range(n): if bridge[i][j] == 1: last_x, last_y = i, j move = [..