algorithm/theory

비트마스크 알고리즘

비트마스크 비트마스크(Bitmask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. 비트마스크를 사용하면 더 빠른 시간 내에 연산을 해결하는 경우가 있다. 예를 들어, 2의 50승을 구해야 하는 문제가 있다고 하자. 이 경우 for문을 50번 돌려서 2를 계속 곱해나가야 한다 생각할 수 있지만, 비트마스크를 사용하면 1

최단 경로

가장 빠르게 도달하는 방법 최단 경로(Shortest path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점(국가 or 마을 등)은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출력된다. 코딩 테스트 수준에서는 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형만 파악해도 충분하다. 더불어 앞서 공부한 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다. 다익스트라 최단 경로 알고리즘 다익..

다이나믹 프로그래밍

어떤 문제를 해결하는데 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터로도 해결하기 어렵다. 그래서 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이나믹 프로그래밍이다. 여기 일반적인 피보나치 수열 코드가 있다. def fibo(n): if n==1 or n==2: return 1 return fibo(n-1)+fibo(n-2) 그런데 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 n이 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이 소스코드의 시간 복잡도는 O(2^n..

이진 탐색

이진 탐색은 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 이진 탐색 : 반으로 쪼개면서 탐색하기 이진 탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 이진 탐색을 구현하는 방법에는 2가지가 있다. 재귀 함수 반복문 이진 탐색 - 재귀 함수 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid ..

정렬

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 선택 정렬 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. array=[7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index=i for j in range(i+1,len(array)): if array[min_index]>array[j]: min_index=j array[i],array[min_index]=array[min_index],array[i] #swapping print(array) -> O(n2) 선택 정렬은 다른 정렬 알고리즘이나 파..

DFS/BFS

그래프에 대한 설명 참고 DFS DFS는 Depth-First-Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다. (이건 문제에 따라 다르게 적용시킬 수 있다.) DFS는 스택을 이용하는 알고리즘이기 때문에 실..

구현

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 보통 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열은 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 (순열과 조합을 찾는 경우 등) -> 많은 연습이 필요한 분야이다.(프로그래밍 언어의 문법을 정확히 알고 있어야 한다.) 대표적으로 완전 탐색과 시뮬레이션 유형을 '구현' 유형으로 많이 사용한다. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 -> 보통 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적..

그리디

그리디 알고리즘 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디 알고리즘은 다른 유형과 달리 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 최단 경로 알고리즘의 경우 플로이드 워셜, 다익스트라 알고리즘과 같은 특정 알고리즘을 미리 알고 있거나 팀 노트를 통해 준비해야 풀 수 있다. 그러나 그리디 알고리즘의 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다. +) 그리디는 보통 작은 값 혹은 큰 값부터 처리하는 경우가 많기 때문에 정렬 알고리즘과도 연관이 있다. 예제) 거스름돈 Q. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈..