본문 바로가기

코딩테스트 준비

 (35)
코딩테스트를 준비하는 효율적인 방법 IT관련 대기업, 금융권 및 유니콘 기업에 취업하기 위한 코딩테스트 준비는 선택이 아닌 필수가 되었다. 대부분의 기업의 채용 프로세스는 서류 - 코딩테스트 - 면접 순으로 이루어지기 때문에 코딩테스트에 통과하지 못한다면 면접을 볼 수 있는 기회조차 없는 것이 일반적이다. 이 글에서 코딩테스트 준비를 시작하는 학생들에게 가늘고 길게 공부할 수 있는 방법을 제시할 것이다. 그리고 이 방법은 내가 작년부터 코딩테스트를 위해 경험한 내용을 기반으로 한다. 나름 긴 시간동안 꾸준히 문제해결과 알고리즘 공부를 해왔고, 채용 단계에서 PS유형의 코딩테스트에서는 한 곳 빼고 모두 합격했었다. 글을 읽는 사람들에게 나름의 신뢰도를 제시해야 하기에 부끄럽지만 나의 백준 프로필을 근거로 올린다. https://www.acm..
LCS(Longest Common Sequence) 알고리즘 LCS LCS(Longest Common Sequence)는 주어진 수열들에 대해 가장 긴 공통 부분 수열이다. 예를 들어, 두 문자열 BCDAACD와 ACDBAC에 대한 공통 부분 수열들은 다음과 같다. BC, CDAC, DAC, AAC, AC, CD ... 이러한 공통 부분 수열 중에서 가장 길이가 긴 부분 수열은 CDAC이다. LCS는 $Dynamic Programming$을 이용해 접근할 수 있다. 알고리즘 동작 다음과 같은 두개의 수열 $X$,$Y$가 있다. 우선, $n = length(X), m = length(Y)$ 일 때, $(n+1)*(m+1)$크기의 dp배열이 필요하다. 그리고 다음과 같이 배열을 채운다. dp[i][j]는 $X$의 i번째 원소와 $Y$의 j번째 원소까지 봤을 때, 현재..
C++ 백준 13160 (최대 클리크 구하기) 백준 13160 (최대 클리크 구하기) https://www.acmicpc.net/problem/13160 13160번: 최대 클리크 구하기 그래프 이론에서 클리크란, 완전 그래프인 부분 그래프를 의미한다. 즉, 정점으로 이루어진 집합 중 모든 두 정점 사이에 간선이 있는 집합을 의미한다. 최대 클리크는 그러한 집합 중 크기가 가 www.acmicpc.net 클리크란 어떤 그래프내에 존재하는 sub 완전그래프이다. 여기서 완전그래프란 모든 노드가 서로 연결되어있는 그래프를 뜻한다. 설명 문제에서 가져온 그림이다. 직선들을 쭉 나열했을 때 가장 많이 겹치는 부분에서의 포함되는 숫자를 찾으면 되는 것이다. 위의 경우에는 빨간 세로선일때 1 2 4가 겹쳐지면서 가장 많이 겹쳐질 때 이므로 최대 클리크는 1 2..
C++ 백준 16496 (큰 수 만들기) 백준 16496 (큰 수 만들기) https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 간단한 정렬을 통해 풀 수있는 문제였다. 프로그래머스에도 똑같은 문제가 있는데, 프로그래머스에서 풀다가 백준에 똑같은 문제가 있길래 이 문제로 설명을 하겠다. 설명 아이디어는 간단하다. 어떤 문자열 A와 B가 있을 때 A+B가 큰지 B+A가 큰지를 비교해 정렬을 하면 된다. 아이디어는 참 간결하고 구현도 쉬운데 왜 티어가 플래티넘..
C++ 백준 2503 (숫자 야구) 백준 2503 (숫자 야구) https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 간단하게 브루트포스로 해결가능한 문제였다. 처음에 문제를 보고 각 스트라이크와 볼에 대해 경우의 수를 빠르게 줄여볼 방법을 생각했지만 string의 길이가 3이고 전체 수가 1000도 안된다는 점을 보고 그냥 브루트포스로 접근했다. (그래도 0ms가 나오더라..) 설명 설명이라고도 하기 쪼끔 민망하지만 설명해보자면 다음과 같다. 인풋이 세자리 string과 스트라이크,..
C++ 백준 2533 (사회망 서비스 SNS) 백준 2533 (사회망 서비스 SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 친구들간의 관계를 그래프로 표현해서 풀 수 있는 문제였다. 또한 중복되는 연산을 막기위해 DP를 사용하는데 설명에서 언급하겠다. 설명 문제 조건을 보면 얼리어답터가 아닌 사람들의 친구들은 무조건 얼리어답터여야 한다. 또한 얼리어답터가 아닌 사람들의 친구들은 얼리어답터이거나 아니어도 된다. 언뜻보면 이분그래프를 생각할 수 있지..
C++ 백준 1202 (보석 도둑) 백준 1202 (보석 도둑) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 정렬과 우선순위큐를 이용해 풀 수 있는 문제였다. 설명 우선 가방의 크기를 오름차순으로 정렬한다. => 담긴 vector를 bag이라고 하겠다. 또한 보석의 pair를 무게에 대한 오름차순으로 우선순위 큐에 저장한다. => 해당 큐를 jew라고 하겠다. 준비를 마친 후 과정은 다음과 같다. 정렬된 가방의 크기..
C++ 백준 1339 (단어 수학) 백준 1339 (단어 수학) https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 설명 간단한 정렬로 풀 수 있는 문제였다. 각 자리수에 대해 가중치를 두고 그 가중치를 정렬한 뒤에 가중치가 높은 알파벳부터 9~1까지 차례대로 주면 된다. 예시를 살펴보자 ABB CAD 라는 두 수를 합친다고 가정해보자. 그러면 (100+10)*A + (10+1)*B + 100*C + D 가 될 것인데, 수가 가장 크려면 자신앞에 붙은 상수값이 가장 큰 알파벳에..

티스토리툴바