코딩 테스트 문제가 어려워짐에 따라 블로그 정리까지 하기에는 너무 시간이 많이 잡아먹는거 같아 앞으로는 주석으로 세세하게 정리하는 방식으로 가려고 합니다(시간이 여유로워지면 다시 정리할겁니다). 아래는 저희 스터디가 사용하는 깃허브 링크 입니다. 2wnsqo 아이디의 코드와 주석을 봐주시면 감사할거 같습니다.
# 35004KB 388ms import sys from collections import deque
N, M, V = map(int, sys.stdin.readline().strip().split(' ')) graph = {} for _ in range(M): a, b = map(int, sys.stdin.readline().strip().split(' ')) if a not in list(graph.keys()): graph[a] = [b] else: graph[a].append(b)
# 양방향 그래프 구현현 if b not in list(graph.keys()): graph[b] = [a] else: graph[b].append(a) visited = [False] * (N + 1) list1 = [] # print(graph) # print("------------------------------") # 너비우선 def dfs(graph, start, visited): visited[start] = True print(start, end=' ') if start in list(graph.keys()): list1 = graph[start] list1.sort() for i in list1: if visited[i] == False: dfs(graph, i, visited)
while queue: a = queue.popleft() if visited[a] == False: visited[a] = True print(a, end=' ') if a in list(graph.keys()): listt = graph[a] listt.sort() queue.extend(listt) bfs(graph,V,visited2)
BFS는 Breadth-First Search 로 너비를 우선적으로 탐색하는 방식입니다.
반면 DFS는 Depth-First Search 로 깊이를 우선적으로 탐색하는 방식입니다.
매우 중요한 내용이므로 무슨 방식이고 어떤 코드로 구현 할 수 있는지 아는게 중요한거 같습니다.
위 코드는 계단오르기 문제(백준 2579)문제를 탑다운 방식의 dp(동적 계획법) 방법으로 푼 코드 입니다.
처음계단 밟았을때 (1칸오르기)와 두번째 계단 밟았을때(1칸 1칸오르기)를 초기 값으로 주고 각 계단을 밟을 때의 값을 2칸전에서 2칸올라 이번 계단을 밟을때, 3칸전에서 2칸 1칸 올라 이번계단을 밟을때의 큰 값으로 주는 방식입니다. 여기서 중요한 점은 이번 계단을 밟는 경우의 수를 2개만 계산 한 이유는 1칸 1칸 1칸 연속으로 밟을 수 없어 (2칸 1칸 1칸) (2칸) 만 계산 하면 다 계산 됩니다. 시작이 무조건 2칸으로 시작하면 저번 마지막 오른 계단의 수는 고려하지 않아도 됩니다. 시작이 2칸인 경우는 (2칸 1칸 1칸) (2칸)만 고려하면 됩니다.
그러하고 n == 0 즉 시작지점과 dp_max[n] 이 0이 아닌경우(계산이 된 경우)는 return하여 아래에서부터 채워져 최종 결과를 return합니다.
탑다운 방식에서는 재귀를 사용하여 문제를 풀고, 이미 계산된 값을 메모이제이션(memoization) 기법을 통해 저장해두고 재사용합니다.
위 코드는 평범한 배낭 문제(백준 12865)문제를 바텀업 방식의 dp(동적 계획법) 방법으로 푼 코드 입니다.
물건의 수 n과 배낭의 용량 k, 각 물건의 무게 w와 가치 v를 받습니다. 물건의 무게와 가치는 items 라는 리스트 안에 튜플로 저장합니다. 그 후 아이템을 하나씩 꺼내 for문을 돌리게 됩니다. 그 후 무게를 역순으로 하여 최대 값을 계산합니다.
역순으로 계산한다는 점이 중요한 포인트 입니다.!
위 정리와 같이 역순으로 하지 않으면 같은 아이템을 여러번 고를 수 있게 됩니다. 처음에는 정순으로 계산하고 뽑은 아이템의 인덱스를 리스트에 담아 그 인덱스가 있으면 집지 않는 식으로 하였지만 결국 실패 하였습니다. 위 표와 같이 역순으로 계산하면 dp[6], dp[4], dp[2] 모두 10이라는 값으로 들어가게 됩니다. 그 후 다른 아이템을 집음으로써 최대 값을 계산하게 됩니다. 또한 아이템을 무게 7을 먼저 집어서 3과 4를 집은걸 계산하지 못하는것도 아닙니다. 나중에 다시 계산되어 큰 값으로 들어가기 때문입니다.
이번 문제는 계단 오르기와 다르게 함수 한번 사용으로 bag_max 리스트의 값을 모두 각 무게의 최대 가치로 채운 후 bag_max[k]의 값을 출력하는 방식입니다.
바텀업 방식의 dp문제는 재귀를 사용하지 않고 반복문을 통해 max_bag 배열을 갱신하는 방식입니다.
3. LCS(백준 9251)
LCS문제는 단어수*단어수로 2차원 배열을 만든 후 각 칸의 최대 값을 채워 나가는 방식으로 풀었습니다. 첫 세로줄과 가로줄은 처음 단어 기준으로 단어가 나오기 전에는 0 나온 후에는 1로 채우고 시작합니다. 그 후 각 칸은 인덱스에 맞는 단어들이 같으면 대각선 값에서 +1 다르면 위와 왼쪽값중 max값을 택합니다. 그렇게 끝까지 채운후 마지막 값을 출력하면 됩니다.
제가 원래는 인덱스의 단어들이 같으면 위와 왼쪽 값의 max에 +1인줄 알았으나 이방법은 비교단어가 2개인데 3이상의 값이 나올수 있다는 점을 알았습니다. 대각선에서 +1 하는 이유는 원래 벼엘에서 단어가 동시에 추가되었을때 같으면 +1 이기 때문입니다. 또한 2차원 배열이 아닌 1차원 배열로 계속 초기화 및 갱신하면서 하는 방법도 있다고 합니다.
위 코드와 같이 a, b =b, a 식으로 a와 b의 값을 바꿀 수 있습니다. temp와 같은 변수를 따로 만들어 담지 않아도 되어 편할거 같습니다. 하지만 문자열에서는 불가능 합니다.
4. range()
range(start, stop, step) 구조에 step 에 음수를 주면 값이 적어지게 됩니다. stop은 미만이므로 -1을 주면 0까지만 가게 됩니다. 즉 i-1부터 0까지 거꾸로 가게 됩니다.
5. for~else
파이썬에만 있는 문법으로 for 문이 break로 끝나지 않을때만 실행하는 코드입니다.
6. extend
extend는 append와 비슷하게 리스트 뒤에 값을 추가하는 기능을 하지만 리스트를 append하면 리스트인 상태로 추가 되지만 extend는 한펀 풀어서 추가하게 됩니다. 즉 1차원 리스트를 extend하면 시퀀스로 들어가지고 2차원 리스트를 extend하면 1차원 리스트가 들어갑니다.
sys 라이브러리의 sys.stdin.readline().strip()을 통해서 한줄한줄 입력을 받아 올 수 있습니다. input()보다 실행시간이 빨라 시간제한이 있는 코딩테스트 문제에선 꼭 사용애햐 하는거 같습니다.
strip() 을 하는 이유는 입력받을때 '\n'인 개행문자를 같이 받기 때문에 한줄씩 받으려면 사용해줘야 합니다.
strip()은 불피요한 개행문자와 공백문자를 제거해줍니다.
2. pop()
pop()을 하면 리스트기준 제일 뒤에 있는 데이터를 뽑아 리턴합니다. 하지만 pop(0)와 같이 인덱스를 넣어주면 리스트 처음 데이터를 뽑아 리턴합니다.
3. heapq 라이브러리(최소 힙 라이브러리)
3-1. 최소 힙
import heapq를 하면 사용할 수 있으며 값이 작은 값부터 처리하기 위해 사용하는 라이브러리 입니다.
위 사진과 같이 함수를 사용하면 손 쉽게 최소 힙을 구현할 수 있습니다.
3-2. 최대 힙
위 코드와 같이 사용한다면 최대 힙 또한 구현할 수 있습니다. 원하는 데이터에 음수를 적용하여 삽입후 반환 할 때는 음수를 적용하여 원상태로 반환 할 수 있습니다.
4. sort()
위 코드와 같이 sort() 함수의 key 옵션을 주어서 원하는 형식으로 정렬 할 수 있습니다. 또한 정렬의 1순위 2순위 같이 여러개 적용도 가능합니다.
5. print()함수 내 언패킹
print 함수 내 *xy 언패킹하여 print문 조금 사용하는 방식입니다. 하지만 둘다 O(n) 방식이여서 실행 시간은 별로 차이나지 않지만 print문 반복사용으로 인한 오버헤드가 발생할 수 있어 알아두면 좋을거 같습니다.
6. 최대공약수 최소공배수
최대공약수는 math.gcd(a, b)로 쉽게 구할 수 있으며 최소공배수는 a*b/ 최대공약수 로 쉽게 구할 수 있습니다.
a*b/최대공약수는 유클리드 알고리즘입니다.
(for문으로 풀려고 고생하다 좋은 정보를 알았습니다)
7. deque 라이브러
from collections import deque 을 한 후 사영할 수 있으며 사용 가능한 함수는 다음과 같습니다.
위 사진과 같이 사용할 수 있습니다.
큐와 덱 문제는 위 라이브러이의 함수로 쉽게 풀 수 있다는 사실을 다 풀고 알았습니다.
7-1 헷갈릴만한 함수
extendleft 함수는 원하는 데이터를 왼쪽에서부터 반대로 삽입 합니다.
rotate 함수는 원하는 방향으로 미는 함수입니다. 양수는 오른쪽으로 음수는 왼쪽으로 밉니다.
8. print() 함수 문자열 포매팅과 리스트 처리
[1, 2, 3, 5, 8] 이런식의 출력을 공백 없이 [1,2,3,5,8]로 출력하는 방법입니다. deque 타입에 정수가 들어있는 number데이터에 map함수를 적용해 str문자열로 변경시킨 후 ,f로 조인을 합니다. 그러하면 1,2,3,5,8이 나옵니다. 그 후 f-string 으로 밖에 []대괄호를 씌우는 방법입니다.
9. json 함수
import json으로 사용할 수 있으며 문자열인 '[1,2,3,4]'를 [1, 2, 3, 4] 로 변환 하는 json.loads함수가 있습니다. json 형태의 문자열을 파이썬 객체로 변환합니다. 입력 형태에 맞게끔 반환 해줍니다. (dict 형식을 넣으면 dict형식으로 나옵니다)
반대로 dumps를 하면 파이썬 객체를 json형식으로 변경해줍니다.
10. 소수 찾기
위 코드는 자연수 a와 b가 주어지면 그 사이에 존재하는 모든 소수를 출력하는 문제입니다.
저 코드에서 중요한 점은 두번째 for문에 범위를 math.sqrt(i)+1 로 주었다는 점입니다. 소수가 아닌 숫자는 1과 자신이 아닌 수로 나누어지는 수가 있는 수입니다. 예를 들어 8은 2*4, 4*2 로 나누어 집니다. 여기서 요점은 사실 2*4가 가능하면 4*2는 당연히 가능하다는 것입니다. 이를 이용해 판별하는 수에 루트를 씌어(math.sqrt) 숫자에 절반만 판단해도 된가는 점이지요. 이렇게 실행시간을 대폭 단축 시킬 수 있습니다(저 방식을 사용하지 않으면 시간 초과가 나옵니다).
또한 1은 모든 숫자를 나눌 수 있어 a가 1이면 2부터 시작하게 +1 해주었습니다. 이 방식이 싫다면 마지막 print()문의 if 조건에 and i != 1 을 추가해도 됩니다. 하지만 이 방법보단 위 코드 방법이 실행시간이 미세하게 빨랐습니다.
11. 튜플 언팩킹 결과
result 는 튜플이 들어있는 리스트 입니다. 즉 [(1,2),(1,3)] 이런식으로 들어있습니다. 그중 for문으로 한줄씩 가져오면 r은 (1,2)와 같은 튜플이 가져와 집니다. 이것을 언패킹을 하여 print()하면 1 2와 같은 식으로 출력 됩니다.
12. itertools 라이브러리(중요!)
from itertools import * 로 사용할 수 있습니다. 여러 경우의 수와 수열을 구할때 매우 유요하여 코딩테스트에 많이 나온다고 합니다. 함수는 다음과 같습니다.
