요새 파이썬을 이용해서 코딩테스트 준비를 다시 시작하려고 하는데 파이썬을 이용하기와 더불어서 알고리즘의 종류가 어떤 것들이 있고, 어떤 분류를 통해 문제에 접근해야할지 처음부터 정리를 해보고자 한다. 이에 따라 '이것이 코딩테스트다 with 파이썬'책과 함께 기록해둔 내용을 velog에 정리해보고자 한다!!
빠르게 내용만 정리해서 머릿속에 담아두고 파이썬을 이용한 문제를 풀어보면서 velog에 문제와 함께 풀이를 업로드 해볼 예정이다!!
참고 강의 링크! 👉 https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만을 고르는 방법
→ 문제를 풀기위한 최소한의 아이디어를 떠올리도록 하기
ex) 루트 노드 부터 시작해서 거쳐가는 노드 값의 합을 최대로 만들기
일반적 상황에서 최적의 해를 보장할 수 없을 때가 많음
그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있도록 풀이!!
거스름 돈 문제
→ 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 최적의 해를 보장 가능
시간 복잡도는 O(K) 동전의 총 종류에만 영향
1이 될 때까지
주어진 N에 대하여 최대한 많이 나누기를 수행 (K에 대해서 나누고 안되면 1빼기)
K가 2이상이면 1을 빼는 것 보다 항상 빠르게 N을 줄일 수 있기 때문에
target = (n // k) * k
곱하기 혹은 더하기
+보다 X 가 더 값을 크게 대개 만들기 때문에 x를 이용하였을 때 더 큰 부분을 채택
int(input)
# 두 수 중 하나라도 0 혹은 1이면 곱하기보다 더하기 수행하기
if num <= or result <= 1 :
result += num
else :
result *= num
모험가 길드
공포도를 하나씩 확인해서 오름차 순으로 정렬해보기
현재 그룹에 포함된 모험가 수가 현재 확인하는 공포도 보다 크거나 같으면 그룹 결성
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0
count = 0
for i in data :
count +=1
if count >= i :
result += 1
count = 0
print(result)
구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
<예시>
일반적으로 알고리즘 문제는 2차원 공간, 행렬의 의미로 사용됨
for i in range(5):
for j in range(5):
시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터 자주 활용
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
x, y = 2, 2 # 현재 위치
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
상하좌우 문제
요구사항대로 충실히 구현
시뮬레이션 유형
*시뮬레이션 구현 완전 탐색은 비슷한 유형으로 생각하기
방향 벡터를 활용하여 이동 계획을 하나씩 확인해보기
시각
모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수 구하기 ex ) 00시 00분 03초, 00시 13분 30초
하나씩 일일히 다 세서 푸는 문제 → 완전 탐색(Brute Force) 떠올리기
24 60 60 = 86,400
파이썬을 이용하면 1초에 약 20,000,000개의 연산을 수행할 수 있다고 염두하고 계산해보기!!
h = int(input())
count = 0
for i in range(h+1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
count += 1
왕실의 나이트
요구사항 충실히 구현하기
나이트의 8가지 경로를 하나씩 확인해보면서 count해보기
steps = [(-2, -1), (-1, -2), (1,-2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
ord()를 사용하여 아스키 코드로 바꿔서 열을 숫자로 계산하기
문자열 재정렬
알파벳을 오름차순으로 정렬하여 이어서 출력하고 모든 숫자를 더한 값을 이어서 출력
알파벳 여부와 숫자를 따로 확인하여 처리
if x.isalpha() :
result.append(x)
else :
value += int(x)
스택 : 먼저 들어온 데이터가 나중에 나가는 선입 후출 자료구조
입구와 출구가 동일한 형태
큐 : 먼저 들어온 데이터가 먼저 나가는 선입 선출 자료구조
큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능
from collections import deque
queue = deque()
queue.append(5)
queue.popleft()
재귀 함수 : 자기 자신을 다시 호출하는 함수
파이썬을 재귀 함수를 실행하면 최대 재귀 깊이 제한이 있음 (설정이 필요할 수 있음)
→ 종료 조건을 제대로 명시해야할 필요가 있음
예시)
def factorial_recursive(n)
if n <=1 :
return 1
return n * factorial_recursive(n - 1)
def gcd(a, b)
if a % b == 0 :
return b
else :
return gcd(b, a % b)
재귀함수를 잘 활용하면 복잡한 알고리즘 간결하게 작성할 수 있다!
→ 재귀함수는 반복문을 이용하여 동일하게 구현 가능
스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음
DFS: 깊이 우선 탐색
스택을 이용하여
def dfs(graph, v, visited) :
visited[v] = True
print(v, end= ' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
BFS: 너비 우선 탐색 - 가까운 노드부터 우선적으로 탐색
큐를 이용하여
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end = ' ')
for i in graph[b]:
if not visited[i]:
queue.append(i)
visited[i] = True
따로 노션에 기재하면서 강의를 정리한 내용들을 velog에 옮겨 게시하였다. 이렇게 정리하였을때, 생각보다 내 velog로 다시 되돌아와서 내가 어떻게 해놨는지 보는 경우가 많았어서 앞으로 기본 개념이 뭐였는지, 또는 면접 대비를 위해 알고리즘 기본 내용이 무엇인지 떠올리기 위해 내가 정리한 부분을 다시 찾을 것이다!!
다음에는 (2)번째 내용의 '이것이 코딩테스트다'의 내용들을 옮겨 정리해볼 예정이다~~ 그 때까지 우선,,,opic 시험 마무리를 하고 다른 개발 공부와 함께 본격적으로 알고리즘 공부를 빡세게!! 해볼 예정이다.
너무 놀았던 것 같다 ㅠㅠ 좀더 열심히 해보자~~
화이팅!