2025년 4월 1일 1. 연구소 (S4) 문제 : 연구소 알고리즘 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, BFS 성공 여부 : 성공(20분) 풀이 : 보류 복기 : 이차원 배열에 벽이 세워져있고, 바이러스가 위치해 있고 세 개의 벽을 추가로 세웠을 때 바이러스로부터 안전한 지역의 크기가 가장 큰 것을 찾는 문제. 세 개의 벽을 무조건 세워야 하므로 dfs로 모든 벽을 세울 수 있는 경우의 수로 place한 다음에 바이러스를 bfs로 퍼뜨려서 정답을 찾았다. dfs 대신 아예 입력받을 때 벽을 세울 수 있는 위치만 저장해 뒀다가 조합으로 푸는 게 더 빠를 것 같긴 하다 2025년 4월 2일 1. 불켜기 (G2) 문제 : 불켜기 알고리즘 : 그래프 이론, 그래프 탐색, BFS 성공 여

2025년 3월 1일 1. 택배 기사 민서 (S2) 문제 : 택배 기사 민서 알고리즘 : 수학, 구현 성공 여부 : 실패 풀이 : 보류 복기 : 실버 2 문제라고 얕봤는데, 의외의 복병이었다. 좌표의 범위가 -10억 ~ 10억이기 때문에 좌표에 대한 각각의 거리를 전부 저장할 수 없다. 따라서 좌표에 따른 거리의 수학적인 규칙을 찾아내야 하는 문제였다. 여기서 수학적인 테크닉이 필요했다. 등비수열의 합 까먹은 거 다시 한번 보기 2025년 3월 4일 1. 가장 긴 증가하는 부분 수열 2 (G2) 문제 : 가장 긴 증가하는 부분 수열 2 알고리즘 : 이분 탐색, LIS 성공 여부 : 성공 (5분) 풀이 : 가장 긴 증가하는 부분 수열(LIS) 복기 : 배열의 범위가 100만이라서 O(n^2) 풀이는 불가

2025년 2월 19일 1. 分 (Minutes) (B5) 문제 : 分 (Minutes) 알고리즘 : 사칙연산 성공 여부 : 성공 (1분) 풀이 : 패스 복기 : 일본어 문제라 당황했지만, 시간 H와 분 M이 주어졌을 때 총 몇 분인지 계산하는 간단한 문제 2. Candy Splitting (Large) 문제 : Candy Splitting (Large) 알고리즘 : 그리디, 비트마스킹 성공 여부 : 실패 풀이 : Candy Splitting (Large) 복기 : Sean과 Patrick이 캔디를 나누는 문제. Patrick은 이진법 연산을 잘하지만 두 수를 더했을 때 remainder를 다음 비트로 옮기는 걸 까먹는다. 이를 이용해 캔디를 두 부분으로 나눴을 때 Patrick이 느끼기에 같은 값이라

0. 들어가며 0.1. 자바스크립트 호이스팅이란 무엇일까? 위 그림은 산업 또는 건설 현장에서 사용되는 호이스트(Hoist)입니다. 주로 엄청나게 무거운 사물을 들어올릴 때 사용되죠. 또한, hoist라는 단어는 ‘끌어올리다’라는 의미를 가지고 있습니다. 자바스크립트만의 독특한 특징 중 하나로 호이스팅 (Hoisting)을 꼽을 수 있습니다. 호이스팅이란 변수나 함수 선언문이 코드의 상단으로 끌어 올려진 것처럼 동작하는 현상 을 말합니다. 호이스팅의 감을 잡기 위해, 일반적인 언어와 자바스크립트에서 동일한 코드를 실행했을 때의 차이를 먼저 살펴보겠습니다. 0.1.1. 일반적인 프로그래밍 언어에서는? 일반적인 언어에서는 선언하지 않은 변수를 사용하면 즉시 오류가 발생 합니다. 예를 들어, 다음과 같은 자

들어가며 현대모비스와 함께하는 편안한 주행 간만에 찾은 재미있는 문제입니다. 문제설명 승환이는 2차원 평면 위에서 (0, 0) → (a, b)로 이동해야 합니다. 승환이는 자동차를 타고 단위길이만큼 움직일 때마다 1의 스트레스를 받습니다. 승환이는 현대모비스 로고가 그려진 간판과의 거리가 1 이하인 곳에서는 스트레스를 받지 않는다고 합니다. 간판은 N개 존재해요. 스트레스를 최소화할 수 있는 경로를 찾자. (-10⁹ ≤ a, b ≤ 10⁹, 0 ≤ N ≤ 2000, 정답과의 절대/상대 오차는 10⁻⁹ 까지 허용) 해설 1. 스트레스를 받지 않는 구간 최소로 하기 먼저 어떻게 하면 스트레스를 받지 않는 구간을 최소로 할 수 있을까를 고민해야겠죠. 먼저 백준에서 제공한 예제를 보면 다음과 같습니다. --

