그래프를 구현하는 방법에는 다양한 접근 방식이 있다. 1. 에지 리스트 : 에지를 중심으로 그래프를 표현 : 열의 갯수를 2개를 두냐, 3개를 두냐에 따라서 가중치가 유무를 표현할 수 있다. : 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다. 2. 인접 행렬 : 행과 열에 그래프 정보를 저장한다.(가령, 1행 2열에 표시하는 것은 1에서 2를 향하는 에지를 나타냄) : 가중치가 없는 경우 1을 저장하지만, 가중치가 있다면 그 값을 저장한다. 3. 인접 리스트 : ArrayList로 그래프를 표현한다. : 가중치가 없다면, ArrayList[5]와 같은 식으로 표현한다. : 가중치가 있다면 각 ArrayList의 값에 노드를 두어 가중치 값을 저장할 수 있다. : 노..
정수론을 제대로 파고자 한다면 그 범위가 만만찮다. 하지만, 코딩 테스트에 나오는 일반적인 유형이라는게 존재하기에 그 대표적인 경우들을 대처할 수 있다. 그 중 많이 쓰이는 것은 유클리드 호제법(확장도 있다)이다. 물론 오일러 피 함수도 간혹 쓰이나 유클리드 호제법에 비할 바는 아니다. 그 이유는 유클리드 호제법이 최대 공약수와 최소 공배수를 구하는 정말 효율적인 방법이기 때문이다. 오일러 피 함수 오일러 피 함수는 1부터 N까지의 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 실제 코딩 테스트에서 사용되는 구현 부분만 짚고 넘어갈 것이기에 간단하게 핵심 원리만 알아보자. 1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 한다. 2. 2부터 시작하여, 현재 배열의 값과 인덱스가 같다면(소수라면) ..
소수란, 1과 자기 자신 이외의 값으로는 나누어 떨어지지 않는 수를 뜻한다. 우리는 이 소수를 구하기 위해서, 통상적으로 2부터 자기 자신 바로 이전이 될 때까지 나누어 떨어지는 지 확인하곤 한다. 하지만, 이러한 방식은 대량의 소수를 구해야 할 때 꽤나 많은 시간 복잡도를 소요한다. 그래서 많은 똑똑한 사람들이 수학적으로 소수를 구할 수 있는 효율적인 방법을 찾아냈다. 그 중 하나가 "에라토스테네스의 체"이다. 에라토스테네스의 체 : 소수의 배수를 소거하는 방법으로 소수를 찾아내는 방법 에라토스테네스의 체를 사용할 때, 시간복잡도는 이중 for문을 사용하므로 O(N^2)이라고 판단할 수 있다. 꽤 많은 것이 아니냐 생각할 수 있는데, 바깥쪽 for문을 생략하는 경우가 많아 실제론 O(Nlog(logN)..
그리디 알고리즘? 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 단, 모든 문제에 무작정 사용하는 것이 아니라 전체 선택지에서 똑같이 적용되는 지 꼭 확인해야 한다. 그래서 그리디 알고리즘을 고려하기 위한 3가지 단계는 다음과 같다. 1. 해 선택 : 현재 상태에서 최선의 해를 선택한다. 2. 적절성 검사 : 선택한 해가 전체 문제 제약 조건에 벗어나는 지 확인한다. 3. 해 검사 : 선택한 해 집합이 전체 문제를 해결할 수 있는 지 확인한다. 못한다면, 다시 해 선택으로 이동한다. 예시 문제를 통해 어떤 방식으로 그리디 알고리즘이 사용될 수 있는 지 알아보자. 그리디 알고리즘 문제 예시 1 11047번: 동전 0 첫째 줄에 N과..
이진 탐색 이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾을 때 효율적인 알고리즘이다. 주요 특징은 대상 데이터의 중앙값과 탐색 대상 값을 비교하고, 데이터 크기를 절반씩 줄이면서 찾는다는 것이다. 정렬된 데이터가 있는 경우, 굉장히 유효하게 사용되는 일반적인 알고리즘이기에 꼭 숙지해야 한다. 이진 탐색의 과정 1. 현재 데이터 셋의 중앙 값을 찾는다. 2. 중앙 값 > 타깃 값인 경우, 중앙 값 기준 왼쪽 데이터 셋에서 다시 탐색한다. 3. 중앙 값 < 타깃 값인 경우, 중앙 값 기준 오른쪽 데이터 셋에서 다시 탐색한다. 4. 이 과정을 반복하다가 중앙 값 = 타깃 값이 된 순간 종료한다. 이진 탐색 문제 예시 1 백준 1920번 문제를 통해서 이진 탐색이 사용되는 간단한 예시를 알 수 있..
DFS와 BFS는 코딩 테스트에서 항상 단골 문제로 출제되는 매우 중요한 알고리즘 중에 하나이다. 이제부터 어떠한 경우에 DFS와 BFS 문제를 적용하여 문제를 풀이 할 수 있는 지 작성해 본다. DFS 깊이 우선 탐색은 그래프 완전 탐색 기법 중에 하나로, 그래프의 시작 노드에서 출발하여, 탐색할 한 쪽 분기를 정해 탐색을 마친 후, 다른 분기로 이동하여 탐색을 하는 알고리즘이다. DFS(깊이 우선 탐색)의 특징 - 재귀 함수로 구현한다.(중요) - 스택 자료구조를 사용한다. 실제 문제 풀이에서 DFS는 재귀함수를 사용하는 경우가 많은데, 이 때 스택 오버플로우를 주의해야 한다. DFS 문제에 대한 유형은 주로, 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제이다. DFS 문제 예시 1..
병합 정렬 분할 정복, 데이터를 분할하고 분할한 집합을 정렬하는 병합 정렬 알고리즘의 정렬 방식이다 특이한 점은 swap을 사용하지 않는 다는 것이다. 여기서 swap이란, 인접한 요소와 비교하여 교환하는 것을 말한다. 그럼 어떤 방식을 사용하길래 swap을 쓰지 않고도 정렬이 가능한 걸까? 병합 정렬의 핵심은 병합이다. 이 과정에서 정렬이 되게끔 재 조합한다는 것이다. 직접 코드를 살펴보며, 어떠한 방식으로 구동되는 지 살펴보자. 병합 정렬 문제 풀이 백준 2751번 문제를 통해 병합 정렬을 구현할 수 있다. 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 ..
잘쓰면 정말 효율적인 퀵 소트 퀵소트의 시간 복잡도는 O(nlogn)이다. 또한 퀵 소트에 대해 제대로 이해만 한다면, 더욱더 빠르게 답을 구하는 것도 가능하다. 퀵 소트의 전반적인 과정에 대해 이해해보자. 1. 피벗을 하나 선택한다. 이 때, 피벗의 부분 배열의 가장 왼쪽을 선택하냐, 중간을 선택하냐, 제일 오른쪽을 선택하냐에 따라서 효율이 다를 수 있다. 2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값과 작은 값을 찾는다. 헷갈린다면, 정렬이라고 생각해보자. 왼쪽에는 작은 값들부터 오른쪽에는 큰 값까지 있어야 한다. 그럴려면, 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾아 바꾸어 줄 필요가 있다. 3. 양쪽에서 찾은 값을 서로 바꾸어 준다. 4. 왼쪽과 오른쪽에서 탐색..
그놈의 정렬 알고리즘을 공부하며 정말 많이 찍먹하였던 정렬 알고리즘. 그만큼 중요하다는 뜻이겠지만, 이제는 그 끝 마무리를 하려한다. 정렬은 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것을 의미한다. 그렇다면 왜 중요한 것인가? 결국은 "효율성"이다. 시간 복잡도가 작을 수록 더 빠르고 효과적인 프로그램을 만들기 쉽다. 정렬에 대한 알고리즘은 이러한 효율성을 증진시키기 위해, 수 많은 똑똑한 사람들이 만들어 낸 것이다. 조금은 과장일 지라도 정렬에 대한 알고리즘을 제대로 사용할 줄 안다면 코딩 좀 하는 개발자가 될 수 있을 것이라 생각한다. 정렬의 종류 버블 : 데이터의 인접 요소를 비교하고, swap 연산을 수행하며 정렬 선택 : 대상에서 가장 크거나 작은 데이터를 찾아가 선택하며..
스택과 큐를 사용한 문제 풀이 일반적으로 스택과 큐하면, 후입 선출과 선입 선출의 개념만 알면 끝 아닌가? 라는 생각을 할 수 있다. 하지만, 개념만 알아서는 되는 것이 아니라 실제로 어떻게, 어떠한 상황에서 사용하는 지 알아야 할 필요가 있다. 그 이전에 자바에서 사용되는 스택과 큐 메서드 용어를 정리해 두자. top : 삽입과 삭제가 일어나는 위치 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek : top위치에 현재 있는 데이터를 단순 확인하는 연산 rear : 큐에서 가장 끝 데이터를 나나냄 front : 큐에서 가장 앞의 데이터를 가리킴 add : rear 부분에 새로운 데이터를 삽입 poll : front부분에 ..
