본문 바로가기

Algorithm290

[백준/C++] 크리스마스 선물 (No.14235) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 선물을 가지고 있을 때, 항상 가치가 가장 큰 선물을 줄 수 있도록 구현하면 된다.즉, 가치가 가장 큰 선물이라는 우선순위가 있으므로 priority queue를 이용하면 쉽게 문제를 풀 수 있다. 이를 이용해 아이디어를 정리하면 아래와 같다. [아이디어 정리]priority queue를 이용해 선물의 가치가 가장 큰 게 먼저 나오도록 한다.n이 0일 경우 priority queue에 선물이 있는지 확인하고 선물이 있다면 가장 큰 선물을 준다.만약 선물이 없다면 -1을 출력한다. Code ">Code #include #include #include #include #include #in.. 2024. 12. 26.

[백준/C++] 벌집들 (No. 3805) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 문제 이해를 잘 해야 풀 수 있는 문제였다. 문제를 잘 보면 벌집이 있는 곳들 사이의 경로만 존재하며, 그 경로들 중 하나가 무작위로 문제가 발생한다는 것을 알 수 있다. 즉, (벌집O, 벌집X)인 나무들 사이에는 경로가 없고 오로지 (벌집O, 벌집O)인 나무들 사이에만 경로가 있다는 뜻이다. 여기서 무작위로 하나의 경로에 문제가 생겨도 모든 나무들 사이를 이동해야한다. 이러한 조건을 만족하기 위해서는 내가 벌집을 만든 나무들간의 경로가 사이클을 이루어야 한다는 것을 알 수 있다.(만약 사이클이 아니면 오로지 하나의 경로만 있는 벌집의 경로를 파괴하면 다른 벌집으로 못가는 경우가 생기게 됨).. 2024. 12. 25.

[백준/C++] 다음 팰린드롬 수 (No. 1334) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 구현을 잘하면 쉽게 풀 수 있는 문제다. 잘 생각해보면 앞에서 i번째 수와 뒤에서 i번째 수를 서로 비교하고 그 후 두 수가 다르면 앞에서 뒤에서 i번째 수가 앞에서 i번째 수와 같도록 더해주면 된다. 뒤에 있는 수에 더해주는 이유는 당연히 뒤에 있는 수가 커지는게 앞에 있는 수가 커지는 것 보다 작은 수가 만들어지기 때문이다. ex) 102 인 경우 앞에 1을 더한 202와 뒤에 9를 더한 111을 비교해 생각하면 이해가 쉽다. 만약 앞에서 i번째 수가 2고 뒤에서 i번째 수가 1이라면 뒤에서 i번째 수를 1 더해 2로 만들어 주면 된다.반대로 앞에서 i번째 수가 1이고 뒤에서 i번째 수가.. 2024. 12. 16.

[백준/C++] 급상승 (No. 23978) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 상승시켜야하는 코인 가격의 최소를 구하는 문제다. 그러므로 코인의 가격을 C라고 하면 가격이 C일 때 현금화 했을 때 가격이 K보다 크거나 같게 할 수 있는지 판단하면 된다. 이때, 적절한 C를 빠르게 찾기 위해 이분탐색을 사용하면 O(N*log K)로 문제를 해결할 수 있다. 그러므로 범위를 최소 범위와 최대 범위인 st=1, ed=2*10^9로 설정하고 이분탐색을 이용해 적절한 C가격을 찾아나가면 된다. 이때, 코인의 상승가격이 C인 경우 현금화 가격 K가 가능한지 계산하기 위해서는 상승 가격의 기간이 중요하다. 코인이 상승하는 기간의 차이를 A일이라고 하면, 상승가격 C와 A를 비교한다.. 2024. 12. 15.

[백준/C++] PPC 만들기 (No. 31778) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 문제의 규칙만 빠르게 파악하면 쉽게 풀 수 있는 문제다. PPC 부분 문자열을 찾는 것이므로 PPC 부분문자열의 최대 개수를 찾으려면 뒤에있는 P와 앞에 있는 C를 바꾸면 된다. 왜냐하면 C문자열이 등장했을 때, 앞에 나왔던 P의 등장 횟수에 의해서만 부분 문자열의 개수가 정해지기 때문이다. 예를 들어 CCCCCCCCCCCCCCPPC 와 같은 경우 PPC를 만드는 경우 앞에 C문자열이 몇 개가 나오던 현재 C문자열로 만들 수 있는 PPC 문자열에 영향을 끼치지 않기 때문이다. 이때, 빠르게 계산하기 위한 아이디어는 앞에서부터 C를 찾았고 뒤에서부터 P를 찾아서 바꿨으므로 그 위치를 저장해 변.. 2024. 12. 13.