들어가며 공항 완전탐색으로 생각한 풀이를 어떻게 최적화시킬 수 있는지 묻는 문제입니다. i번째 비행기를 1번부터 gi번째 게이트 중 하나에 도킹해, 비행기를 최대한 많이 도킹한다는 뜻은 gi번째 게이트에 도킹하거나 gi번째 게이트에 최대한 가까운 가능한 게이트에 도킹해야 한다는 아이디어를 떠올려야 합니다. 문제설명 1부터 G까지의 번호를 가진 게이트가 있을 때, P개의 비행기가 순서대로 도착합니다. 이 때, i번째 비행기를 1번부터 gi(1 ≤ gi ≤ G) 번째 게이트 중 하나에 영구적으로 도킹하려고 합니다. 순서대로 도착하다가 더 이상 도킹할 수 없을 때, 공항이 폐쇄됩니다. 최대 몇 대를 도킹시킬 수 있을까요? 해설 앞서 ‘들어가며’에서 설명한 것처럼 비행기를 최대한 많이 도킹하기 위해서는 gi번째

들어가며 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence; LIS)은 DP로 풀 수 있는 유명한 문제 유형 중 하나입니다. 문제의 핵심은 주어진 시퀀스에서 오름차순으로 정렬된 가능한 가장 긴 부분 수열을 찾는 것 입니다. 참고로 답이 되는 부분 수열은 꼭 하나가 아니라 여러 개가 될 수도 있습니다. 이 문제를 푸는 방법은 크게 두 가지가 알려져 있습니다. DP로만 풀기 와 DP + 이분탐색으로 풀기 입니다. 각각 O(n²)와 O(n log(n))의 시간복잡도를 가집니다. n이 작으면 전자의 방법으로도 충분할 수 있지만 n이 더 커지면 힘들겠죠. 풀어볼 문제는 가장 긴 증가하는 부분 수열5 입니다. 문제는 아주 짧고 명확합니다. 예를 들어 수열 A가 A = {10,

들어가며 이중우선순위큐 힙을 이용한 대표적인 테크닉인 이중우선순위큐 문제입니다. 문제설명 이중 우선순위 큐란 숫자를 삽입하는 insert연산, 그리고 최댓값/최솟값을 제거하거나 리턴하는 delete_max_value/delete_min_value연산을 할 수 있는 자료구조입니다. 최대 1,000,000개의 연산이 주어졌을 때, 모든 연산을 처리한 후 큐가 비어있으면 [0, 0], 비어있지 않으면 [최댓값, 최솟값]을 리턴하는 solution함수를 구현하세요. 해설 이중 우선순위 큐는 다음과 같은 개념을 알고 있으면 풀 수 있습니다. 힙 자료구조 Max-Heap, Min-Heap 두 개의 힙 사용하기 lazy하게 처리하기 힙 자료구조 먼저 힙 자료구조는 최댓값, 최솟값을 빠르게 찾아내기 위해 고안된 완전이

들어가며 Candy Splitting (Large) 솔브드에서 제공하는 랜덤 마라톤에서 나온 문제입니다. XOR 연산에 대한 이해가 있어야 풀 수 있는 문제였습니다. 문제설명 형제 Sean과 Patrick은 부모님으로부터 캔디가 든 가방을 받았습니다. 가방 안에는 값이 다른 여러 개의 캔디가 들어있는데, 이를 공정한 방법으로 나누려고 합니다. Sean이 두 더미로 나누면 Patrick이 둘 중 하나를 골라 가져가는 방식이죠. 불행하게도 Patrick은 너무 어려서 캔디의 값을 올바르게 더하는 방법을 모릅니다. 대신 이진법 덧셈을 거의 할 줄 아는데, 올림을 까먹었습니다. 예를 들어, 12(1100), 5(101)이 있을 때 올바른 덧셈 결과는 17(10001)이지만, Patrick의 방식으로는 9(1001)

들어가며 배낭 문제(Knapsack Problem)는 조합 최적화 문제의 기본적인 문제 유형으로 동적 계획법(DP)을 이용해 풀 수 있습니다. 코딩 테스트에서 배낭 문제 혹은 냅색이라고 하면 바로 이 유형이구나 생각하면 됩니다. 배낭 문제의 핵심은 각각 가중치(Weight)와 가치(Value)를 가진 집합이 주어졌을 때, 총 가중치의 한계 내에서 유지하면서 총 가치가 가장 커질 수 있도록 어떤 원소를 포함시킬 것인지 결정하는 것 입니다. 쉽게 말해 10kg 용량 배낭에 [5kg, 5만원, 신발], [6kg, 4만원, 패딩], [4kg, 3만원, 속옷]이 있을 때 어떤 것들을 가져가야 용량에 넘치지 않으면서 최대 가치를 챙길 수 있는지 찾는 것입니다. 위 예시에서는 신발과 속옷을 챙기는 것이 8만원으로