개발과 기획 다하기

1) 힙 정렬 원리: 1. 배열 전체 최대 힙으로 바꾼다 2. 배열의 첫 원소(=최댓값)와 마지막 원소를 교환한다 3. 배열의 마지막 원소를 가르키는 포인터를 1 줄인다 4. 배열을 최대 힙으로 다시 바꿔준다 코드(파이썬): def heapsort(a,n): for i in range(n//2-1,0,-1): rebuildheap(a,i,n) heapsize = n for last in range(n-1,1,-1): a[0],a[last] = a[last],a[0] heapsize -= 1 rebuildheap(a,0,heapsize) def rebuildheap(a,r,n): current = r value = a[r] while 2*current + 1 < n: leftchild = 2*currren..

병합 정렬과 퀵 정렬은 간단한 정렬 알고리즘인 선택 정렬, 삽. 입 정렬, 버블 정렬에 비해 수행시간이 빠르다 또한 각자 수행시간 면에서 유리한 상황이 상이해 이에 대한 이해가 필요하다 1) 병합 정렬 원리: 1. 리스트를 반으로 나눈다 2. 두 부분을 재귀적으로 정렬한다 3. 정렬된 두 부분을 하나로 병합한다 코드(파이썬): def mergesort(a,first,last): if first < last: mid = (first + last) / 2 mergesort(a,first,mid) mergesort(a,mid+1,last) merge(a,first,mid,last) def merge(a,first,mid,last): f = first l = last k = 0 b = [] while(f < m..

*참고 - 나동빈 유튜브 https://gae-gi-da.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra 알고리즘 - 다익스트라 알고리즘(Dijkstra) *참고 저서 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이 gae-gi-da.tistory.com 다익스트라 알고리즘은 이전 포스트에서 말했듯이, 모든 간선의 가중치가 양수일 때만 적용이 가능하다. 현실의 상황에서는 간선의 가중치, 즉 거리가 음의 ..

* 참고 저서 나동빈저 https://gae-gi-da.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra 알고리즘 - 다익스트라 알고리즘(Dijkstra) *참고 저서 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이 gae-gi-da.tistory.com 다익스트라 알고리즘이 하나의 시작 지점에 대해 각 노드까지의 최단 거리를 구하는 것이었다면, 플로이드 와샬 알고리즘은 모든 노드에 대해서 모든 노드까지의..

*참고 저서 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 각 간선의 가중치들을 양수로 가정하고 있다. 따라 음의 가중치를 지닌 수가 있을 경우 다익스트라 알고리즘은 제대로 동작하지 않게 된다. 다익스트라 알고리즘의 과정은 다음과 같다. 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 과정에서 3과 4번을 반복한다. 최단 거리 테이블은 노드의 개수만큼의 크기를 지니며 출발노드에서의 최단 거리(가중치)를 ..

*참고저서 dfs, bfs 로 불리는 그래프 탐색 문제는 코딩 테스트의 단골 출제 유형이다. 자료구조에 대한 이해가 어느정도는 필요한 영역으로서 스택 / 큐 / 그래프에 대해 알아야만 한다. 이에 대해 아주 간단히 살펴보려한다. 1. 스택(stack) 기초 자료구조 중의 하나로 선입후출의 구조를 띄고 있다. 선입후출이란 먼저 들어간 자료가 가장 늦게 빠져나오는 것을 뜻한다. 파이썬에서는 기본 제공메서드인 append로 삽입 연산을, pop으로 삭제 연산을 실행할 수 있다. 재귀(recursion)에 대해 이미 알고 있다면, 재귀가 스택의 형태로 처리된다는 것도 알아야 한다. 2. 큐(queue) 스택과 다르게 선입선출의 구조를 띄고 있는 자료구조이다. 역시 삽입 연산과 삭제 연산으로 이루어져 있지만, 그..

*참고 저서 구현이라는 카테고리는 사실 기존의 알고리즘 커리큘럼에선 찾아보기 힘든 카테고리다. 모든 알고리즘이 특정 기능을 구현한다고 볼 수 있기 때문이다. 여기서 구현이란 좀 더 좁은 의미로, '특정한 접근방법없이 요구사항을 한 줄씩 구현하면 되는 문제유형'이다. 굳이 이러한 특정을 하는 이유는 기업 코딩테스트에서 이러한 유형이 꾸준히 출제되고 있기 때문이다. 구현 문제는 특정 알고리즘에 대한 이해보다는 문제에 대한 독해력, 사용 언어에 대한 숙련도, 코드 작성 속도 등이 중요한 문제라고 볼 수 있다. 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나 누어져 있다. 가장 왼쪽 위 좌표는 (1, 1 )이며, 가장 오른쪽 아래 좌표는 (N, 비 에 해..

*참고저서 - 나동빈 그리디는 한국어로 바꾸면 말 그대로 '탐욕스러운'이라는 뜻이다. 이름과 같이 이후 상황을 고려하지 않고 현재 상황에서 가장 좋은 것만 고르는 방법이다. 그리디의 경우 dfs/bfs/mst 문제들처럼 코드의 원형이 따로 없으며 아이디어의 형태로 존재한다. 해당 문제가 그리디로 해결 가능한지 판별하고 정답을 제공하는 접근법을 떠올리기까지가 그리디 문제의 핵심이라 할 수 있다. 여기서 보통 '~~한 순서로' 와 같은 접근법이 나오기에, 정렬에 대한 이해도 조금은 필요하다. 그리디 문제를 설명하는 대표 예제는 거스름돈 문제이다. 거슬러 줘야 할 돈 N원이 주어졌을 때, 500,100,50,10원 짜리 동전들을 이용해 거슬러 준다 하자. 이 때 동전의 최소 개수를 구하라. 가장 쉬운 예제답게..