어디까지 갈 수 있을까?

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열한 것이다. 리스트의 .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..

현재 상황에서 지금 당장 좋은 것만 거르는 방법 문제 상에 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준 제시 1. 거스름돈 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys input=sys.stdin.readline n=int(input()) coin=[500, 100, 50, 10] result=0 for c in coin: if n==0: break result+=n//c n%=c print(result) cs 2. 큰 수의 법칙 입력 예시 5 8 3 2 4 5 4 ..