DFS

124 나라의 숫자 (3진수, 0이 없을 때, 재귀)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 EX) 9는 124나라에서 24 3진법 계산 9 ÷ 3 = 3 ⋯ 0 3 ÷ 3 = 0 ⋯ 0 124나라 계산 9 ÷ 3 = 3 ⋯ 0 ➔ 0은 4로 치환, 몫에 -1을 빼서 재귀 2 ÷ 3 = 0 ⋯ 2 풀이 answer = '' def solution(n): def DFS(x): global answer if x == 0: return else: if x%3==0: DFS((x-1)//3) answer+='4' else: DFS(x//3) answer+=str(x%3) DFS(n) return ans..

여행경로 (DFS, 모든 경로 사용해서 모든 노드 방문)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 무조건 알파벳 순서가 앞서는 곳을 향하도록 여행 경로를 구성하면 문제의 답을 올바르게 구할 수 있음을 보장하지 않음 ticket result [["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]] ["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"] 위 예시에서 처음에 "ICN"에서 출발하여 "AAA"를 먼저 방..

[1068] 트리 (리프 노드의 개수 구하기, DFS)

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline n=int(input()) parent=list(map(int, input().split())) deleteNode=int(input()) tree = [[] for _ in range(n)] root=0 for i in range(n): if parent[i]!=-1: tree[parent[i]].append(i) tree[i].append..

[11725] 트리의 부모 찾기 (DFS)

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net """ 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. """ import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline n=int(input()) tree = [[] f..

동전 문제 유형 정리 (greedy, DFS, DP)

1. 여러 단위 동전, 무수히 많을 때, 교환 최소 개수 출력 2023.04.27 - [Algorithm PS/Search] - 동전 교환(DFS) 2023.05.19 - [Algorithm PS/DP] - 동전 교환 (DP) 2023.06.01 - [Algorithm PS/DP] - [2294] 동전 2 (동전 개수 최소값) 2.여러 단위 동전, 무수히 많을 때, 교환 방법 경우의 수 출력 2023.06.01 - [Algorithm PS/DP] - [2293] 동전 1 (경우의 수 구하기) 3.여러 단위 동전, 정해진 갯수, 교환 방법 경우의 수 출력 2023.05.03 - [Algorithm PS/Search] - 동전 바꿔주기 (DFS) 2023.05.03 - [Algorithm PS/DP] - [..

알리바바와 40인의 도둑 (Bottom-Up, Top-Down)

bottom up """ 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1,1)격자에서 (N,N)까지 가는데 드는 에너지의 최소량 만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면 3 2 5 2 3 4 6 5 2 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. 5 3 7 2 1 9 5 8 3 9 2 5 3 1 2 3 5 4 3 2 1 1 7 5 ..