ddu programming

이번에는 다이나믹 프로그래밍에 대해 알아보도록 하겠습니다. 저는 이부분을 공부하면서 진짜 공식 짜고 생각하는 과정이 진짜 알고리즘 답다고 느꼈습니다. 좀 어렵긴한데 공식이 들어맞았을 때 가장 희열이 느껴지는 것 같습니다. ▶ 메모이제이션 기법 한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법입니다. 탑다운(메모이제이션), 보텀업 방식 두가지가 있습니다. DF에서 가장 많이 예시로 드는 문제는 피보나치 수열 문제입니다. 이 문제의 구현을 보면서 하나씩 알아보도록 하겠습니다.. 1. 탑다운(Top Down) 이 방법은 별로 추천하지 않으니 사용하지 말도록 합시다. 그래도 학습차원에서 무엇인지는 알아봅시다. d = [0]*100 def fibo(x): ..

이번에는 이진 탐색에 대해 알아보겠습니다. 이진 탐색은 대체로 검색 범위가 어마어마하게 많을 경우 사용합니다. 시간을 절약(?) 하기 위해 사용하는 느낌인 것 같습니다. 이진 탐색보다는 일반적으로 순차 탐색을 했었는데, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법입니다. 하지만 이럴 경우 데이터가 많아지면 시간이 너무 오래 걸린다는 단점이 있어서 그럴 경우 이진 탐색을 사용합니다. 이 녀석도 알고리즘을 외워두면 조금 편하게 사용할 수 있습니다. 이제 이진 탐색에 대해 알아보도록 합시다. 1. 이진 탐색(binary search) 간단히 말해서 반으로 쪼개면서 탐색하는 알고리즘입니다. 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있습니다. 변수 3개(..

오늘은 최단 경로 알고리즘을 공부해 보려고 합니다. 최단 경로 알고리즘이란 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 일명 길 찾기 문제라고 불립니다. 최단 경로 알고리즘은 크게 두가지 종류로 나눌수 있는데 아래와 같습니다. 다익스트라 알고리즘 플로이드 워셜 알고리즘 이 두 알고리즘에 대해 알아보겠습니다. 1. 다익스트라 알고리즘 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. 우선순위 큐를 사용하고 우선순위가 가장 높은 데이터를 가장 먼저 삭제합니다. heapq 을 사용하며, (거리, 노드) 형태의 튜플 자료형을 이용합니다. 코드로 확인해 보면 아래와 같습니다. import heapq INF = int(1e9) # n:..

오늘은 알고리즘 중에서도 어렵다고 유명한 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..

오늘은 그리디 알고리즘에 대해 알아보려고 합니다. 그리디 알고리즘은 매 순간마다 미래를 생각하지 않고 당장 눈앞에 보이는 최적의 상황을 선택하는 기법입니다. 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다. 따라서 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됩니다. 예제 문제와 함께 소스코드로 알아보도록 하겠습니다. 참고로 문제를 연습해 보면서 실행 시간을 측정하고 싶다면 아래과 같이 시작과 끝 부분에 시간을 출력하는 메서드를 넣어줄 수 있습니다. # 수행 시간 측정하기 import time start_time = time.time() ...

오늘은 스택에 대해 공부해보자! 스택(Stack) 자료구조는 한쪽 끝이 막힌 형태이다. 스택의 가장 큰 특징은 입구가 하나뿐이기 때문에 먼저 들어간 것이 가장 나중에 나오는 구조이다. 이를 선입후출(First In Last Out, FILO)이라고 하거나 반대로 후입선출(Last In First Out, LIFO)이라고 한다. 스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다. 스택에 데이터를 삽입하는 동작을 push(푸시)라고 하며, 반대로 데이터를 추출하는 동작을 pop(팝)이라고 한다. 스택에서는 top이라는 용어가 중요한데, 현재 스택에 들어있는 가장 위의 데이터 위치를 가리키는 개념이다. 스택은 배열 형태로 구현할 수 있다. 스택이 작동하는 코드를 구현해 보자. # 함수..

오늘은 선형 리스트와 비슷한듯 다른 단순 연결 리스트에 대해 알아보자! 앞서 공부했던 선형 리스트는 배열에 데이터를 차례대로 저장하므로 데이터의 실제 위치 순서로 구성된다. 한마디로 물리적인 순서와 논리적인 순서의 구조가 동일하다. 반면 단순 연결 리스트(Singly Linked List) 에서는 노드들의 위치가 모두 떨어져 있고, 노드의 주소도 순차적이지 않다. 하지만 연결된 링크(Link)를 따라가다 보면 순서대로 정렬할 수 있다. 선형 리스트와 단순 연결 리스트를 좀 더 자세히 비교해 보자. 선형 리스트에서는 데이터의 삽입하거나 삭제할 때에 많은 작업이 필요하다. 중간에 삽입하게 되면 중간부터 끝까지의 데이터가 모두 한칸씩 뒤로 이동해야 한다. 삭제할 때에도 한칸씩 앞으로 당여져야 한다. 이렇게 될..

어제 공부한 선형 리스트의 예제 카톡 친구 자동 삽입하기 문제를 풀어보도록 하겠다. 난이도는 별 ★★ 앞서 했던 예제들과 비슷하지만 이번에는 삽입할 위치가 정해진게 아니라 위치를 내가 정해줘야 한다는 점이 조금 다른 것 같다. 예제 설명 : 카톡 친구 이름과 카톡 횟수를 입력하면 자동으로 위치를 찾아 삽입하는 프로그램이다. (친구이름, 연락횟수) 튜플 리스트로 시작한다. 초기 정보는 [('다현', 200), ('정연', 150),('쯔위', 90),('사나', 30),('지효', 15)] 연락횟수가 같을 경우에는 추가한 친구를 먼저 작성한다. # 함수 설정하기 def find_position(name, count): fLen = len(friend) pos = -1 for i in range(fLen):..