Coding Test/Baekjoon

https://www.acmicpc.net/problem/2637✔ 유형 : 위상 정렬✔ 문제 풀이:  위상 정렬을 이용한 최단거리느낌? 뭐라고해야하지ㅜㅜ 백준 Test Case를 분석해봤을 떄, ⬇️코드import sysfrom collections import deque input = sys.stdin.readlineN = int(input())M = int(input())Graph = { i : {} for i in range(1, N+1)} # 이중 딕셔너리!need = [0 for _ in range(N+1)] # indegree 개수를 센 리스트indegree = [0 for _ in range(N+1)]for i in range(M): X, Y, K = map(int, input().s..

https://www.acmicpc.net/problem/1707 ✔ 유형 : DFS✔ 문제 풀이: 이분 그래프의 특징을 이용해 DFS로 탐색해 나가며 조건에 위배 될 경우 탐색을 종료시킨다.- 방문하지 않은 노드를 탐색하려고 할 때 현재 노드와 다른 색으로 visited 배열에 저장을하고- 방문 했던 노드를 탐색하려고 할 때는, 자신과 같고 이어져 있다면 이분 그래프가 아니므로 탐색을 종료한다.  ✨ 주의 할 점1. 재귀를 쓰면 시간 초과가 날 수 있다.2. 모든 그래프가 연결 되어 있다는 보장이 없기 때문에, 전체 노드를 for문으로 탐색해야한다.  import sysfrom collections import defaultdictinput=sys.stdin.readline # input함수 바꾸기sy..

https://www.acmicpc.net/problem/11725 ✔ 유형 : DFS✔ 문제 풀이: 해당 노드와 연결된 노드들의 부모는 해당 노드라는 점을 이용해 배열에 자신의 부모 노드 번호를 저장한다. 백준의 테스트 케이스를 예시로 들어 설명하자면, 위와 같은 방법으로 계속 DFS를 돌리면 아래와 같이 부모 리스트가 채워진다.  ⬇️문제import sysinput=sys.stdin.readline # input함수 바꾸기sys.setrecursionlimit(10**5)# input N = int(input())Graph = {i: [] for i in range(1, N+1)}for i in range(N-1): u, v = map(int, input().split()) Grap..

https://www.acmicpc.net/problem/1197✔ 유형 : 최소 신장 트리, 크루스칼 알고리즘, union find✔ 문제 풀이: union find 알고리즘을 이용하여 거리가 최소인 간선과 정점을 선택하여 V-1개의 간선을 가진 부분 그래프를 만든다.  ⬇️코드 import sysinput=sys.stdin.readline # input함수 바꾸기# union find algorithmdef find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x]def union(parent,a,b): a = find_parent(par..

https://www.acmicpc.net/problem/5639✔ 유형 : 재귀✔ 문제 풀이: 이진 검색 트리의 특징과 전위 순회를 했을 때의 배열의 규칙을 찾아 범위를 줄여나가 탐색하며 오른쪽 서브트리와 왼쪽 서브트리를 구분해서 문제를 푼다.  해당 노드보다 큰 원소가 나올 때까지 탐색한다.큰 원소가 나오면 오른쪽 서브트리를 의미하고 큰 원소의 인덱스부터 오른쪽 서브트리.해당 노드 인덱스 + 1 부터 큰 원소의 인덱스 -1 까지는 왼쪽 서브트리임을 알 수 있다.  이제부터 위의 규칙을 이용해 재귀를 돌린다. 재귀를 계속 돌리면 결국 리프 노드까지 탐색이 완료되고, 같은 방법으로 왼,오 노드를 구분하여후위 순회의 순서대로 print를 해주면 된다.  ⬇️ 코드import sysinput=sys.stdi..

