참고: https://youtu.be/atTzqxbt4DM 백트래킹 백트래킹? : 모든 경우의 수를 확인해야 할 때 사용하는 알고리즘 → for로는 확인이 불가능한 경우 (깊이가 달라질 때) 재귀함수 사용 재귀함수를 사용하여 1단계를 계속 돌면서 2단계에 진입, 2단계를 돌면서 만족하면 return 2단계가 모두 끝나면 1단계의 다음 단계 진입 계속 재귀적으로 반복하면서 만족하면 return 즉, 종료할 return 조건은 항상 코드 상단에 위치할 것 백트래킹 시간복잡도 N^N : 중복이 가능한 경우, N=8까지 가능 N! : 중복이 불가능한 경우, N=10까지 가능 ❗백트래킹 Tip 백트래킹 문제는 N이 작음 (N이 보통 10 언저리) 재귀함수 사용할 때, 종료 시점 잊지 않기! 백준 15649번 im..
참고: https://youtu.be/3_eVkTkBbJE DFS DFS? : Depth-first search (깊이 우선 탐색) Stack과 재귀로 구현할 수 있다. 시작점에 연결된 Vertex 찾기 연결된 Vertex를 계속해서 찾음 (끝날때까지) 더 이상 연결된 Vertex가 없을 경우 다음 이동 재귀함수란? 자기 자신을 다시 호출하는 함수 재귀 함수가 종료되는 시점 반드시 명시 (Infinity loop) 재귀 함수의 깊이가 너무 깊어지면 Stack Overflow DFS, 백트래킹에서 주로 사용 DFS 알고리즘 해결 방법 시간복잡도 O(V+E) 검색할 그래프 확인 방문여부 확인 (재방문 금지) Queue가 아닌 재귀 또는 Stack 활용 백준 2667번 - 단지번호붙이기 import sys s..
참고: https://youtu.be/ansd5B27uJM BFS 기초 그래프(Graph)? : Vertex(어떤것) + Edge(이어지는것) BFS : Breadth-firest search (너비 우선 탐색) 시작점에 연결된 Vertex 찾기 찾은 Vertex를 Queue에 저장 Queue의 가장 먼저 것을 뽑아 반복 BFS 알고리즘 해결 방법 시간복잡도 구하기 O(V+E) 검색할 그래프 확인하기 방문여부 확인하기(재방문 금지) Queue에 담아 BFS 실행 백준 1926번 - 그림 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) map = [list(map(int, i..
참고: https://www.acmicpc.net/problem/10866 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 해당 예제처럼 앞, 뒤로 넣고 빼는 자료구조를 할 수 있는 덱(deque)을 구현하는 문제인데 pop(0), pop() 등으로도 구현할 수 있지만 이전처럼 라이브러리에 있는 덱 함수를 사용해보면서 익히기로 했다. import sys from collections import deque input = sys.stdin.readline n = int(input()) result = deque([]) for _ in range(n): l = len(result) command = input().rstrip() if 'push_front' in command: text = command.spli..
참고: https://www.acmicpc.net/problem/10816 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 N개의 숫자카드가 주어진 것을 정리하여 다음 M개만큼 주어지는 숫자카드가 N개의 숫자카드와 일치하는 개수가 몇개인지 반환하는 문제이다. import sys from collections import Counter input = sys.stdin.readline n = int(input()) data = Counter(list(map(int, input().split()))) m = int(input()) card = list(map(int, input().split())) for i in card: if i in data: print(data.get(i), end=' ') else: pr..
참고: https://www.acmicpc.net/problem/2164 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 예를 들어서 1 2 3 4 5 6 이라는 카드가 있을 때, 1을 버리고 2는 맨뒤로 가서 3 4 5 6 2가 다음의 과정이 된다. 이것을 큐로 생각했을 때, 맨 앞에 오는 수를 버리고 다음 수는 임시로 저장해서 뒤로 추가하고, 앞에서는 버리는 그러한 과정을 구현할 수 있을 것으로 생각했다. import sys from collections import deque input = sys.stdin.readline card = deque(list(map(str, range(1, int(input())+1)))) while len(card) > 1: card.popleft() x = card[0]..
