반응형 Algorithm280 [프로그래머스/C++] [PCCP 기출문제] 3번 / 충돌위험 찾기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 생각보다 구현이 까다로웠던 문제다.특정 위치에서 로봇들이 서로 충돌하는지 파악하고 그 지점의 수를 더하면 되는 문제다. 다양한 방법이 있겠지만, 기본적으로 로봇이 움직이는 규칙이 있기 때문에 row 위치가 다르면 row방향으로 움직이고 그다음에 column방향이 다르면 column방향으로 이동하는 움직임을 한다. 그러므로 이를 이용해 특정시간에 로봇들의 위치를 파악하면 어느 위치에서 겹치는지 파악할 수 있다. 처음에는 각 r * c * 시간 으로 3차원 vector를 만들어 저장하려고 했다. 하지만, 이렇게 .. 2024. 10. 4. [백준/C++] 계란으로 계란치기 (No. 16987) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때 가장 효율적인 방법이 있을까? 고민했지만 방법이 떠오르지 않았다.그래서 완전 탐색으로 모든 경우를 고려해 계란을 깨는 방법을 선택했다. 이러한 방법이 가능한 이유는 N이 8로 작기 때문에 8^8 = 2^24로 충분히 빠르게 해결이 가능하기 때문이다. 1번 계란부터 차례대로 다른 계란을 치는데 만약 깨져있다면 넘어가도록 코드를 구현했다. 이 과정에서 내구도와 무게가 저장된 vector가 계속 복사되지 않도록 Call by Reference를 이용했다. i번 계란으로 j번 계란을 칠 수 있다면 i.. 2024. 10. 1. [백준/C++] MEX (No. 23820) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 많은 고민을 했다. 잘 생각해보면 조건에서 200만까지만 범위가 정해져있으므로, 정말 최악의 경우 200만 보다 크면서 가장 작은 소수의 범위를 벗어나지 않겠다는 생각이 들었다. 그리고 a_i *a_j로 S집합의 수를 나타낼 수 있으므로, a_i * a_j의 계산 값이 200만 보다 크면서 가장 작은 소수의 범위 k보다 작을 때 까지만 체크를 하면 되겠다는 생각이 들었다. (잘 생각해보면 이때의 시간 복잡도는 약 2,000,000/a_i 를 전부 더한 값이므로 적분하면 시간복잡도가 약 nLo.. 2024. 9. 28. [백준/C++] 동작 그만. 밑장 빼기냐? (No.20159) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 밑장을 뺄 경우 어떻게 수가 분배 되는지를 파악하면 누적합을 이용해 쉽게 풀 수 있는 문제다. 그림을 통해 한번 알아보자 B카드를 받아야 하는 상태에서 밑장을 빼면, A카드를 받고 그 뒤에 z, b, c, d ...카드를 받게 된다.즉, 내가 카드를 받을 순서에서 밑장을 빼면 그때부터 나는 원래 받을 카드가 아니라, 상대방의 카드를 전부 받게 된다. 이를 이용하면 내가 받을 i번째 카드의 밑장을 빼면 내가 원래 받을 i-1번째 카드까지의 합 + 상대방이 받을 i번째 카드부터 N/2번째 카드까지의 합으로 나.. 2024. 9. 25. [백준/C++] 단어 수학 (No.1339) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀 때, 단순 대입을 이용해 재귀로 풀었다.그랬더니 단순히 반복문이 10^10이라 시간초과가 걸렸다;; 다음으로 생각한 방법은 어차피 수가 최대 10개나오므로 가장 앞자리에 많이 나온 자리수를 이용해 정렬하면 풀 수 있겠다는 생각이 들었다. 즉, A라는 문자가 10의 자리에만 2번 나오고 B의 문자가 10의 자리에만 1번 나온다면 당연히 A>B로 수를 대입하는게 더 큰 수를 만들 수 있다는 아이디어다. 문제는 수의 개수가 10개라는데서 반례가 발생했다. 만약 A라는 문자가 10의 자리에 2번 나.. 2024. 9. 24. [백준/C++] 더워! (No. 32360) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가장 빠르게 집에서 약속장소를 도착하는 시간을 찾는 문제므로 BFS로 풀 수 있다. 단지, 일반적인 BFS와 다른 점은 불쾌감 지수가 있어서 불쾌감 지수가 100이상이 되면 더 이상 이동할 수 없는 상태가 된다.그러므로 불쾌감 지수가 100이 되지 않으면서 약속장소에 도달할 수 있도록 불쾌감을 조절하며 가장 빠르게 약속장소에 도착하는 시간을 찾으면 된다. 이제 불쾌감 지수를 고려해 BFS로 문제를 푸는 방법을 생각해보자. 현재 위치의 불쾌감 지수를 B, 시간을 T라고 하고, 앞으로 이동할 위치에 방문한.. 2024. 9. 23. [프로그래머스/C++] [PCCP 기출문제] 4번 / 수식 복원하기 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 크게 어렵지 않지만, 구현이 생각보다 빡센 문제였다. 주어진 수식들 중에 수식의 결과를 알고 있다면, 그 수식을 이용해 N진법이 가능한지 판단하고, 만약 결과를 모른다면 후보군에 두면 된다. N진법이 가능한지 판단하는 방법은 간단하다. 먼저 2~9진법의 수로만 수식이 이루어지므로, A + B = C라는 수식에서 A, B, C를 각각 N진법의 수가 가능한지 판단한다.만약 A, B, C 수가 전부 N진법이 가능하다면, A + B라는 값이 C라는 식과 일치하는지 판단한다. 이렇게 비교해서 만약 A+B=C라면 이 .. 2024. 9. 11. [백준/C++] 합성함수와 쿼리 (No.17435) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 빠르게 해결하기 위해 Cycle이 생기는 순간을 기록해야하나? 의문이 들었다.그런데 아무리 생각해도 Cycle을 판단하는데 시간이 오래 걸릴 것으로 보여 다른 방법을 고민했다. 중간에 다른 사람의 힌트를 보니 DP를 이용해 문제를 푼 것을 보고 해결을 할 수 있었다. 함수를 2^k번 적용한 값을 저장하는 DP를 만들면, DP배열을 이용해 빠르게 계산을 할 수 있다. 함수를 2^k번 적용한 DP배열을 만드는 방법도 간단하다. x라는 수를 2^k번 적용해 x1이라는 수가 나오면, x1을 다시 2.. 2024. 9. 4. [백준/C++] 가장 가까운 공통 조상 (No. 3584) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트리가 주어지면 특정 노드들 간의 공통조상을 구하면 되는 문제다. 처음부터 자식노드와 부모노드를 알려주기 때문에, 두 노드 a, b 의 공통조상을 구하기는 쉽다.왜냐하면 두개의 노드를 따라서 부모노드를 찾아가면 공통 조상들을 찾을 수 있기 때문이다. 여기서 우리는 가장 가까운 공통 조상을 찾아야한다. 가장 가까운 공통 조상을 찾는 방법도 간단하다. 먼저 a 노드에서 출발해 최상위 조상까지 올라가며 어떤 노드가 a 노드의 조상인지 파악한 뒤 방문 처리를 한다.그러면 이제 b에서 출발해 조상을 찾아가며 처음으로 .. 2024. 8. 2. [백준/C++] 문제집 (No. 1766) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 위상정렬을 이용하고, 어떤 경우에 문제를 빨리 출력할지 구분하면 쉽게 해결할 수 있는 문제다. 조건에 따르면 더 쉬운 문제를 먼저 풀 수 있다면 먼저 풀어야 한다.그러므로 1번 문제부터 사전에 풀어야 하는 문제가 몇 개인지 파악한다. 이제 위상정렬을 떠올리면, i번 문제를 풀 수 있는 경우 i번 문제를 풂으로써 i번째를 사전에 풀어야하는 문제들은 사전에 풀 문제가 1개씩 줄어든다는 사실을 알 수 있다. 이를 이용해 for 문으로 1번 문제부터 사전에 풀어야 하는 문제가 0인지 미리 풀어야 하는 문제가 있는지 .. 2024. 7. 15. [백준/C++] 최종 순위 (No. 3665) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 전에 위상 정렬 문제를 풀었었다. 위상 정렬의 특징은 정렬할 때, 특정 노드로 들어오는 간선의 수를 이용하면 노드간의 상대적인 우선 순위를 이용해 정렬을 할 수 있다는 특징이 있었다. 그래서 이 문제도 위상정렬의 특징을 이용해 풀었다. 이 문제의 핵심은 모든 팀의 확실한 순위를 알게 되는지 판단하는 것이다. 확실한 순위를 알기 위해서는 처음에 특정 노드로 들어오는 간선이 0인 노드가 1개여야하며, 서로 다른 팀 간에 우선순위를 확실하게 알아야 하기 때문에 특정 노드에서 출발하는 간선을 하나씩 지울때 마다.. 2024. 7. 8. [백준/C++] 색상환 (No. 2482) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 저번에 풀었던 RGB거리 2와 사실 크게 다르지 않은 문제다"> HTML 삽입미리보기할 수 없는 소스 단지 차이점이 있다면, 저번 문제에서는 가중치를 구해야 했다면, 이번 문제는 경우의 수를 구하는 것이다. 문제의 핵심은 색을 칠하기 위해서 i번째 색을 선택하면 i-1번째 색과 i+1번째 색을 선택할 수 없다는 것이다. 그러므로 i-1번째 색을 사용했다면, i번째 색을 사용할 수 없고 i-1번째 색을 사용하지 않았다면 i번째 색을 사용할 수 ㅣㅆ다는 점을 이용해 N번째 색에 도달할 동안 몇 개의 색을 선택했는.. 2024. 7. 3. [백준/C++] RGB거리 2 (No. 17404) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N번째 집이 N-1번째 집과 N+1번째 집의 색과 다르게 색칠하는 경우 최소의 비용을 구하는 문제다. 단, 1번 집과 N번째 집도 서로 색이 달라야 한다. 즉, 처음과 끝이 연결된 원탁과 같은 경우다. 하지만 처음과 끝이 연결됐다고 해서 크게 어려운 문제는 아니다.처음과 끝의 경우를 고려해 탐색하면 쉽게 풀 수 있는 문제다. i번째 집을 색칠하기 위해서는 마지막에 색칠된 i-1번째 집과 i번째 집의 색이 다르면 된다.그러므로 i번째 집을 R로 색칠하기 위해서는 i-1번째 집을 G, B로 색칠하는 경우만 고려하.. 2024. 7. 1. [백준] Solved.ac 랜덤 마라톤 (No. 6903, 11896, 15410, 11501, 9335, 6207, 2467, 12796) Solved.ac 랜덤 마라톤 풀기 링크 ">HTML 삽입미리보기할 수 없는 소스 문제 + 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 후기] A. Trident (9분)문제 링크" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 간단하게 문제의 조건에 따라 삼지창을 그리면 된다.for문을 이용하면 쉽게 그릴수 있는 문제다. 더보기 구현#include #include #include #include #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); i.. 2024. 6. 28. [백준/C++] 박성원 (No. 1086) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 매우 큰 수를 입력받아 처리를 해야하는 문제다. 이외에도 N이 15로 큰 값이기 때문에 (15!)을 전부 계산하면 시간 초과가 나게 된다. 그래서 이러한 반복을 줄이는 방법은 나머지를 이용하는 방법이다. 예를 들어 아래와 같은 경우를 생각해보자. 그러면 17, 6 순서로 정수를 만드는 경우와 6, 17 순서로 정수를 만드는 경우는 나머지가 1로 같다. 이를 이용하면 176333과 617333의 나머지가 같음을 알 수 있다.(왜냐하면 176과 617의 나머지가 1이였으므로, 333을 뒤에 붙이면 1333 이 .. 2024. 6. 27. 이전 1 2 3 4 5 ··· 19 다음 반응형
