Optimal Solution

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 OFF, OFF -> ON). 현재 전구의 상태와 만들고자 하는 전구의 상태가 주어질 때, 만들고자 하는 전구의 상태로 변화시키기 위해 최소한 몇 번의 스위치를 눌러야 하는지를 구하는 문제이다. 문제를 처음 접했을 때 되게 막막하다고..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 분석 용액들의 특성값이 -10억부터 +10억까지, 오름차순으로 주어진다. 우리는 이 용액들 중 두 용액을 혼합할 것이다. 혼합액의 특성값은 두 용액의 특성값의 합인데, 우리가 찾고자 하는 것은 혼합액의 특성값이 0에 가장 가깝게 하는 두 용액을 찾고자 한다. 문제를 읽고 두 개의 포인터를 사용하는 풀이를 생각했다. 용액들의 특성값이 오름차순으로 주어지기 때문에 가장 왼쪽에는 최솟값이 있..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 문제 분석 1번 정점에서 N번 정점으로 이동해야 한다. 이동할 때는 정점과 정점 사이를 잇는 간선을 타고 이동하는데, 이 간선에는 음수가 아닌 가중치가 부여되며 간선을 통과할 때 가중치만큼의 비용을 지불한다. 1번 정점에서 N번 정점으로 이동하기 위해 드는 최소한의 비용을 찾는 것이 문제이다. 그래프의 간선들이 음이 아닌 가중치를 가질 때, 최소 비용의 경로를 찾는 알고리즘으로 다익스트라 알고리즘을 사용할..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 분석 문제를 보자마자 최근 풀었던 한 문제가 생각났다. 아래에 그 문제를 풀고 작성한 포스트 링크를 첨부하겠다. https://optimal-solution.tistory.com/entry/%EB%B0%B1%EC%A4%80-C-2304-%EC%B0%BD%EA%B3%A0-%EB%8B%A4%EA%B0%81%ED%98%95 [백준, C++] 2304 - 창고 다각형 https:/..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 분석 문제에 대한 설명은 안 해도 될 정도로 문제에 자세히 나와있다. 이 문제를 풀기 위해 나는 BFS를 활용해야겠다고 생각했다. 인접 나라 간 국경을 개방하는 조건이 두 인접한 나라의 인구 차가 L 이상 R 이하이면 국경을 개방하는 것이기 때문에, 인구 차가 L 이상 R 이하이면 BFS를 통해 연합할 수 있도록 조건을 걸어주어 인구 차가 조건을 만족하는 모든 나라들을 "연합"..

https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 문제 분석 문제를 보고 이건 어떤 식으로 풀어야겠구나 (가령 어떤 알고리즘을 사용해야겠구나 !) 라는 생각이 안 들었다. 뭐라 해야하지 ... 어떻게 풀어야할지도 모를만큼 어려웠다는 뜻이 아니고, 이게 뭔가 특별한 풀이가 필요한가 ? 라는 생각이 들었던 ... 그런 문제이다. 다 풀고나서 문제의 알고리즘 분류를 봤는데, '문자열' 과 '슬라이딩 윈도우' 라고 한다. 음 ... 내가 푼 방식이 ..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 분석 삼성 스타일의 문제라고 생각했다. 뭐랄까, 문제 지문이 길고 한 번에 이해하기 쉽지 않아 처음에는 '아 되게 어렵겠다' 하고 겁먹는데, 막상 문제를 분석하면서 '어떤 알고리즘을 사용하면 될까 ?' 를 생각할 이유가 없이 그저 문제에서 시키는대로 구현만 하면 되는, 그런 스타일의 문제이다. 삼성 코딩테스트에서 주로 이런 유형이 나왔던 것 같다 (방금 블로그 작성하며 ..

요새 풀고 있는 백준 문제집이 있다. https://www.acmicpc.net/workbook/view/8708 문제집: IT기업 및 대기업 계열사 코테보면서 비슷했던 문제들(지속적으로 업데이트 중) (ses9928) www.acmicpc.net 뭔가 특정 유형만 반복되는 그런 것도 아니고, 다양한 유형의 문제를 약 80여 개 정도 보유하고 있는 문제집이다. 나는 이 문제집을 정복해보고자 지금 풀어보고 있는데, 특히 대기업 및 IT기업 코딩테스트를 준비하는 입장에서 되게 괜찮은 문제집이라는 생각이 들어 혹시나 내 블로그를 보는 사람이 있다면 ... 추천한다.