https://www.acmicpc.net/problem/2630✔ 유형 : 이분 탐색✔ 문제 풀이: 큰 문제를 작은 문제로 분할하여 작은 문제부터 순차적으로 해결한 뒤 결과를 합한다.  탐색할 영역의 제일 왼쪽 위의 색을 저장해두고, 이중 for문으로 다른 색이 포함되어 있는지 확인한다.만약 다른 색이 포함되어있다면 각 면을 N/2로 나눠서 총 4 부분으로 나눈다.계속 나누다가 언젠간 한면이 1이되면 해당 색을 배열에 저장한다. 만약 한 구역을 검사했는데 모두 같은 색이라면 해당 색을 배열에 저장한 후 함수를 리턴한다. 위의 방법을 아래의 코드로 나타내었다. import sysinput=sys.stdin.readline # input함수 바꾸기import copy#inputN = int(input())..

https://www.acmicpc.net/problem/2805✔ 유형 : 이분 탐색✔ 문제 풀이: 리스트 양쪽에 start와 end 피벗을 두고 범위를 좁혀가며 답을 찾는다.   #2850 나무자르기#이분 탐색import sysinput=sys.stdin.readline # input함수 바꾸기N, M = map(int, input().split())trees = list(map(int, input().split(' ')))st, en = 0, max(trees) # 최소 최대값!while st mid: #톱날보다 긴 나무들만. count += tree - mid # 톱날h만큼 자른다 if count >= M: # 구하려는 나무길이보다 크면 더 잘라야하므로 s..

https://www.acmicpc.net/problem/3190 ✔ 유형 : 큐✔ 문제 풀이: 뱀이 지나가는 맵의 좌표를 큐를 이용한다. ✨Key Point1. 뱀의 이동 좌표 2. 회전 3. 게임 종료 조건   (1) 위치가 index 범위 밖일 떄   (2) 스스로 부딪혔을 때 →  map[][] 2차원 배열에 현재 맵상태를 기록해두고 확인한다.ex ) 0 일경우 빈 맵, 1일경우 뱀이 위치해있음. 2일경우 사과가 있음. 코드import sysimport collections input=sys.stdin.readline # input함수 바꾸기dequeu = collections.deque#inputN = int(input()) # 보드의 크기K = int(input()) # 사과의 개수#사과의 위..

https://www.acmicpc.net/problem/2493 ✔ 유형 : 스택✔ 문제 풀이: 반복문으로 검사하면 최악의 경우 O(N^2)의 시간복잡도가 나온다. 이를 해결하기 위해 stack을 이용한다. 구해야 하는 답: 각 탑에서 발사한 레이저 신호를 수신한 탑의 번호 리스트.  코드import sysinput=sys.stdin.readline # input함수 바꾸기# inputN = int(input())towers = list(map(int,input().split())) #list 자료구조지만 스택 사용 가능stack = list()answer = [0 for i in range(N)]# 2. for i in range(N): # 1. 현재 스택에 값이 존재한다면? while(s..

https://www.acmicpc.net/problem/11866✔ 유형 : 큐✔ 문제 풀이: 큐의 성질 이용. push, pop import sysimport collectionsinput=sys.stdin.readline # input함수 바꾸기size, gap = map(int, input().split())q = collections.deque()for i in range(1,size+1): q.append(i) result = list()i = 0while(len(result) ') break if idx==0: print('') else: print(result[idx], end=', ')

https://www.acmicpc.net/problem/2468✔ 유형 : 완전 탐색✔ 문제 풀이: BFS

https://www.acmicpc.net/problem/10971✔ 유형 : 완전 탐색✔ 문제 풀이:  # 외판원 순환# 입력N = int(input())W=[[*map(int,input().split())] for _ in range(N)] # 정리 해두기 N행 배열 입력 받는 법min_cost = 1e9visited = [False for _ in range(N)] # 방문 여부temp = list()def go(depth, cost)->int: global min_cost if(cost >= min_cost) : return if( depth == N ): if W[temp[N-1]][temp[0]] == 0 : return #print(f..