어디까지 갈 수 있을까?

23. 국영수 www.acmicpc.net/problem/10825 1 2 3 4 5 6 7 8 9 10 11 12 import sys input=sys.stdin.readline arr=[] for _ in range(int(input())): a, b, c, d=input().split() arr.append([a, int(b), int(c), int(d)]) arr.sort(key=lambda x:(-x[1], x[2], -x[3], x[0])) for i in arr: print(i[0]) Colored by Color Scripter cs 24. 안테나 www.acmicpc.net/problem/18310 1 2 3 4 5 6 7 import sys input=sys.stdin.readline ..

알고리즘의 효율성을 표기해주는 표기법으로 데이터가 n개 주어졌을 때 연산의 횟수를 나타낸다 빅오 표기법은 알고리즘 최악의 경우 복잡도를 나타낸다 간단하게 이진탐색을 예로 들어보자. 주어진 데이터가 8개일 때 이진탐색은 8->4->2->1 이렇게 3번의 탐색을 진행해 최종적인 답을 찾아내게 된다 만약 주어진 데이터가 n개이고 x번의 탐색을 통해 1이 될 때 x는 어떻게 구할 수 있을까? 로 나타낼 수 있고 여기서 양변에 x를 구하기 위해 log(2)를 취하면 여기서 x를 구하기 위해 양변에 log2를 하면 탐색횟수 x를 구할 수 있다 O( 1) < O( log n)

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열한 것이다. 리스트의 .reverse()는 O(N)의 복잡도로 수행 가능하기 때문에 오름차순 코드만 다루기로 한다. 1. 선택정렬 정렬되지 않은 배열 중 가장 작은 값을 선택해 정렬한다 시간복잡도는 O(N^2) 이다 1 2 3 4 5 6 7 8 arr=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): min_index=i for j in range(i+1, len(arr)): if arr[min_index]>arr[j]: min_index=j arr[i], arr[min_index] = arr[min_index], arr[i] cs [0, 5, 9, 7, 3, 1, 6, 2, 4, 8] [0, 1, 9,..

15. 특정 거리의 도시 찾기 백준에도 같은 문제가 있다. 짠 코드를 채점해보자 www.acmicpc.net/problem/18352 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import sys from collections import deque input = sys.stdin.readline # 도시의 개수, 도로의 개수, 최단 거리, 출발 도시의 번호 # 도달 할 수 있는 도시가 없으면 -1 n, m, k, x = map(int, input().split()) visited = [0] * (n + 1) graph = [[] for _ in..

DFS - 재귀호출 - 백트래킹 - 조건 많은 그래프 BFS - 큐 - 최단 거리, 최소 비용 문제 - 모든 간선의 비용 1 DFS/BFS 둘 다 visited 배열 만들어서 방문처리를 해줘야 한다 반복문이 재귀함수보다 빠르게 동작하는 경우가 많기 때문에 DFS, BFS 둘 다로 구현 가능하면 BFS를 사용하는 게 낫다 1. 스택 선입후출 구조로 한쪽에서만 입력과 출력이 일어나기 때문에박스 쌓기에 비유된다 1 2 3 4 5 6 7 8 9 10 11 stack=[] stack.append(5) #5 stack.append(2) #5 2 stack.append(3) #5 2 3 stack.append(7) #5 2 3 7 stack.pop() #5 2 3 stack.append(1) #5 2 3 1 stac..

1. 모험가 길드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys input=sys.stdin.readline n=int(input()) arr=list(map(int, input().split())) arr.sort() result, count=0, 0 for i in range(len(arr)): count+=1 if count==arr[i]: count=0 result+=1 print(result) cs 2. 곱하기 혹은 더하기 1 2 3 4 5 6 7 8 9 10 11 12 import sys input=sys.stdin.readline n=input().strip() result=1 for i in n: if i=='0': continue result*=int..

책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현이라고 한다 완전 탐색은 모든 경우의 수를 모두 다 계산하는 법이고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 것이다. 1. 상하좌우 ① 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys input=sys.stdin.readline n=int(input()) arr=list(input().split()) x ,y=1, 1 for a in arr: past_x, past_y=x, y if a=='R': y+=1 elif a=='U': x-=1 elif a=='D': x+=1 elif a=='L': y-=1 if xn or yn: x, y = past_x, past_y..

문제링크 www.acmicpc.net/problem/2193 이게 왜 피보나치인 지 궁금해서 질문 게시판 보고 정리했다 [답코드] 1 2 3 4 5 6 7 8 9 import sys input=sys.stdin.readline n=int(input()) fib=[1, 1] for i in range(n-2): fib.append(fib[-1]+fib[-2]) print(fib[-1]) cs [풀이법] fib(n)=fib(n-1)+fib(n-2)가 나오는 이유는 ① 뒤에 0은 아무데나 붙을 수 있다 fib(n-1) 수열에 0을 붙이면 된다 ② 뒤에 1이 붙는 수열은 사실상 2자리가 고정돼있다고 생각해야한다. 1이 연속될 수 없으므로 fib(n-2)의 수에 01이 붙어 fib(n)을 구성한다고 생각해야 한다..