어디까지 갈 수 있을까?

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

[해결방법] invalid literal for int() with base 10: '\n' 오류 메시지가 난다면 1 2 3 4 import sys input=sys.stdin.readline a=input().rstrip() cs 이와 같이 끝에 rstrip()를 붙여주면 된다 [이유] 1 2 3 4 5 6 import sys input=sys.stdin.readline a=input() print(a) print('b') cs 프로그램을 돌리면 위와 같이 enter가 한 번 더 추가적으로 들어간다 그 이유는 sys.stdin.readline은 우리가 입력한 값을 모두 받기 때문에 문자열에 끝에 입력한 개행문자 (\n)도 같이 받는다. 이 때문에 끝에 rstrip()를 붙여주면 개행문자가 제거돼 정상적..

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)을 구성한다고 생각해야 한다..

문제링크 www.acmicpc.net/problem/1783 [읽기 전에] ① 나이트가 이런식으로 이동했다면 3칸 방문한 것이다. ② 1, 2, 3, 4 이동 방법을 모두 한 번 씩 사용하고 난 후에는 1, 2, 3, 4 아무거나 사용해서 움직여도 가능하다 이동횟수가 4회째 되는 파란 화살표 이후 부분은 1, 4만 계속 이용해서 움직여도 무방하다 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys input=sys.stdin.readline n, m=map(int, input().split()) #for문 안 써도 됨 if n==1: print(1) elif n==2: print(min(4, (m + 1) // 2)) else: if m