알고리즘 공부

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. 풀이를 보고 복붙 하지 말고 이해하고 찾아보며 직접 따라 쳐본다. 백문이 불여일타 > 그냥 복붙 하면 살 뺀다고 하고 운동 유튜브 보고 운동했다고 하는 거랑..

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

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/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. Testcase 하나를 예시로 들어보면 Testcase 10 4 5 1 3 5 10 7 4 9 2 2 여기서 더해서 4가 되는 연속되는 인..