이번에는 다이나믹 프로그래밍에 대해 알아보도록 하겠습니다. 저는 이부분을 공부하면서 진짜 공식 짜고 생각하는 과정이 진짜 알고리즘 답다고 느꼈습니다. 좀 어렵긴한데 공식이 들어맞았을 때 가장 희열이 느껴지는 것 같습니다. ▶ 메모이제이션 기법 한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법입니다. 탑다운(메모이제이션), 보텀업 방식 두가지가 있습니다. DF에서 가장 많이 예시로 드는 문제는 피보나치 수열 문제입니다. 이 문제의 구현을 보면서 하나씩 알아보도록 하겠습니다.. 1. 탑다운(Top Down) 이 방법은 별로 추천하지 않으니 사용하지 말도록 합시다. 그래도 학습차원에서 무엇인지는 알아봅시다. d = [0]*100 def fibo(x): ..
이번에는 이진 탐색에 대해 알아보겠습니다. 이진 탐색은 대체로 검색 범위가 어마어마하게 많을 경우 사용합니다. 시간을 절약(?) 하기 위해 사용하는 느낌인 것 같습니다. 이진 탐색보다는 일반적으로 순차 탐색을 했었는데, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법입니다. 하지만 이럴 경우 데이터가 많아지면 시간이 너무 오래 걸린다는 단점이 있어서 그럴 경우 이진 탐색을 사용합니다. 이 녀석도 알고리즘을 외워두면 조금 편하게 사용할 수 있습니다. 이제 이진 탐색에 대해 알아보도록 합시다. 1. 이진 탐색(binary search) 간단히 말해서 반으로 쪼개면서 탐색하는 알고리즘입니다. 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있습니다. 변수 3개(..
오늘은 최단 경로 알고리즘을 공부해 보려고 합니다. 최단 경로 알고리즘이란 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 일명 길 찾기 문제라고 불립니다. 최단 경로 알고리즘은 크게 두가지 종류로 나눌수 있는데 아래와 같습니다. 다익스트라 알고리즘 플로이드 워셜 알고리즘 이 두 알고리즘에 대해 알아보겠습니다. 1. 다익스트라 알고리즘 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. 우선순위 큐를 사용하고 우선순위가 가장 높은 데이터를 가장 먼저 삭제합니다. heapq 을 사용하며, (거리, 노드) 형태의 튜플 자료형을 이용합니다. 코드로 확인해 보면 아래와 같습니다. import heapq INF = int(1e9) # n:..
[Algorithm] DFS/BFS 알고리즘과 예시
오늘은 알고리즘 중에서도 어렵다고 유명한 DFS와 BFS에 대해 공부해 보려고 합니다. 그런데 막상 공부하고 보니 이 두 알고리즘은 일단 외우고 시작하는 게 가장 좋은 것 같습니다. 실제로 이와 비슷한 문제를 마주치면 이 알고리즘을 구현해 놓고 수정하는 방법으로 진행해도 좋을 것 같습니다. 1. DFS(Depth-First-Search, 깊이 우선 탐색) 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 구현은 아래와 같이 하면 됩니다. def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited) graph = [ [], [2, 3, 8..
오늘은 구현에 대해 알아보려고 합니다. 최근에 보았던 코딩테스트에서 구현에 관련된 문제가 많이 나왔던 것 같아서 이 부분도 잘 공부해 두면 좋을 것 같습니다. 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정입니다. 구현 문제를 풀어보면서 느낀 건 알고리즘이라고 말하는 것도 조금 그렇지만 머릿속에 있는걸 소스코드로 옮기는 작업은 생각보다 쉽지 않다는 것이었습니다. 난이도도 너무 다양해서 쉬운걸 풀면서 뿌듯해 하기도 하고 좌절도 많이 주었던 유형인 것 같습니다. 그리고 그냥 구현만 하면 되다보니, 아이디어를 떠올리고 소스를 작성해 나가면 어느순간 엄청 길어지기도 합니다. 뭔가 느낌상 코딩 연습하기 좋은 것 같습니다. 이제 문제로 한 번 알아보도록 하겠습니다. 1. 상하좌우 n = int(input(..
오늘은 그리디 알고리즘에 대해 알아보려고 합니다. 그리디 알고리즘은 매 순간마다 미래를 생각하지 않고 당장 눈앞에 보이는 최적의 상황을 선택하는 기법입니다. 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다. 따라서 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됩니다. 예제 문제와 함께 소스코드로 알아보도록 하겠습니다. 참고로 문제를 연습해 보면서 실행 시간을 측정하고 싶다면 아래과 같이 시작과 끝 부분에 시간을 출력하는 메서드를 넣어줄 수 있습니다. # 수행 시간 측정하기 import time start_time = time.time() ...
오늘은 코딩테스트를 준비하면서 학습했던 내용을 정리해 보려고 합니다. 요즘 취업 시장에서 코딩테스트는 거의 필수로 자리 잡은 만큼 까먹지 않도록 주요 개념들을 기록해 두도록 합시다. 그리고 알고리즘을 알아두면 확실히 코딩을 하면서 사고력을 높이는데 도움이 되는 것 같습니다. 그리고 코딩테스트를 위해서는 파이썬이 가장 유리한 것 같아서 파이썬으로 학습을 진행해 보도록 하겠습니다. 기장 기본이 되기도 하면서 유명한 알고리즘은 바로 정렬 알고리즘이라고 생각합니다. 정렬 알고리즘 몇 개를 알아보도록 하겠습니다. 설명으로만 알아보는 것보다 소스와 함께 이해하는 게 빠르니 소스코드 위주로 이해해 봅시다. 1. 선택 정렬 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터..