힙 (Heap) 힙(Heap)은 완전 이진트리인 특별한 트리를 기반으로 한 자료구조이다. 힙에는 최대힙과 최소힙이 있는데, 최대힙은 최대값을 다루는데 특화되어 있고 최소힙은 최소값을 다루는데 특화되어 있다. 각 힙은 일련의 원소들이 주어졌을 때 최대 or 최소 원소를 빠르게 조회, 삭제할 수 있다. 또한 각 힙 모두 임의의 원소를 빠르게 삽입할 수 있다. 최대, 최소 원소를 다루는 특수적인 상황에 있어 효율적이고, 의외로 최대 최소 원소를 활용해야 하는 상황이 많이 발생하기 때문에 굉장히 중요한 자료구조에 속한다. (우선순위큐도 힙으로 제작된다.) 힙에서 제공하는 연산들을 배열과 비교해보자. 값 삽입 배열 : O(1) 힙 : O(log N) 최대값 or 최소값 삭제 배열 : O(N) 힙 : O(logN)..
그래프 간선의 분류 그래프의 구조와 특성을 파악하려면 어떤 방법을 이용해야 할까? 깊이우선탐색(DFS)은 그래프의 구조를 파악하는데 사용될 수 있다. 깊이우선탐색을 수행하면 그 과정에서 그래프의 모든 간선을 한번씩은 만나게 된다. 그중 일부 간선은 처음 발견한 정점으로 연결되어 있어서 우리가 따라갈 테고, 나머지는 무시하게 될 것이다. 하지만 이 간선들을 무시하지 않고 이들에 대한 정보를 수집하면 그래프의 구조에 대해 많은 것들을 알 수 있다. 어떤 그래프를 깊이 우선 탐색했을 때 탐색되는 간선들만 모아 보면 트리 형태를 띄게 된다. 예를들어 다음 왼쪽 그림에 있는 그래프를 0번 정점을 기준으로 깊이우선탐색을 했을 때, 오른쪽 그림의 굵은 검정색 간선들처럼 탐색이 될 것이다. 이처럼 깊이우선탐색으로 탐색..
백트래킹 백트래킹(Backtracking)은 컴퓨터 계산 문제, 특히 제약 충족 문제(Constraint Satisfaction Problem)에 대한 해결방법을 찾기 위한 일반적인 알고리즘으로, 솔루션에 대한 후보를 점진적으로 구축하고 후보가 유효하지 않다면 해당 후보를 포기하고 퇴각하여 이전 단계부터 다른 선택을 해나가는 방식으로 동작한다. 다음 문제들을 보자. 스도쿠 스도쿠는 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분된 3 x ..
유향 비순환 그래프 유향 비순환 그래프(Directed Acyclic Graph, DAG)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 사이클이 없는 유향 그래프이다. 즉, 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련한 간선을 따라가는 방법이 없는 그래프를 의미한다. 또한 사이클이 없는 방향그래프라는 정의를 통해 모든 트리는 DAG임을 알 수 있다. (어떤 그래프가 주어졌을 때 이 그래프가 DAG인지 판단하기 위해서는 사이클의 존재여부를 확인하면 된다.) 위상 정렬 위상 정렬(Topological Sort)은 모든 방향 모서리 u v에 대해 정점 u가 순서에서 v 앞에 오도록 정점들을 정렬하는 알..
최단 경로 최단 경로란 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제로, 그래프의 응용문제 가운데 가장 유용하고 널리 사용된다. 가중치가 없는 그래프에 대한 최단 경로는 너비 우선 탐색(Breadth First Search)을 통해 구할 수 있지만, 가중치가 있는 그래프에 대해서는 좀 더 복잡한 방법이 필요하다. 음수 사이클 최단 경로 문제를 해결하기 위해 가장 유의해야 하는 부분은 음수 가중치를 갖는 간선이 있는지다. 음수 간선이 존재하는 그래프에서 해당 간선을 지나가면 전체 경로의 길이가 짧아지게 된다. 이러한 특성에 더해 만약 가중치에 합이 음수인 사이클이 그래프에 존재한다면, 최단 경로의 길이는 음의 무한대까지 발산하게 된다. 그러므로 음수 사이클이 있는 그래프에서는 어..
오일러 경로 오일러 경로(Eulerian Trail)은 그래프에 존재하는 모든 간선을 정확히 한 번씩 방문하는 연속된 경로를 의미한다. 시작점을 어느 지점으로 하느냐에 따라 몇몇의 간선에 도달하지 못할수도 있다. 오일러 회로 오일러 회로(Eulerian Circuit)은 시작점과 끝점이 같은 오일러 경로를 의미한다. 다음과 같이 그래프가 오일러 회로를 갖지 않는 경우도 존재한다. 일반적으로 오일러 경로가 없는 경우거나 오일러 경로가 존재하지만, 시작과 끝점이 다른 경우이다. 오일러 경로는 오일러 회로일 수도 있지만, 시작 정점과 끝 정점이 다른 경우도 포함하므로 오일러 회로가 아닐 수도 있다. 오일러 회로를 이용한다면 정해진 단어 집합에서 모든 단어를 끝말잇기로 연결하는 예제나 가진 항공권을 모두 이용하..
부분합 다음과 같은 수열이 있다. v = {2, 3, 7, 5} 이 수열에서 구간 [1, 3]의 합은 3 + 7 + 5 = 15 이다. 이처럼 어떤 임의의 구간 [i, j]가 주어졌을 때, 구간의 합을 구하기 위해서는 해당 구간을 순회하며 값을 더하면 될 것이다. 하지만 만약 수열의 크기 N이 크고 이런 구간에 대한 질의 개수 Q도 많아진다면 어떻게 될까? 위와 같은 방식으로는 최악의 경우 O(N x Q) 의 시간복잡도를 갖게 될 것이다. 이러한 문제를 해결하기 위해 고안된 방법으로 부분합(Partial Sum or Prefix Sum)이 있다. 부분합은 배열 원소의 인덱스까지의 합으로 다음과 같이 정의된다. psum[i] = ∑ v[k] (0
그래프 그래프는 트리보다도 훨씬 더 일반적이고 강력한 자료구조로, 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하기 위해 사용된다. 사람들 간의 관계, 도로와 도시들 사이의 관계, 네트워크로 연결된 컴퓨터들의 관계와 같은 것들을 연결 구조의 예로 들 수 있을 것이다. 그래프는 이러한 다양한 관계에 대해 표현할 수 있고, 현실세계의 문제를 그래프로 매핑시킨 후에는 여러 그래프 알고리즘들을 이용하여 그 문제들을 해결할 수 있다. 그래프는 객체들을 대응시키기 위한 개념인 정점(Vertex) 집합과, 관계들을 대응시키기 위한 개념인 간선(Edge) 집합 G(V, E)의 형태로 정의한다. 일반적으로 정점 집합은 각 정점에 대응되는 번호로 나타내고, 간선 집합은 정점번호 쌍의 집합으로 나타낸다. V =..
구간트리 구간 트리는 일차원 배열의 특정 구간에 대한 질의를 빠르게 대답하는데 사용된다. 예를 들어 어떤 숫자들이 주어진다고 가정해보자. S = {1, 2, 1, 2, 3, 1, 4, 2, 2} 이 숫자들에 특정 구간에 대한 질의가 들어온다고 생각해보자. 예를들면 [2, 4] 구간의 최소값은 1이고, [6, 8]구간의 최소값은 2이다. 물론 이 처리를 위해 순회를 하며 최소값을 찾을 수 있다. 하지만 이 방법은 O(N)의 수행시간을 갖는다. 만약 이러한 질의가 무수히 많이 들어온다면 어떨까? 기존의 방법대로라면 쿼리의 개수가 Q라고 했을 때, O(Q x N)의 수행시간을 갖게 될 것이다. 하지만 구간트리는 하나의 쿼리를 O(logN) 시간에 수행할 수 있고, 모든 쿼리에 대해서는 O(QlogN) 시간에 ..
트라이 (Trie) 문자열을 다루는 작업은 정수나 실수를 다르는 것과는 다르다. 정수나 실수는 고정된 크기만큼의 메모리만 이용하지만, 문자열의 경우에는 그 크기가 정해져 있지 않다. 그러므로 최악의 경우 문자열 길이에 비례하는만큼 시간을 소모하게 된다. 그렇기 때문에, 정수나 실수와 같은 타입에 대해서는 훌륭하게 동작하는 이진트리나 해시테이블 같은 자료구조도, 문자열을 저장하는데에 있어서는 취약하다. 이진트리에 일반적인 정수 타입을 검색, 삽입, 삭제 하는데에는 O(logN)의 시간이 걸린다. 하지만 이진트리에 길이 M의 문자열을 N개 저장한다고 했을 때, 이 문자열 타입에 대한 연산은 O(MlogN)이 걸린다. 즉, 문자열이 길어지게 되면 이진트리의 장점도 무용지물이 된다는 의미이다. 해시테이블도 마찬..
동적계획법 동적 계획법은 수학 이론에서 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 부분 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 분할정복 vs 동적계획법 (부분문제의 중복) 전..
재귀 함수 컴퓨터가 수행하는 대부분의 작업들은 좀 더 작은 단위의 작업들로 나누어 볼 수 있다. 예를 들어 온라인으로 상품을 구매하는 작업은, 상품 정보 조회하기, 구매자 정보 조회하기, 구매자-상품 결제 처리하기, 데이터베이스 갱신하기, 문자 보내기 와 같은 더 작은 단위의 작업들로 나누어진다. 또 그 중에서 상품 정보 조회하기와 같은 작업은, 자료구조에 따라 다르겠지만, 상품 정보를 비교하는 작업을 반복적으로 수행하여 정보를 찾게 된다. 이렇게 어떤 작업들을 더 작은 작업들로 표현할 수 있는데, 이 범위가 작아지면 작아질수록 작업의 형태가 유사해지게 된다. 이런 상황을 코드로 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수이다. 재귀적 정의 재귀 함수란 수행해야하는 목표 작업을 유사한 형태의 조각..
분할 정복 분할 정복(Divide ans Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로 큰 문제를 작은 문제로 분할하여 해결하는 전략이다. 이 전략을 활용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀 함수를 이용하여 계산한다. 그 후 부분 문제의 답을 이용하여 전체 문제의 답을 계산해낸다. 분할정복 전략이 일반적인 재귀함수와 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다는 것이다. 그렇다면 분할정복이 필요한 이유는 무엇일까? 분할 정복을 활용하면, 선형적인 방법보다 빠르게 문제를 해결할수도 있기 때문이다. 다음 예제를 보자. 어떤 수 N과 P가 주어졌을 때, N의 P승을 구하는 알고리즘을 작성하라. 일반적..
상태 공간 탐색 상태 공간 탐색은 인공지능을 포함한 컴퓨터공학에서 사용되는 전략으로 문제에서 정의될 수 있는 모든 상황을 상태로 정의한다. 그 후 각각의 상태에서 수행할 수 있는 모든 선택을 행동으로 정의하여 원하는 속성을 갖는 목표 상태에 도달하기까지 여러 가지 전략으로 행동들을 선택해나가는 탐색 과정이다. 일반적으로 가능한 해 중 가장 최적의 해를 찾는 형태인 최적화 문제(Optimization Problem)를 해결하기 위해 많이 사용된다. 문제는 굉장히 다양한 방법으로 정의될 수 있지만, 탐색 과정 중에 얻는 정보들을 적절하게 이용하여 각 문제를 해결할 수 있다. 먼저 틱택토(Tic-Tac-Toe) 게임을 예로 들어보자. 틱택토는 두 명이 번갈아 가며 O와 X를 3 x 3 게임판에 놓아서 같은 글..
시뮬레이션, 구현 시뮬레이션 및 구현 문제는 문제에서 제시한 상황을 알고리즘으로 수행해내도록 구현하는 문제이다. 일반적으로 게임 상황을 재현하는 문제들이 자주 등장한다. 예를들면 다음과 같은 문제들이다. https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 이런 형태의 문제들은 딱히 대단한 전략을 갖고있어야 하는것은 아니지만, 분석해야하는 요구사항이나, 구현해야하는 코드량과 예외처리들이 많기..
완전탐색 완전탐색 알고리즘은 문제는 해결하는 전략 중 하나로, 가능한 모든 경우의 수를 다 찾고, 그 중에서 답을 고르는 전략이다. 하지만, 가능한 모든 경우의 수를 다 나열해 보는것은 생각보다 어려운 일이다. 우리가 수학에서 배우는 단순한 경우의 수를 예로 들어보자. 1~4 까지의 숫자가 적힌 공들 중 임의의 두 공을 고르는 모든 경우의 수는 총 6가지이다. (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 수학적으로는 조합이라는 개념으로 이를 표현한다. Combination(4, 2) = 6 이렇게 단순하게 모든 경우의수를 생각해낼 수 있는 문제도 물론 존재한다. 하지만 다음과 같은 문제는 어떨까? Queen은 가로, 세로, 양쪽 대각선 모두 공격이 가능하다. 8 x..
조합 모든 경우의 수를 표현하기 위해 자주 사용되는 또다른 전략 중 하나는 조합이다. 조합으로는 어떤 상황이 놓였을 때 선택에 대한 경우의 수를 표현할 수 있다. 예를 들어 다음과 같은 회사 목록이 있다고 가정해보자. vector company = { "Apple", "Google", "Amazon", "Facebook" }; N개의 원소에서 K개를 고르는 조합 이 회사 목록에서 3개의 회사를 선택하는 모든 경우의 수를 생각해보자. 다음과 같은 선택지들이 있을 것이다. "Apple", "Google", "Amazon", "Apple", "Google", "Facebook" "Apple", "Amazon", "Facebook" "Google", "Amazon", "Facebook" 이처럼 어떤 N개의 원소..
무차별 대입법 (Brute Force) 무차별 대입법은 모든 가능한 값을 다 시도해보는 형태의 전략을 의미한다. 그 중에서도 알고리즘 분야에서는 중첩 루프를 이용하여 표현하는 전략을 의미한다. 무차별 대입을 하는데 있어 필요한 개념들을 정리해보자. 순서쌍 다음과 같은 문제를 생각해보자. 두 자연수 n과 k에 대해 (1
비트마스크 현대의 모든 CPU는 이진수를 이용하여 자료를 표현한다. 이러한 구조 덕분에 컴퓨터는 이진법 관련한 연산들을 아주 빠르고 쉽게 수행할 수 있다. 그리고 이 특성을 프로그래밍에서도 활용할 수 있는데, 그 활용 기법을 비트마스크라고 부른다. 비트마스크를 이용하면 다음과 같은 이점들을 얻을 수 있다. 1. 매우 빠른 시간에 동작한다. 2. 간결하게 코드를 작성할 수 있다. 3. 메모리 절약이 가능하다. 4. 중첩 컨테이너를 단순 컨테이너로 대체할 수 있다. ex) // 기존 map // 비트마스크 활용 vector 5. 집합 개념으로 활용될 수 있고 집합 관련한 연산들을 매우 쉽게 표현할 수 있다. (매우 중요) ex) 다음과 N개의 원소가 있을 때, 이에 대한 모든 부분집합을 나열해보자. vect..
코딩테스트 연습 > 2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 시행착오 x 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Extra/Solutions/Programmers/%ED%81%AC%EB%A0%88%EC%9D%B8%20%EC%9D%B8%ED%98%95%EB%BD%91%EA%B8%B0%20%E..
상호 배타적 집합 어떤 학교에 N명의 사람이 있다고 가정해보자. 학교에서 이 사람들은 처음에는 흩어져 있다가, 서로 같은 학과임을 확인하면 같이 그룹을 만든다. 만약 두 그룹이 서로가 같은 학과임을 확인하면 두 그룹을 합한 더 큰 그룹을 만든다. 이 상황을 표현하기 위해 사용되는 개념이 상호 배타적 집합(서로소 집합)이다. 상호 배타적 집합은 흩어져 있는 원소들을 묶어서 표현한다. 중요한 점은, 이 집합에서는 서로 다른 두 집합에 대해서 교집합이 생기는 상황을 가정하지 않는다. 즉 교집합이 있다면, 그것은 상호배타적 집합이라 할 수 없다. 이것을 알고리즘으로 표현하려면 어떻게 해야 할까? 상호 배타적 집합을 표현하기 위해서는 기본적으로 다음과 같은 연산들이 필요하다. Find : 어떤 원소가 속한 그룹을..
코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT 오픈채팅방 programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 시행착오 1. 빈 log를 answer에 집어넣음 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/Solutions/Programmers/%EC%98%A4%ED%94%88%EC%B1%84%ED%8C..
코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT 문자열 압축 programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 시행착오 시행착오 1. 문자열을 무조건 제일 앞부터 잘라야 한다는 조건을 제대로 읽지 않았음. 2. 한번 자른 문자열이 계속 나타나는지 확인하는것이 아니라, 고정된 크기로 자른 문자열이 연속적으로 같은지 판단해야하는데 이 부분을 잘못 이해함 3. 탐색 범위 오류 (i < s.size()..
Binary Search Tree vs Hash Table 기본적으로 Binary Search Tree와 Hash Table은 모두 키 & 값 형태로 자료를 저장하는 자료구조이다. 그렇기 때문에 사용성 측면에서는 굉장히 유사한 인터페이스를 갖고 있고, 지원하는 연산들도 아주 흡사하다. 그런 이유로, 자주 비교대상이 되는 자료구조로써 각각의 장단점을 한번쯤 정리해볼 필요가 있다. 기능적인 측면 탐색, 삭제, 삽입과 같은 기본기능들에 대해서, 해시 테이블 : O(1) 이진탐색트리 : O(logN) 정도 성능으로 동작한다. 해시 테이블의 해시 함수의 비용과, 충돌 해결비용까지 고려하더라도 데이터가 엄청 많아지는 경우에는 해시 테이블이 효과적이라고 볼 수 있다. 그리고 만약 입력 사이즈를 알고 있다면, 입력 사..
