본문 바로가기

코딩 테스트

(10)
코딩 테스트 주요 알고리즘 feat.그래프 이론 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. 그래프 알고리즘 그래프 알고리즘은 매우 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 제대로 알아야 하는 알고리즘이다. 그래프는 노드(Node)와 노드 사이를 연결하는 간선(Edge)으로 이루어져있는 자료구조이다. 따라서 서로 다른 객체가 연결되어 있다는 내용이 있으면, 그래프 알고리즘을 떠올려야 한다. 또한 트리 자료구조는 다양한 알고리즘에서 사용되므로 기억해두어야 한다. 다익스트라 최단 경로 알고리즘에서 사용되는 우선순위 큐를 구현할 때, 최소힙을 이용할 수 있는데, 이때 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다. 그래프 VS 트리 자료구조 그래프 ..
코딩 테스트 주요 알고리즘 feat.최단 경로 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. 최단 경로 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 3가지가 대표적이다. 이 중 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘에 대해 다뤄보도록 하자. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 다익스트라 최단 경로 알고리즘은 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로 분류된다. 알고리즘의 원리는 다음과 같다. 출발 노드를 ..
코딩 테스트 주요 알고리즘 feat.다이나믹 프로그래밍 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. 다이나믹 프로그래밍 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 짜도록 해야한다. 어떤 문제에 대해 약간의 메모리를 더 사용함으로써, 연산 속도를 매우 증가시킬 수 있는 다이나믹 프로그래밍 기법(동적 계획법)이 있다. 이를 개념적으로 설명하자면, 큰 문제를 중복이 일어나지 않는 작은 문제들로 나누어 푸는 방식이다. 이때, 작은 문제들이 반복하는 경우에 해당 문제에 대한 정답이 동일하다. 따라서 한번 계산한 작은 문제들을 각각 저장을 해놓고 나중에 반복이 될 때 다시 사용할 수 있도록 한다. 이를 메모이제이션(Momoization)이라고 한다. 이 다이나믹 프로그래밍은 탑다운(Top..
코딩 테스트 주요 알고리즘 feat.이진 탐색 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. 이진 탐색 순차 탐색 순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 순서대로 데이터를 하나씩 확인하는 방법이다. 이 방식은 정렬이 되지 않은 리스트에서 원하는 특정 데이터를 시간만 있다면 찾아낼 수 있다는 장점이 있다. 순차 탐색의 파이썬 코드는 다음과 같다. # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인 for i in range(n): # 현재 원소가 찾고자하는 원소와 동일 하면 if array[i] == target: return i + 1 # 현재 위치 반환 print("생성할 원소 개수를 입력한 다음..
코딩 테스트 주요 알고리즘 feat.정렬 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. 정렬 정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 정렬 알고리즘은 다음에 포스팅할 이진 탐색의 전처리 과정이라고 할 수 있다. 많은 정렬 알고리즘들 중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 알아보자. 이 정렬 알고리즘들을 공부하면서 알고리즘의 효율성의 중요성을 자연스럽게 깨닫게 될 수 있다. 선택 정렬 선택정렬은 맨 앞의 데이터부터 가장 작은 데이터를 맨 앞으로 보내면서 데이터를 정렬하는 방식이다. 이렇게 가장 작은 데이터가 맨 앞에 오게 되면, 그 다음 두 번째 자리부터 이를 다시 반복하게 된다. 이를 파이썬 코드로 표현하면 다음과 같다. array = [7, 5, 9, ..
코딩 테스트 주요 알고리즘 feat.DFS/BFS 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. DFS/BFS 사전 지식 탐색은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 이때 대표적인 탐색 알고리즘은 DFS와 BFS이다. 이 DFS와 BFS를 알아보기 위하여 기본 자료구조인 스택과 큐에 대한 개념과 재귀함수, 그래프에 대해서 먼저 알아보자. 스택 스택(Stack)은 상자를 쌓는 것과 비슷하다고 할 수 있다. 일반적으로 상자는 바닥부터 위로 쌓으며, 이를 다시 꺼내기 위해서는 위에서부터 순서대로 꺼낸다. 이러한 구조를 선입후출구조 (First In Last Out) 또는 후입선출구조(Last In First Out)라고 한다. 이를 파이썬 코드로 표현하면 다음과 같다. stack=[] # ..
코딩 테스트 주요 알고리즘 feat.구현 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. 구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 즉, 어떤 문제든 소스코드를 작성하는 과정이 있으므로, 구현 문제는 모든 코딩 테스트 문제 유형을 포함한다고 할 수 있다. 구현 유형의 문제는 풀이를 떠올리기 쉽지만, 이를 소스코드로 옮기는 것은 어려운 문제를 의미한다. 특히 이 책에서는 완전 탐색과 시뮬레이션을 구현 유형으로 다루고 있다. 완전 탐색은 모든 경우의 수를 다 계산하는 해결 방법이며, 시뮬레이션은 제시된 알고리즘을 한 단계씩 직접 수행하는 문제를 의미한다. 이 유형은 따로 정해진 알고리즘 틀이 있는 것이 아니므로, 문제들을 통해 어떤 식으로 풀어야 하는지 감을 잡아보도록 하자. 예제 4-1 ..
코딩 테스트 주요 알고리즘 feat.그리디 본 내용은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. 그리디 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디 알고리즘은 탐욕법으로 소개되는데, 이는 말 그대로 단순하게 탐욕적으로 문제를 푸는 알고리즘이라는 의미이다. 나중의 영향을 고려하지 않고, 현재 순간에서 가장 좋은 선택을 해나가는 것이다. 이러한 그리디 알고리즘 문제는 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많다. 그리디 알고리즘은 많은 유형을 접해보며, 문제에 익숙해지도록 훈련해야 한다. 그러면 그리디 알고리즘의 대표 예시인 최소한의 동전으로 돈을 거슬러주는 '거스름돈 문제'를 생각해보자. 이 문제를 풀기 위한 핵심 아이디어는 가장 큰 화폐 단위부터 거슬러 주는 것이다...