Algorithm

1. Quick sort 분할 정복 테크닉을 사용한 매우 빠른 시간 복잡도를 가진 정렬 알고리즘이다. 정렬 로직 수행 간 초기 정렬 상태를 보장하지 않는 불안정 정렬이다. 추가 메모리 공간을 필요로 하지 않는다. 시간 복잡도 : O(NlogN) Quick sort의 로직 동작 과정 주어진 배열의 범위 내에서 하나의 값(Pivot)을 기준으로 정하고, pivot 왼쪽에는 pivot보다 작은 값들이 오른쪽에는 pivot보다 큰 값들이 오도록 정렬한다. pivot을 기준으로 나뉜 배열은 정렬된 순서는 보장하지 않기 때문에 각각 배열에서 새로운 pivot을 설정하여 다시 분할해서 재귀 호출 한다. 1,2번의 과정을 배열을 분할할 수 없을 때 까지 반복한다. Quick sort 장/단점 장점 - pivot과 거리..

1. 위상정렬이란? 순환하지 않고 방향이 정해져있는 그래프의 노드를 거스르지 않은 상태로 정렬하는 방법. 비순환 유향 그래프에서만 사용할 수 있으며 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저오는 순서로 정렬이 된다. 시간 복잡도 : O(V+E) {Vertex : 노드의 갯수 / Edge : 간선의 갯수} 2. Default Logic 위상정렬을 하는 방법에는 BFS를 사용하는 방법과 DFS를 사용하는 방법이 있는데 나는 BFS로 설명할 것이다. 먼저 BFS를 사용한 방법을 말로 설명해 보자면 1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수) 2. 한 간선을 처리한 후 inDegree를..

1. 개요신입 개발자로 취업하기 위해서는 코딩테스트는 거의 필수인 듯하다. 처음 시작할 때 백준 티어 기준 브론즈 5에서 현재 골드 1까지 올라오고 나서 회고 겸 처음 시작할 때 뭐부터 어떻게 해야 할지 정말 모르겠는 알고리즘 공부에 대해서 정리해 볼 것이다. 이 글은 지극히 주관적인 기준이며 알고리즘 및 코테 공부를 하는데 하나의 작은 기준?으로만 생각하고 각자 자신에게 맞는 공부법을 찾길 바란다.2. 알고리즘 공부 방법1. 약 30분 ~ 1시간 정도 시간을 정해놓고 그 시간을 넘겨도 못 풀면 구글링으로 다른 사람이 푼 코드를 보고 공부한다. 2. 풀이를 보고 복붙 하지 말고 이해하고 찾아보며 직접 따라 쳐본다. 백문이 불여일타 > 그냥 복붙 하면 살 뺀다고 하고 운동 유튜브 보고 운동했다고 하는 거랑..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 1. Logic - 해당 문제에서 시간이 거꾸로 가는 경로인 웜홀이 존재한다고 하였다. 이건 음수 간선을 나타내는 말이기 때문에 그래프 최단거리 알고리즘 중에서 음수가중치가 있을 때 사용할 수 있는 방법인 벨만-포드 알고리즘을 사용해서 풀이할 수 있다. 원래 벨만 포드 알고리즘은 V(노드의 갯수)-1만큼 순회하며 모든 간선을 확인하며 최단거리를 구하는 방법이다. 이 문제에서는 음수싸이..

1. 다익스트라(Dijkstra) 란? 다익스트라 알고리즘이란 하나의 그래프에서의 최단 경로 탐색 알고리즘이며, 우리가 흔히 알고있는 동적계획법 즉 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 한 정점에서 모든 정점까지의 최단거리를 구할 때 사용하며, 주어진 그래프중에서 음의 가중치가 없는 그래프에서 사용 가능하다. 음의 가중치가 있을 경우 벨만-포드 알고리즘을 사용하여 해결할 수 있다. 2. Default Logic 다익스트라 알고리즘 동작 반복 과정 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. 2. 현재 위치한 정점을 거쳐 다른 노드로 넘어가는 가중치 값을 계산하여 최소 비용을 갱신한다. 3. 위의 과정을 목표한 노드에 도달 할 때까지 반복한다. 이해를 돕기 위해..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. Logic 음수와 양수가 섞여있기 때문에 먼저 오름차순으로 정렬을 한다. 두개의 포인터중 하나는 음수에서부터 하나은 양수에서 부터 서로 끝과 끝에서 가운데로 모이는 방식으로 투포인터를 적용한다. 2. Code #include using namespace std; const long long INF = 1e12; vector ans(2); vector vec;..

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. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. 해당 문제는 투포인터를 설명하면서 똑같이 풀이해놨으니 투포인터를 잘 모른다면 다음 글을 참고하면 좋을 것 같다!..

1. Two pointers 란? 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 치리하는 알고리즘 보통 알고리즘에서 엄청나게 많은 입력들 중에서 원하는 값을 찾거나 반복문을 사용했을때 시간복잡도가 터지는 경우에 사용. 시간 복잡도 : O(N) || 매 과정에서 인덱스를 옮기는데 무조건 1씩 증가하고 항상 start m (현재 부분합이 우리가 원하는 부분합보다 클 때) - sum -= vec[start] (start인덱스의 값) - start 증가 글로는 이렇게 표현할 수 있지만 직접 그림으로 보자 Testcase 10 4 5 1 3 5 10 7 4 9 2 2 end == 2가 됐을 때 구간합과 원하는 Value가 일치하게 된다. 그리고 이후에 원하는 Value 값이 나왔기때문에 end..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. Logic - 처음엔 dp테이블을 2차원이라고 생각했지만 인덱스 갯수가 1500000이기 때문에 dp table이 2개가 아닌 한개라고 생각했다. - 부분문제를 쪼개봤다 1. 해당 날짜의 상담을 할때 - idx + 상담에 필요한 시간 + 상담으로 받은 상담비용 2. 해당 날짜의 상담을 안할때 - 상담을 안하고 다음 인덱스로 넘어가기 2. Code #include using namespace std; int n; vector vec; int dp[1500001]; int solve(int cur) { if(cur == n) ret..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 1. Logic - 카드를 최소한의 점수로 합체하기 위해서는 가장 작은 값끼리 묶어서 합쳐야 하기 때문에 우선순위 큐를 사용해서 가장 앞에 오는 두개의 수를 가지고 계산을 돌려준다! 2. Code #include using namespace std; priority_queue pq; int main() { long long n, cnt; cin >> n >> ..