본문 바로가기

전체 글

 (147)
백준 7573: 고기잡이 https://www.acmicpc.net/problem/7573 일단 나는 단순하게 생각을 했다. 물고기 위치를 하나 잡아서 꼭짓점으로 잡아서 각각 1,2,3,4 분면을 길이를 조정하는 방식을 하면 쉽게 해결할 수 있을것이라 생각했다.#include #include using namespace std;pair P[101];int N, L, M, ans = 0;int dy[4] = { -1, 1, -1, 1 };int dx[4] = { 1, -1, -1, 1 };bool inRange(int y, int x){ return y >= 1 && x >= 1 && y ey) return cmp(ey, sx, sy, ex, idx); if (sx > ex) return cmp(sy, ex, ey, sx, id..
백준 2957: 이진 탐색 트리 https://www.acmicpc.net/problem/2957 이 문제를 처음 보며 생각해낸건 "각 노드의 자식 노드의 갯수를 구해서 더하면 어떨까?" 란 아이디어였다. 하지만, N이 300000이라서 최악의 경우 O(N ^ 2)란 시간복잡도를 지니기에, 초기의 아이디어를 바탕으로 이것을 어떻게 더 효율적으로 문제를 해결할 지 고민을 했었다. 문득, 나는 이 문제를 어디서 본듯한 느낌이 들었다. 그러자 하나 생각난 개념이 있었는데, 이진 탐색 트리는 배열로 나타낼 수 있다. 그림으로 나타내면 다음과 같다. 일단 서로 다른 값을 넣을 것이고, 늘 정렬되어있고, 랜덤 값에 접근을 해야하니, 말이 배열이지, 실 구현은 Set 사용이 바람직할것이다. 여기서, 이것을 활용해서 값을 어떻게 구현할 것이냐? 이다..
백준 9938: 방 청소 https://www.acmicpc.net/problem/9938 이번 문제는 간만에 구글링의 도움을 받았다. 난이도는 플레티넘 3, 내가 지금까지 푼 문제 중에 어려운 축에 속한다. 일단 내 첫 시도에 대해 얘기하려한다. 문제를 읽었을 때, 분리 집합을 사용해야하는 것은 명백한데, 어떻게 사용을 해야할지 헷갈렸다. 고민 끝에 나는 집합과 배열을 활용하기로 하였다.일단 1과 2를 통해 해당 위치가 비어있으면 그곳에 다음 목적지를 설정한다. 만약 둘 다 비어있지 않다면, 3,4를 거쳐 해당 위치가 속한 집합에서 다음 목적지를 찾고, 목적지와 해당 집합을 합친다. 그 목적지가 이미 동일한 집합이거나, 불가능하면 다음 행동을 한다는 메커니즘이였다. 나는 비어있는 위치는 -1, 불가능은 -2로 정의해 문제를 해..
백준 1069: 집으로 https://www.acmicpc.net/problem/1069 이번에 다룰 문제는 "백준 1069: 집으로"이다 난이도도 있고 풀이도 꽤 재밌는 문제였다.사실 이 문제의 예제가 많은 덕분에 해결 할 수 있었다. 만약 예제가 적었다면, "틀렸습니다"로 도배된 "내 제출" 탭에 절망해서, 구글링으로 풀이법을 검색했을 것 같다. 일단 가장 먼저 떠올린 방법은 "피타고라스의 정리"를 사용해서 현재 위치에서 (0, 0)까지의 최단거리를 구하고, 최대한 점프를 한 뒤, 남은 거리는 걸어가는 방법이였다. 하지만, 신경 써야할 것들이 있음을 깨달았다. 첫째, 점프가 걷는 것보다 느리다면? 이건 단순하게 T가 D보다 많으면 걷는 것으로 분기하면 된다. 둘째, 마지막에 점프를 한번 더하고 되돌아가는 게 빠르는 경우가 ..
백준 17611: 직각다각형 이번에 푼 문제는 https://www.acmicpc.net/problem/17611 17611: 직각다각형이다. 이번 포스트는 다른 글과 다르게 두 가지 풀이법을 제시할 것이다.처음에 내가 떠올린 것은 "스위핑"방법이다. input은 시계 방향으로 제시되니, 인접한 두 개의 점을 하나의 선분으로 바꿀 수 있다.자세히 말하면, X축에 평행한 선분들과 Y축에 평행한 선분으로 나누고, 만약 Y값이 같으면 X축 선분에, X값이 같으면 Y축 선분에 평행한 그룹에 추가하는 방식이다. 이제 스위핑을 할 것인데, 일단 선분 집합을 Sort한다. 이러면 가장 왼쪽에 있는 선분을 먼저 들여다 볼 수 있다. 그 다음 선분을 순회할 것인데, 여기서 나는 최소 우선순위 큐를 사용했다. 이 우선 순위 큐는 지금까지 순회했던 선..
백준 1854: K번째 최단경로 찾기 https://www.acmicpc.net/problem/1854 나는 솔브닥 티어를 "성공인 경우만 보기"로 설정을 해서, 내가 푸는 문제의 티어를 보지 않도록 설정하였다.그런데, 이 문제는 평소와 달리 문제를 처음 봤을 때, 답이 안 떠올라서 솔브닥 티어를 보았다. 그 때, 이 문제가 플레티넘 4란 비교적 높은 티어를 배정 받아서, 내가 풀기엔 힘든 문제라고 단정짓고 다른 문제를 해결했던 기억이 있다. 플레티넘 4 이상의 문제를 자력으로 해결한 경험이 없는 건 아니지만 하나 같이 만만한 문제가 아니여서 넘어갔던 것 같다. 그렇게 시간이 지나고, 해결할 문제를 찾던 도중 이 문제를 다시 마주하게 되었다. 이번엔 맞힌 사람이 많은 것을 보고, 내가 해결할 수 있을것이라 가정을 하고 문제에 임하였다. 문제..
백준 15791: 세진이의 미팅 https://www.acmicpc.net/problem/15791  이 문제와 비슷한 문제인https://www.acmicpc.net/problem/11401 백준 11401: 이항 계수 3는 예전에 해결한 적이 있다. 하지만, 사용된 페르마의 소정리를 완전히 이해하지 않고 넘어갔고, 관련 문제도 안 푼지 오래되어서 오랜만에 관련 개념도 정리하고, 문제도 해결을 해보려한다. 일단 문제 읽고나면 이항 계수를 사용해야한다는 건 그리 어렵지 않게 알수 있다. 왜냐하면 남학생 n명 중에 미팅을 해야할 m명을 골라야하니, 정답은 nCm (mod 1000000007)이란건 금방 알 수 있다. 문제는 n의 값이 최대 1,000,000이라서 내가 이전까지 알던 DP 방식으로는 O(N ^ 2)의 복잡도를 가지기에 이 ..
백준 23829: 인문예술탐사주간 지금까지 나는 아이디어가 필요하거나, 내가 모르는 것을 알게 되었거나 오랜 시간 막혔던 문제 위주로 글을 작성하였다.그런데 이번 문제에서의 아이디어는 금방 떠올렸고, 딱히 모르는 것을 알게 된 문제는 아니다. 문제도 오늘 처음보고, 오늘 풀었다. 그래서 이 코드를 처음 짰을 때는 글을 적을 생각은 없었지만, 디버깅에 생각보다 오랜 시간이 걸렸고, 그 버그조차 너무 사소한 것이라서 반성을 목적으로 적어보려한다. https://www.acmicpc.net/problem/23829 이 문제를 분석하며 떠올린 아이디어는 이분 탐색 + 누적 합이다. 나무의 위치들을 정렬해서, 입력으로 들어온 값을 이분 탐색으로 찾아서, 이 값으로 답을 계산하면 된다. 답은 어떻게 계산하나?나무들의 위치를 차트로 나타낼 때 다음과..

티스토리툴바