[백준/C++] 합집합 (No. 14411) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 잘 생각해보면 정렬로 쉽게 풀 수 있다. x와 y로 사각형의 크기가 주어지기 때문에 x축과 y축의 길이를 기준으로 내림차순으로 정렬하면 가장 x축이 긴 사각형이 나온다. 그리고 만약 x축의 길이가 같다면 y축의 길이가 가장 큰 사각형이 나온다. 이때, 중요한 점은 x축의 길이를 기준으로 정렬했으므로 y축의 길이가 A인 사각형이 나오면 그 뒤에 나오는 사각형의 y축이 A보다 짧은 경우는 고려하지 않아도 된다는 점이다. 아래 그림을 통해 쉽게 생각해보자 위 그림에서 빨간색 사각형은 파란색 사각형보다 y축과 x축이 짧으므로 고려할 필요가 없게 된다. 하지만 x축이 짧아도 y축이 파란색 사각형보.. 2024. 12. 9.

[백준/C++] 의리 게임 (No. 28424) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 조건 쿼리에 맞게 빠르게 정답을 출력하도록 하면 되는 문제다. 단순히 구현으로 문제를 풀면 술을 먹는 로직에서 100,000*100,000 만큼의 연산으로 시간 초과가 될 수 있다. 이를 해결하기 위해 i번째 사람이 술을 마시고 난 다음 어떤 사람이 술을 마실 수 있는지 빠르게 찾도록 로직을 구현했다. 아래 그림을 예로 들어보자 그림과 같이 마실 수 있는 술의 양이 정해져 있다고 생각하면 1번 사람 이후에 2번과 3번 사람은 더 이상 술을 못 마시므로 바로 4번째 사람의 순서가 되게 된다. 그리고 마지막 사람의 다음 사람은 없으므로 -1을 이용해 뒤에 술을 마실 수 있는 사람이 없다는 것을.. 2024. 12. 2.

[SWEA/C++] DAG 동전 게임 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 설명을 잘 이해해야 쉽게 풀 수 있는 문제다. 먼저 조건을 보면 사이클이 있으며 위상 정렬이 되어있다.이를 이용하면 DFS로 1번 노드부터 시작해 N번노드와 N-1번 노드에 도착하는 경우에 돈을 얼마 미만 갖고 있어야 하는지 파악 할 수 있다. 먼저 그림을 통해 예를 들어 보자. 위 그림과 같은 경우에는 N-1과 N으로 바로 가는 방법이 있다.그러므로 다현의 돈의 비율이 나연의 비율과 같은 1:1 미만이면 무조건 나연이 승리한다는 사실을 알 수 있다. 이번에는 조금 다른 경우를 그려보자 위 그림을 보면 N-1과 직접 연결된 경로가 있으면 가진 돈을 전부 제시해 N-1로 가도록 유도할 수 있.. 2024. 11. 26.

[백준/C++] ChatGPT 만들기 (No. 31911) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 구현만 잘하면 되는 문제다. 각 문자별로 다음에 어떤 문자가 올지 정해지면 이를 이용해 사이클을 찾아 계산하면 된다. 먼저 크게 두가지 경우로 나눌 수 있다. 1. 문자를 반복하면 ']' 로 끝나는 경우2. 문자를 반복하면 계속 사이클이 생성되는 경우 1번의 경우는 ]가 나오면 그 뒤에 모든 문자는 '.' 으로 채우면 된다. 2번의 경우는 사이클이 생성되면 문자 사이클을 찾은 다음 그 문자사이클을 반복하면 된다. 위를 구현하기 위해 문자의 뒤에 어떤 문자가 많이 왔는지 map을 이용해 개수를 셌다.그리고 정렬을 이용해 특정 문자의 뒤에는 어떤 문자가 오는지 계산했다. 예를 들어 [abcdeb.. 2024. 11. 23.

[백준/C++] 줄다리기 (No. 31444) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때 어떻게 풀어야할지 감이 잘 안왔다. 모든 경우를 전부 구하면 2^2000으로 시간이 초과됐고, 우선순위 큐를 이용해 그리디하게 풀어도 동점의 경우 명확하지 않다는 문제가 있었기 때문이다. 고민을 하다 힌트를 보니 이분탐색으로 문제를 풀 수 있겠다는 생각이 들었다. 먼저 두 팀의 팀워크 점수를 A값보다 크거나 같게 만들 수 있는지 검사한다.그러면 같은 팀이 된 사람들의 점수가 A보다 크거나 같아야 하므로, i번째 사람과 j번째 사람의 팀워크 점수가 A보다 작다면 두 사람은 같은 팀이 되면 안된.. 2024. 11. 19.

[백준/C++] 골드바흐흑흙의 추측 (No. 32647) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] A, B사이의 소수들의 합으로 K라는 수를 만들 수 있는지 라는 문제를 보고 처음에 단순히 경우의 수를 계산하면 안되겠다는 생각이 들었다. B-A 하지만, 모든 경우를 직접 계산하지 않고 소수의 합을 Memoization으로 몇 번 나왔는지 계산하면 중복되는 경우가 생기므로 빠르게 계산할 수 있겠다는 생각이 들었다. 예를 들어 2, 3, 5, 7의 소수가 있을 때를 아래 그림을 통해 생각해보자. 이렇게 덧셈을 해가며 계산하면 중복되는 경우가 생긴다.5의 경우 소수 5만 사용하는 경우와 2, 3을 더해 5를 만드는 .. 2024. 11. 13.

