문제 [BOJ 17143 : 낚시왕] 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 흔히 말하는 맞왜틀을 방지하기위해서 문제를 풀기전에 읽고 해설하는데 시간을 쏟는 연습을 하고 있습니다. 그럼에도 불구하고 원트라이에 풀지 못하였는데, 어디서 막혔었고..

개발자가 왜 컨테이너 기술을 알아야 할까? 개발자 혹은 개발자를 하고자 공부하는 모든 사람들은(이하 개발자) 인프라를 알아야할까요? 제 대답은 "알아야 한다" 입니다. 개발자들마다 환경이 다르고 하고자하는 것이 다르기 때문에 감히 모든 개발자라고 말하기 어려울 수 있으나, 역설적으로 개발자마다 환경이 다르고 하고자하는 것이 다를수록 컨테이너 기술을 사용해야 합니다. 이전까지 혹은 지금도 인프라 엔지니어는 데이터 센터나 서버실이 있어서 직접 서버를 두고 관리하는 온프레미스(On-premise)방식에서 네트워크나 환경 구축등을 담당하고 있습니다. 그러나 온프레미스 방식에서는 모놀리식(Monolith) 방식으로 모든 애플리케이션, 서비스를 묶어서 관리해왔습니다. 따라서 하나의 서비스를 수정하기 위해서 모든 서..

개념 가지치기(Pruning)는 탐색 과정에서 필요없는 과정을 줄여 최적화 시키는 것입니다. 단편적인 예를 들면, 탐색한 값들 중 최솟값을 구하는 문제에서 현재까지 탐색한 결과값보다 값이 커질 경우 더이상 탐색하지않고 종료하는 것이 가지치기입니다. 위 사진*은 특정 방법으로 노드 하나하나 탐색하고 있을때, 결과의 최솟값을 구해야하는 문제에서 모든 곳을 탐색한 경우의 수라고 가정해보겠습니다. 이 문제의 답이 빨간색 노드가 가지고있는 값이 최솟값이라고 하고 파란색 노드가 빨간색 노드의 값보다 커지는 위치라고 했을때, 위처럼 모든곳을 탐색할 필요가 있을까요? 파란색 노드 아래로는 탐색하지 않아도 적어도 최솟값이 아니란걸 알 수 있습니다. 따라서 탐색하지 않고 종료하는것이 가지치기 입니다. * 설명을 위한 사진..

목표 부분집합의 원소를 구할 수 있다. 부분집합의 개수를 구할 수 있다. 이번 부분집합에서는 위 두가지 목표에 대해 조합을 통한 구현과 bitmask를 통한 구현을 알아보겠습니다. 구현 RecursiveSubset 첫번째는 조합을 이용한 풀이인데, 조합에 대한 코드나 지식이 부족하다면 여기를 참고하세요. 부분집합은 " 멱집합(개수) = nC0 + nC1 + nC2 + ... nCr + nCr+1 ... + nCn" 와 같은 성질을 가지고 있습니다. 조합 함수에 파라미터로 r을 넘겨주면 쉽게 구할 수 있습니다. void Comb(int idx, int curr, int r) { if (idx == r) { for (int i = 0; i < r; ++i) cout

개념 서로 다른 n개의 수 중에 r개를 선택 nCr = n! / (n-r)! * r! 리스트를 순서에 상관없이 수를 뽑는 것입니다. 사실 완전탐색으로 풀리는 문제가 있지만 많은 문제들이 그렇지 않습니다. 그럴때 최적화를 하여 답을 도출해 내는것이 중요한데, 최적화하기 앞서서 기본 뼈대가되는 탐색인 조합탐색을 알아보도록 하겠습니다. 구현 재귀 호출을 이용해서 조합을 구성하기 위해서는 네가지 파라미터가 필요합니다. nCr에서 n nCr에서 r 기저 조건을 위한 idx 어느곳을 탐색할지 정하는 curr 그러나 n과 r이 고정되어 있다면 idx와 curr만 사용할수도 있습니다. 이처럼 재귀 호출은 변형에 용이합니다. 그리고 아래와 같은 배열 2가지가 필요합니다. 나열한 수를 담을 배열 나열되어져야 할 수를 담은..

문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 해설 단순구현 시뮬레이션 문제입니다. 문제의 조건을 간단히 정리하자면 아래와 같습니다. 공기청정기는 첫번째 열에서 2행을..