prefer2 Log

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

문제 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다. 큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가..

다익스트라 알고리즘? 한 정점에서 다른 정점까지의 최단경로를 구하는 알고리즘이다. 각 정점을 최대 한번씩만 방문하여 최단 거리를 정한다. 시작 노드로부터 각 노드까지의 거리를 저장하는 배열을 이용하여 탐색을 진행하면서 현재 누적 최단 거리와 간선의 가중치의 합이 이동하는 노드까지의 저장된 최단 거리보다 작을 경우 값을 업데이트해주며 구하고자 하는 바를 구한다. 다익스트라는 모든 가중치가 음이 아닐때만 사용할 수 있다. 동작 과정 아래 그림과 같은 예시에서 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

문제 수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다. 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다. 수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 ..

인덱스 트리란? 포화 이진 트리 형태의 자료구조로 부모 노드가 자식 노드의 대표값을 가지는 트리이다. 리프 노드에 사용할 값들을 적어놓고, 부모 노드에 값들의 합을 모아놓은 형태이다. 글보다 아래 그림 예제를 보면 쉽게 이해할 수 있다. 언제 사용? 배열 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)으로 ..

문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을..

문제 집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다. 양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가..

문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, ..