[백준/C++] LCS 3 (No. 1958) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 어떻게 풀 수 있을까 고민을 많이 했다.단순한 LCS 와 다르게 3개의 문자열에 대한 LCS를 구하는 문제였기 때문이다. 처음에는 3중 for문을 이용해 a, b, c의 문자열이 같은지 비교하고 LCS를 구해 min값을 출력하면 되는 줄 알았지만, 반례가 존재했다. 그래서 2개의 문자열만 비교하는 방법을 확장해 문제를 풀었다.먼저 a, b, c 문자열의 각 i, j, k번을 비교해보자. 그리고 LCS[i][j][k]를 a_i, b_j, c_k번 문자열까지 비교한 경우의 LCS라고 가정하자. 그러.. 2024. 11. 12.

[백준/C++] 도미노 예측 (No. 17943) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 xor 연산에 대해 잘 알고 있으면 쉽게 풀 수 있는 문제다. xor 연산은 2진법으로 표현한 뒤 두 수를 비교했을 때 같은 자리에 있는 수가 같으면 0 다르면 1로 표현하는 연산이다. 즉, A (xor) A는 같은 수 이므로 모든 자리에 있는 수가 같으므로 값이 0이 된다.또한 A (xor) 0을 연산할 경우 0과 연산했으므로 0은 모든 자리에 있는 수가 0이므로 결과 값이 0이 된다. 이를 이용하면 누적해서 xor을 계산해 둠으로써 쿼리의 연산을 빠르게 해결할 수 있다. 아래 그림을 보며 생각해보자 위 .. 2024. 11. 7.

[백준/C++] 도로 네트워크 (No. 3176) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 먼저 이 문제를 풀기 전에 LCA 2 문제를 풀 수 있다면 이해하는데 도움이 많이 된다. " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 도로 네트워크 문제는 N개의 노드에 대해 N-1개의 간선이 있으며, 다른 도시로 이동할 수 있는 최단 경로가 유일하게 하나 존재한다.즉, 잘 생각해보면 이 그래프는 트리 구조를 이루고 있다는 사실을 알 수 있다. 문제에서 A 도시에서 B 도시로 가는 경우에 최소 비용과 최대 비용을 구하라고 했으며, 경우가 K로 최대 10만이기 때문에 단순 탐색을 반.. 2024. 11. 5.

[백준/C++] 벌레컷 (No. 27651) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 조건을 파악하면 빠르게 풀 수 있는 문제다. 구간은 [머리, 가슴, 배] 이며 조건은 (머리 구간 합 그럼 구간을 크게 [LEFT, CENTER, RIGHT] 로 나눌 수 있다. 이제 이를 이용해 문제를 풀 수 있는데, RIGHT 구간의 값이 정해졌을 때, CENTER의 값이 RIGHT보다 크면서 LEFT 구간이 RIGHT 구간보다 작도록 만족하는 구간 중 가장 큰 인덱스를 찾으면 된다. 즉 그림을 참고하면 위 그림과 같이 표현할 수 있는데 조건을 만족하면서 가장 큰 index를 찾으면 index의 값이 경.. 2024. 10. 31.

이전 1 2 3 4 ··· 20 다음

티스토리툴바