정렬된 배열에서 최대와 최소를 잡고 중앙값을 이동시킨다. 그러다 보면 원하는 값이나 위치에서 멈추게 된다. 이것을 이분 탐색(Binary search)이라고 부른다. 기본적인 탐색은 다음과 같이 진행할 수 있다. low = 배열의 시작 인덱스 high = 배열의 끝 인덱스 while(low < high) { 1. low와 high의 중앙값을 찾음. 2. 중앙값이 원하는 수보다 큰지 작은지 판별 3. 큰 경우 : low = mid+1 작은 경우 : high = mid-1 } 탐색이 끝난 후에는 조건을 어떻게 처리했느냐에 따라 답이 저장되는 변수가 달라진다. (그래 봐야 low, middle, high 중이지만...) 하지만 이 테크닉을 실전에서 사용하기 위해서는 약간의 가공(?)이 필요하다. 이것을 매개 ..
본격적으로 최단 경로 알고리즘에 대해 알아보자. 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 3중 for문으로 구현하여 최단 경로를 알아내는 알고리즘이다. 본격적으로 구현하기 전에 몇가지 세팅이 필요한데... 우선 연결 관계를 표현할 배열이 하나 필요하다. 그리고, 자기 자신으로 가는 것은 최단 경로가 0이므로 그대로 둔다. 입력은 두 정점과 가중치가 주어진다. 두 정점이 연결되어 있다는 것을 배열의 [정점A][정점B] = 가중치의 형식으로 나타낸다. 정점들의 연결 관게와 가중치가 모두 처리 되었다면! 자기 자신으로 가는 경우에는 0으로 처리하고, 배열에 저장된 값이 없으면 절대 나올 수 없는 수로 처리해 준다. 이제 본격적으로 플로이드 와샬 알고리즘을 사용해 최단 경로를 구할 건데... 원리는 다음..
최단 경로 알고리즘을 하기 전에 백트레킹을 이용해서 최단 경로를 찾는 코드를 짜 보자! 그래프 용어 그래프에서 사용하는 용어는 다음과 같다. 정점 : 한 지점을 나타낸다. 간선 : 정점과 정점을 연결한 것을 나타낸다. 가중치 간선 : 정점과 정점 사이를 이동하는데 드는 비용이나 힘이 표시된 간선 그래프의 표현 그래프는 크게 2가지로 표현할 수 있다. - 인접행렬 - 인접리스트 배열로 그래프를 구현해 놓은 것을 인접행렬이라고 부른다. 구현은 매우 간단하다. 두 정점의 연결 관계가 입력되었을 때, (vertex1, vertex2)와 (vertex2, vertex1)에 체크 또는 가중치를 넣어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 //인접행렬에 체크하기 while(m--) { int..
이분 탐색은 원하는 값을 찾을 때, 완전탐색보다 더 빠르게 찾을 수 있는 알고리즘입니다. 일반적인 탐색보다는 나중에 매개 변수 탐색에 더 많이 사용되지만, 기본적인 탐색도 알아두면 좋습니다. 먼저 정렬을 해 주는 것이 중요합니다. 그 이유는 중앙값을 기준으로 값을 찾아 나갈 것인데, 정확한 기준이 없다면 중앙값을 어떻게 바꿔 나가야 하는지를 모르기 때문입니다. 그 다음! 양끝 지점을 잡고, 그 중앙값에 따라 판별을 합니다. 이 판별은 두가지 경우로 나뉘게 됩니다. 1. 찾는 값이 중앙값보다 큰 경우 - 작은 지점을 중앙값으로 갱신합니다. 2. 찾는 값이 중앙값보다 작은 경우 - 큰 지점을 중앙값으로 갱신합니다. 이렇게 판별하는 이유는 중앙에 있는 값보다 작다면? 굳이 더 큰 수들을 볼 필요가 없기 때문입..
DFS와 BFS는 그래프 탐색의 기초적인 알고리즘입니다. 이것을 기반으로 구현할 수 있는 알고리즘도 있으니 꼭 알고 있어야만 하는 알고리즘이기도 합니다. 그래프 탐색을 하기 전에 알아두면 좋은 몇가지 용어가 있는데, ( 아래 그림을 참조... ) 정점 : 동그라미 안에 숫자가 있는 것을 정점이라고 한다. 간선 : 정점을 이어놓은 부분을 간선이라고 한다. 1. DFS ( 깊이 우선 탐색 ) DFS는 깊이를 우선으로 탐색하는 알고리즘입니다. 시작 노드와 연결된 것을 쭉 타고가서 더 이상 연결된 것이 존재하지 않을 때까지 탐색을 한 다음에 그 다음 연결된 노드에 이 과정을 반복하며 탐색하는 방법입니다. 다음 그림을 보면, 깊이 우선 탐색을 1부터 진행하여 나오는 결과는 1 -> 2 -> 7 -> 8 -> 9 ..
Two pointers algorithm은 연산량을 줄여주는 효과적인 알고리즘입니다. 주로 원하는 해를 구하는 문제의 연산량 줄이기에 사용되는데, 구현 자체는 그렇게 어렵지 않아서 알아두면 두고두고 쓸 일이 많을 겁니다. Two pointers algorithm은 두개의 지점을 최종 지점으로 움직이면서 몇가지 처리를 하면 원하는 해가 구해지는 형태입니다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net ..
목차 1. Back Tracking의 개념/이해 2. Back Tracking 활용 방향 3. 다양한 Back Track 구현 Back Tracking의 개념/이해 Back Tracking은 최적 값을 찾는데 사용할 수 있는, 글쓴이의 개인적인 의견으로는 제일 쉬운 방법입니다. Back Tracking은 말 그대로 값을 뒤로 추적하는 방법입니다. 기본적인 원리는 DFS를 기반으로 탐색을 진행하고 아니다! 싶으면 다시 돌아가는 방법이자 하나의 기법이라고 생각하면 됩니다. 일반적으로 재귀로 구현하는 것이 정석이고, 그 외의 방법으로 구현하는 것은 아직까지는 보지 못했습니다. Back Tracking을 쉽게 생각하자면 우리가 수학문제 푸는 것과 비슷하다고 생각하시면 됩니다. 우리가 수학문제를 처음 풀 때, 일..
http://koistudy.net/?mid=prob_page&NO=706 -- R&E 가는길 (Tiny) 지금까지 우리는 정점과 간선으로만 이루어진 그래프를 탐색하였다. 여기서 가중치가 포함되면 물론 일반적인 DFS/BFS의 형식을 벗어나지는 못하지만, 또 다른 방법으로 그래프를 해석할 수 있게 된다. 오늘은 Back_track을 이용해 가중치 그래프에서 최소 경로로 도착지점에 도착하는 비용을 구해보자. 목차 1. 지금가지의 그래프 탐색 2. back_track을 이용한 그래프 탐색과 가중치 처리 지금까지의 그래프 탐색 지금까지 그래프 탐색하면 깊이 우선 탐색으로 파고 들어가는 방법을 떠올렸을 것이다. 대표적으로 KOI 문제 중에는 단지 번호 붙이기가 있다. 이러한 것은 그래프 탐색의 한 종류이지만 그..