군 생활을 하며 지난 200일동안 백준을 하루에 한 문제 이상씩 풀어왔다.백준이 서비스를 종료한 지금 생각해보면 어떻게 했지 싶다가도, 재미있게 풀었던 기억이 많아서 다시 하라면 다시 할 수 있을 것 같은 마음이 든다. 200일을 달려왔지만 얻은건 백준의 서비스 종료 소식이라서 아쉬운 마음이 있지만, 이것만 얻은 것은 아니다.긴 시간이라면 긴 시간동안 많은 것을 얻었다. 본격적으로 후기를 작성해보기 전에, 대체 그 200일동안 뭘 했는지 한번 끄적여보려고 한다. ※ 스트릭 기준은 solved.ac로 정했다.보직 특성상 밤샘도 있고, 불규칙적인 생활을 해서 00시에 초기화되는 스트릭에는 도저히 맞출 수가 없었다.그래서 06시에 초기화되는 solved.ac 스트릭이 나의 근무 시간이나 군 내 생활 패턴이랑 ..

백준 1113번 - 수영장 만들기문제더보기지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 166616111616661이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다. 자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다. 땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오...

백준 1202번 - 보석 도둑문제더보기세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.입력더보기첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000) 모든 숫자는 양의 정수이다.출력더보..

백준 2169번 - 로봇 조종하기문제더보기NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다. 지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다. 각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.입력더보기첫째 줄에 N, M(1≤N, M≤1,0..

백준 1708번 - 볼록 껍질문제더보기다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을..

알고리즘 분류 : [ 기하학 ]개념볼록 껍질 (Convex Hull) 은 2차원 평면 상에 여러 점에 대해, 나머지 점들을 모두 감싸는 제일 바깥점으로 만드는 볼록 다각형을 말한다.예를 한 번 들어보면,이런 점들이 있을 때, 이런 모든 점을 감싸는 볼록 다각형 (볼록 껍질) 을 찾는 것이다.이 상황만 보고 이 알고리즘의 구조를 간단히 생각해보면, 이렇게 생각할 수 있다.점들의 무리 중 가장 아래에 있는 것을 기준점으로 잡고그 기준점에서 점들이 있는 반대 방향으로 직선을 쏴서시계 또는 반시계방향으로 돌리다가그 직선과 처음 만나는 어느 한 점이 있을 것이다.그렇다면 그 점은 모든 점들 중에 가장 바깥에 있는 점일 것이다.이 작업을 만나는 바깥 점에 대해 모두 실행하면 볼록 껍질을 이루는 점들을 찾아낼 수 있..