CS/알고리즘 (9) 썸네일형 리스트형 [ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++) 1. 이분탐색 원리 이분탐색은 오름차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법이다. 정렬된 배열에서 특정 값을 찾을 때 정중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있다. 아래 그림을 보자. 배열은 오름차순으로 정렬되어 있다고 가정한다. 배열의 시작점과 끝점의 정중앙에 위치한 값을 '중앙값'이라고 부르겠다. 만약에 그림과 같이 '탐색값 < 중앙값' 이면 중앙값의 오른쪽 부분은 고려할 필요가 없다. 오름차순으로 정렬되어 있기 때문이다. 따라서 이제 끝점은 중앙값이서 1을 뺀 위치가 된다. 끝점의 위치가 이동했으므로 중앙값의 위치도 아래 그림과 같이 이동한다. 이번에는 '중앙값 < 탐색값' 이므로 중앙값의 왼쪽 부분은 볼 필요가 없다. 따라서 시작점은 중앙값에 1을 더해준.. [C++] 투 포인터로 연속 부분합 구하기 어떤 수열의 연속 부분합을 구해보자!! 어떻게 해결할 것인가? 직관적으로 떠오르는 아이디어는 단순하게 이중 for문을 돌리는 것이다. 그러나 이 방법은 O(N^2)의 시간복잡도를 가지기 때문에 효율적이지 못하다. 투 포인터를 사용하면 시간 복잡도를 O(N)까지 단축시킬 수 있다. 위 문제의 핵심은 '연속'에 있다. 연속합을 구하는 것이기 때문에 중복되는 부분이 존재한다. 말로 하면 헷갈리니깐 그림으로 보자. 위 그림에서 빨간색과 파란색의 연속된 부분합에서 형광색 부분이 중복됨을 알 수 있다. 이 사실을 잘 기억하자. 이제 투 포인터의 알고리즘을 살펴보고, 손으로 예제 한 문제를 직접 풀어보자. [ 투 포인터 알고리즘 ] 1. 시작점(start), 끝점(end)을 -1로 초기화한다 2. 현재 부분합(sum.. [C++] 위상 정렬(Topology Sort) 위상 정렬은 비순환 단방향 그래프에서 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주는 알고리즘이다. 순서만 맞으면 되기 때문에 정답이 두 개 이상일 수 있다. 단, 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. 이렇게 사이클이 발생하지 않는 그래프를 DAG(Directed Acyclic Graph)라고 한다. 즉, 위상정렬은 DAG에서만 정의될 수 있다. 위상 정렬을 구현하기 위해서 '진입 차수'라는 개념을 알아야 한다. '진입 차수'란 노드로 들어오는 간선의 개수다. 말로 하면 헷갈리니깐 바로 그림으로 알아보자. 위 그림의 경우 진입 차수는 3이다. 노드0으로 들어오는 화살표의 개수가 3이기 때문이다. 위 그림의 경우 진입 차수는 0이다. 노드 0으로 들어오는 화살표.. [C++] 다익스트라(Dijkstra) 1. 다익스트라의 구성 최소 거리를 구할때 사용하는 대표적인 알고리즘 '다익스트라'에 대해 알아보자. 다익스트라 알고리즘은 시작점으로부터 모든 노드까지의 최소거리를 구해준다. 다익스트라를 구현하기 위해서는 비용 배열, 방문 노드 배열, 시작점~각 노드까지의 비용 배열이 필요하다. [ 다익스트라 구현시 필요 요소 ] 1. 비용 배열 weight(이중배열) 출발지에서 목적지로 갈 때 드는 비용을 나타내는 배열이다. weight[3][5] = 5 // 노드3 -> 노드5 갈 때 비용이 5만큼 든다는 뜻이다. weight[2][4] = INF // 노드2 -> 노드4 갈 때 비용이 무한만큼 든다는 뜻이다. 2. 방문 노드 배열 visit 방문한 노드를 확인하는 배열이다. visit[3] = true // 노드3.. [C++] 중위 표기식을 후위 표기식으로 변환 후 계산 중위 표기식은 연산자가 중간에 위치하는 표기식으로 우리가 늘 쓰는 표기식이다. 후위 표기식은 연산자가 뒤에 있는 표기식으로 컴퓨터의 연산 방식이다. 컴퓨터는 사람이 입력한 중위 표기식을 후위 표기식으로 변환해서 연산을 진행한다고 한다. 중위 표기식 : A * (B + C) 후위 표기식: ABC+* 이번 글에서는 중위 표기식을 후위 표기식으로 변환하는 알고리즘과 후위 표기식을 계산하는 알고리즘을 다룬다. 두 가지 경우 모두 stack 자료구조가 필요하다. 1. 중위 표기식을 후위 표기식으로 변환 알고리즘은 아래와 같다. 1) 피연산자는 무조건 출력 2) 연산자인 경우 ---- top보다 우선순위 크면 push ---- top보다 우선순위 작거나 같으면 pop 후 2) 반복 3) '('는 push 4) ').. [C++] 순열과 조합 DFS로 구현해보기 코딩 테스트를 준비하면서 느낀건데 최종 보스는 DFS와 dp인 것 같다. 생각하기는 어려운데 굉장히 직관적이랄까.. 백준 문제를 풀다가 조합이 꼭 필요한 문제가 있었는데 조합을 구현할 줄 몰라서 이 글을 쓰게 됐다. 조합을 먼저 구현한 뒤에 순열을 구현해 보겠다. 둘 다 재귀를 이용한 DFS로 구현한다. 1. 조합 그냥 직관적으로 생각해보자. 크기가 5인 배열 {4, 2, 1, 3, 5}에서 3개를 뽑는 5_C_3의 경우를 예로 들어보자. 첫번째 숫자부터 차례대로 뽑았다가 3개를 다 뽑으면 다시 되돌아오고 다음 숫자를 뽑을 것이다. 말로 하면 헷갈리니 그림으로 보자. 5가지 경우의 수까지를 살펴보면 아래와 같다. 우선 조합에서는 각 경우의 수 마다 '한 번 뽑으면 다시 쳐다볼 필요가 없다'가 중요.. [C++] Next Permutation, Prev Permutation 파헤치기 1. Next Permutation 알고리즘 문제를 풀다 보면 라이브러리의 next_permutation 함수를 쓸 일이 많다. 문득 이 함수의 원리가 궁금해서 이 글에 정리해보려고 한다. Next permutation의 기본 원리는 오름차순을 내림차순으로 변경하는 것이다. 변경하는 과정에서 모든 가능한 조합이 나오게 된다. 단, 수열은 사전에 오름차순 정렬되어 있어야 한다. Next_permutation의 과정을 살펴보면 아래와 같다. Next Permutation 과정 1. find max(k), a[k] < a[k+1] 2. find max(m), a[k] < a[m] && k < m 3. swap(a[k], a[m]) 4. reverse(a[k+1:]) [1, 2, 3, 4, 5]를 수동으로 한 .. [C++] 최소비용신장트리 - kruskal 알고리즘 최소비용신장트리는 순환하지 않는 최소 비용의 경로를 의미한다. kruskal 알고리즘은 그리디 알고리즘이며 합집합 찾기가 이 알고리즘의 핵심이다. 사실 알고리즘 자체는 굉장히 간단하다. 아래의 세 단계만 거치면 된다. 1. 비용을 기준으로 오름차순 정렬한다. 2. 순환하지 않도록 최소 비용순으로 노드를 선택한다. 이때 Union-Find 알고리즘을 사용한다. 3. 모든 노드를 선택할때까지 2번을 반복한다. 사실 합집합 찾기만 알면 너무 간단한 문제라서 크게 설명할 건 없다. Edge 클래스를 정의해 주고 연산자 오버로딩만 해주면 된다. 그 외에는 위의 세 단계만 코드로 구현하면 된다. 코드가 이해가지 않으면 Union-Find 파트를 다시 읽어보자. 아래 코드는 '프로그래머스 - 섬 연결하기' 문제 .. 이전 1 2 다음
