prefer2 Log

체감상 점점 많은 기업들이 프론트엔드 코테의 경우 javascript로만 문제 풀이 언어를 제한하는 것 같다. 또 몇년 전까지만 하더라도 코테 언어로 javascript를 지원하는 회사들이 정말 유명한 회사 몇곳을 제외하고는 없었는데 플랫폼의 발전과 프론트엔드 분야의 성장(?)으로 대부분 javascript를 지원하고 있다. 물론 프로그래머스로만으로도 충분히 코딩테스트 대비를 할 수 있지만 압도적으로 많은 문제 수와 특이한 형식에 입출력에 익숙해지려면 백준으로의 연습도 필요하다고 생각한다(실제로 몇몇 기업의 경우 백준 형식으로 node.js입출력을 받는다) 개인적으로는 코테를 보며 때려 맞추는 형식을 많이 취한다는 느낌이 들었다. 프로그래머스의 경우 모든 입력값들을 보여주지는 않지만 그래도 몇개의 테스트..

다익스트라 알고리즘? 한 정점에서 다른 정점까지의 최단경로를 구하는 알고리즘이다. 각 정점을 최대 한번씩만 방문하여 최단 거리를 정한다. 시작 노드로부터 각 노드까지의 거리를 저장하는 배열을 이용하여 탐색을 진행하면서 현재 누적 최단 거리와 간선의 가중치의 합이 이동하는 노드까지의 저장된 최단 거리보다 작을 경우 값을 업데이트해주며 구하고자 하는 바를 구한다. 다익스트라는 모든 가중치가 음이 아닐때만 사용할 수 있다. 동작 과정 아래 그림과 같은 예시에서 0번 노드에서 5번 노드로 가는 최단경로를 구하고 한다고 해보자. 최단거리를 저장하는 배열을 모두 INF로 설정해준다. priority queue에는 (노드, 누적거리)를 저장한다. 이 priority queue는 누적 거리를 기준으로 오름차순으로 정렬..

위상 정렬? 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 이론적으로는 비순환 방향 그래프(DAG, Direct Acyclic Graph)에서 그래프의 방향성을 거르지 않고 정점들을 나열하는 알고리즘이다. 예를 들어 A작업이 끝난 후 B작업을 실행할 수 있고, C작업이 끝난 후 B작업을 실행할 수 있다고 할때 작업의 순서는 ACB 또는 CAB가 될 수 있다. 이렇게 정해진 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘을 위상 정렬이라고 한다. 일반적으로 위상 정렬의 결과는 유일하지 않다. 동작 과정 배열에 각 노드들의 진입 차수를 저장한다. queue에는 진입차수가 0인 모든 노드들이 삽입된다. queue의 첫번째 값을 꺼낸다. 이 노드에 연결된 모든 ..

Union Find? Union-Find(혹은 Disjoint Set)은 교집합이 공집합인 집합(서로소 집합)들을 효율적으로 표현하기 위해 만들어진 자료구조이다. 서로 다른 집합을 하나의 집합으로 합치는 Union 연산과 원소가 어떤 집합에 포함되어있는지를 찾는 Find연산으로 이루어져있다. 노드간의 연결관계가 주어졌을 때 그룹 관계를 파악할때 주로 사용한다. 코드 (c++) 초기화 각 노드들이 자기 자신을 부모(parent)로 가지도록 초기화해준다. for (int i = 1; i

인덱스 트리란? 포화 이진 트리 형태의 자료구조로 부모 노드가 자식 노드의 대표값을 가지는 트리이다. 리프 노드에 사용할 값들을 적어놓고, 부모 노드에 값들의 합을 모아놓은 형태이다. 글보다 아래 그림 예제를 보면 쉽게 이해할 수 있다. 언제 사용? 배열 A가 있고 아래 두 연산을 M번 수행해야 하는 문제가 있다고 하자. 1️⃣ 구간 l, r이 주어졌을 때 A[l]+A[l+1]+...+A[r-1]+A[r]을 구해라 2️⃣ i번째 수 A[i]를 X로 바꾸어라 N개의 수가 있다고 할 때 일반적인 방법으로는 1번 연산을 수행하는데는 O(N), 2번 연산을 수행하는 데에는 O(1)이 걸려 결과적으로 시간 복잡도는 O(NM)이 된다. 누적합 배열을 사용해서 풀게 되어도 1번 연산 O(1), 2번연산 O(N)으로 ..

그래프 자료구조의 일종 정점(Node, Vertex)과 간선(Edge)로 이루어져 있음 G = (V, E)로 나타낸다 차수(Degree): 정점과 연결되어 있는 간선의 개수 방향 그래프이 경우에는 In-degree, Out-degree로 나누어서 차수를 계산한다 그래프의 표현 인접 행렬 정점의 개수를 V라고 했을 때 V*V 크기의 이차원 배열을 이용 A[i][j] =1 (i→j 간선이 있을 때, 가중치가 있을 경우 가중치), 0 (없을 때) 공간 복잡도: O(\(V^2\)) 인접 리스트 A[i] : i와 연결된 정정을 리스트로 포함 리스트의 크기는 동적으로 변경할 수 있어야(원칙적으로는 링크드 리스트, c++에서는 vector 사용) 공간 복잡도: O(E) 대체적으로 인접 리스트가 효율적 그래프의 탐색 ..

다이나믹 프로그래밍(동적 계획법) 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 DP → 중복⭕ 분할정복(Divid & Conquer) → 중복❌ 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다(memorization) Overlapping Subproblem(중복되는 부분 문제): 문제를 작은 문제로 쪼갤 수 있다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다 Optimal Substructure(최적 부분 구조): 문제의 정답을 작은 문제의 정답에서 구할 수 있다 int memo[100]; int fibonacci(int n){ if( n 0){ return memo[n]; } memo[n] =fibonacci(n-1) + fibonaccai(n-2); return memo[n]; } } /..

나머지 연산 (A+B) mod M = ((A mod M) + (B mod M)) mod M (A*B) mod M = ((A mod M) * (B mod M)) mod M (A-B) mod M = ((A mod M) - (B mod M) +M) mod M (음수가 나올 수 있기 때문에) 나눗셈의 경우는 성립하지 않는다 최대 공약수(GCD) 유클리드 호제법(Euclidean algorithm) a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) == GCD(b, r) //재귀함수 사용 int gcd(int a, int b){ if( b == 0){ return a; } else { return gcd(b, a%b); } } //재귀함수를 사용하지 않고 int gcd(int a, int b){ wh..