https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 이 문제의 시간 복잡도는 n^2? for 문이랑 while문이 들어가니 그렇게 생각한다 import sys from collections import deque sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] ..

https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 시간 복잡도는 N^2 이라 생각한다. 아닌가? N 인가? import sys sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] for i in range(n + 1)] visited = [False] * (n + ..

문제 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 시간 복잡도 시간 복잡도는 재귀를 써서? 잘 모르겠지만 n^2 일거 같다. 코드 import sys sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] for i in range(n + 1)] visited =..

https://programmers.co.kr/learn/courses/30/lessons/12981?language=python3 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr def solution(n, words): answer..

https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 나는 문제 보자마자... 백트레킹이다 하고 접근했는데.... 이게 다이나믹 이었다... 하하 오랜만에 푸는 문제라 감각이 많이 떨어졌다. 하하 다시 하루 생각해봤는데 전형적인 메모제이션이다! dp의 유형은 문제를 잘게 조깨는게 중요하다. 아래의 문제를 잘 해석해보자 중요한 부분은 def solution(n..

https://programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 오랜만에 알고리즘 문제이다. 수학적인 문제인데 나는 정말 어려웠다. 하하... def solution(n): answer = [] snail = [[0]*n for i in range(n)] x,y = -1,0 num = 1 for i in range(n): for j in range(i,n): if i % 3 ==0: x += 1 elif i % 3 == 1: y +..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net import sys from collections import deque m, n, k = map(int,sys.stdin.readline().split()) graph = [[0]*n for i in range(m)] for _ in range(k): x1,y1,x2,y2 = map(int,sys.stdin.readline().split()) for i in range(y1,..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net import sys from collections import deque n, m = map(int,sys.stdin.readline().split()) graph = [[] for i in range(n+1)] for i in range(m): a, b = map(int, sys.stdin.readline().split()) grap..