반응형 분류 전체보기158 [백준 30106] 현이의 로봇 청소기 문제 출처 : https://www.acmicpc.net/problem/30106 DFS나 BFS를 활용하여 풀 수 있는 플러드 필 문제 입니다. 하지만 DFS로 풀었을 때에는 시간초과가 발생했습니다. 같은 로직의 BFS로는 시간초과 없이 통과 되었습니다. 파이썬으로 문제를 풀 때에는 DFS보다는 BFS로 문제를 해결하는 습관을 들이는 것이 좋을 것 같습니다.문제 이해하기이 문제가 다른 플러드 필 문제와 다른 점은 연결이 되어있지 않아 여러 구역으로 나누어지는 것이 아니라 높이로 인해 건너갈 수 없어 여러 구역으로 나누어진다는 사실 입니다. 따라서 높이의 차를 통해 연결 여부를 따져야 합니다.코드 작성하기그럼 코드를 작성해 보겠습니다.입력 받기mii = lambda : map(int, input().sp.. 2024. 5. 7. [백준 25381] ABBC 문제 출처 : https://www.acmicpc.net/problem/25381 A와 B를 지우는 방법을 시행 1이라고 하고, B와 C를 지우는 방법을 시행 2라고 하면 결국 B가 이 문제의 핵심 입니다. 시행 1을 실행함으로 시행 2를 실행 못하는 경우가 생기고, 시행 2를 실행함으로 시행 1을 실행 못하는 경우가 생기기 때문 입니다.DP로 생각할 수도 있지만 문자열의 길이가 30만 이나 되기 때문에 DP로는 해결할 수 없습니다. 좀 더 생각해보면 그리디로 문제를 해결할 수 있습니다.문제 이해하기결국 B의 개수가 문제 입니다. 시행 1과 시행 2 모두 B를 포함하기 때문에 A와 C가 아무리 많다고 하더라도 B의 개수 이상을 만들 수 없습니다. 따라서 시행 1이 가능한 개수와 시행 2가 가능한 개수를 .. 2024. 5. 4. [백준 2776] 암기왕 문제 출처 : https://www.acmicpc.net/problem/2776 수첩 1에 있는 정수가 수첩 2에 있으면 1을, 없으면 0을 출력하는 문제 입니다.문제 이해하기수첩 1의 순서가 중요한 것이 아니기 때문에 수첩 1을 정렬한 다음, 수첩 2의 숫자로 이분탐색을 하여 결과를 출력하면 됩니다.이 방법보다 더 쉬운 방법은 수첩 1을 set 자료구조로 저장하여 찾는 것입니다. 간단한 문제이기 때문에 이분 탐색, set 두 가지 방법 모두 해보겠습니다.코드작성이분 탐색의 입력부터 알아보겠습니다.입력 받기mii = lambda : map(int, input().split())T = int(input())for _ in range(T): N = int(input()) arr = list(mii.. 2024. 5. 3. [백준 2295] 세 수의 합 문제 출처 : https://www.acmicpc.net/problem/2295 집합에 포함된 세 수를 더한 결과가 집합 내에 있는 가장 큰 수가 되는 경우를 찾는 문제 입니다. 세 수 x, y, z와 그 결과로 가장 큰 수 k를 찾아야 합니다. 이 때 꼭 기억해야 하는 부분은 x, y, z, k의 값이 서로 같아도 된다는 부분 입니다. 저는 세 수가 같을수는 없다고 생각하고 아무리 풀어도 틀리다고 나와 문제를 다시 제대로 읽어보니 숫자가 중복되어도 상관 없다는 부분을 찾을 수 있었습니다. 저와 같은 실수를 하지 마시기 바랍니다.아이디어세 개의 수를 더하기 때문에 시간복잡도가 높을 것으로 생각이 듭니다. 하지만 조금만 더 생각해보면 시간복잡도를 줄일 수 있는 아이디어가 있습니다. 우리가 구해야 하는 공식.. 2024. 5. 2. [백준 2512] 예산 문제 출처 : https://www.acmicpc.net/problem/2512 렌선 자르기 문제와 비슷한 느낌이 드는 문제 입니다. 다빈치코딩 알고리즘에 넣기에는 중복적인 내용이라 블로그에 추가하였습니다.문제 이해하기예산이 낮은곳은 그대로 두고, 예산이 높은곳만 줄여나가며 총액보다 작게 만드는 문제 입니다.이 문제는 일반적인 이분 탐색 문제와 다른점이 있습니다. 바로 예산을 증액할 필요는 없다는 것입니다. 예산의 총액이 신청한 예산보다 크다면 더이상 예산을 늘릴 필요 없이 최대값을 출력하면 됩니다. 이 부분만 주의하면 문제를 해결할 수 있습니다.코드 작성그럼 코드를 작성하며 문제를 해결해 보겠습니다.입력 받기N = int(input())arr = list(map(int, input().split())).. 2024. 5. 1. [백준 18185] 라면 사기 (Small) 문제 출처 : https://www.acmicpc.net/problem/18185문제 이해하기라면을 최대한 싸게 사면 되는 문제 입니다. 1개를 살 때에는 3원, 2개를 살 때에는 5원, 3개를 살 때에는 7원을 주고 사야 합니다. 최대한 많이 사는 것이 이득이기 때문에 그리디로 문제를 해결할 수 있습니다.하지만 그리디 문제는 반례를 찾기가 힘듭니다. 반례를 잘 찾아 문제를 해결해야 합니다. 반례는 3개를 살펴볼 때 나오는 것이 아니라 4개 이상일 때 발생 합니다. 라면이 위와 같이 있다고 하겠습니다. 그리디 알고리즘으로 한꺼번에 많이 사는것이 이득이기 때문에 처음에 3개를 사보겠습니다.3개를 한꺼번에 샀기 때문에 3 * 7 로 21의 돈이 들었습니다. 그리고 2번째 2개, 4번째 3개가 남았습니다. 각.. 2024. 4. 29. [백준 13023] ABCDE 문제출처 : https://www.acmicpc.net/problem/13023 A → B → C → D → E 의 관계가 성립하는 그래프가 있는지 확인하는 문제 입니다.깊이 우선 탐색을 이용하여 4단계까지 깊이가 생성된다면 1을 출력하고, 생성되지 않는다면 0을 출력하면 됩니다.문제 이해하기아래와 같은 친구 관계가 있습니다.1번에서부터 친구 관계를 찾아보면 4단계의 깊이를 내려갈 수 없습니다. 2번에서 시작해도 마찬가지로 4단계의 깊이로 내려갈 수 없습니다. 4번이나 5번에서 시작해야만 4단계의 깊이로 내려갈 수 있습니다. 따라서 이 문제는 모든 친구를 A로 가정하고 다 확인해봐야 합니다.코드작성함정이 없고, 이해하기 쉽기 때문에 바로 코드를 작성하겠습니다.입력 받기mii = lambda : map(i.. 2024. 4. 27. 2023년 정보올림피아드 필기 중등부(16 ~ 20) 2023년도 정보올림피아드 1차대회 필기 중등부 16번부터 20번까지 문제 풀이 입니다.이전 문제는 아래 링크 확인 바랍니다.2024.04.23 - [알고리즘 설명/정보올림피아드 필기] - 2023년 정보올림피아드 필기 중등부(1 ~ 5)2024.04.23 - [알고리즘 설명/정보올림피아드 필기] - 2023년 정보올림피아드 필기 중등부(6 ~ 10)2024.04.24 - [알고리즘 설명/정보올림피아드 필기] - 2023년 정보올림피아드 필기 중등부(11 ~ 15) 16번초등부 19번과 같습니다. 아래 링크를 통해 19번 확인 바랍니다.https://davincicoding.tistory.com/138#19%EB%B2%88 2023년 정보올림피아드 필기 초등부(16 ~ 20)2023년 정보올림피아드 1차.. 2024. 4. 26. 2023년 정보올림피아드 필기 중등부(11 ~ 15) 2023년도 정보올림피아드 1차대회 필기 중등부 6번부터 10번까지 문제 풀이 입니다.이전 문제는 아래 링크 확인 바랍니다.2024.04.23 - [분류 전체보기] - 2023년 정보올림피아드 필기 중등부(1 ~ 5)2024.04.23 - [분류 전체보기] - 2023년 정보올림피아드 필기 중등부(6 ~ 10) 11번세 개의 점을 찍고 각각의 간선들이 몇 번 사용 되었나 묻는 문제 입니다. 총 12개의 정점이 있고, 여기서 세 개의 점을 고르기 때문에 총 220의 경우의 수를 가집니다.$$ _{12}C_3 = \frac{12 * 11 * 10}{3 * 2 * 1} = 220 $$220개의 경우에서 각각의 간선들이 사용 되었는지를 따지는 것입니다.그림과 같이 빨간색 간선이 사용되었는지를 알기 위해서는 전체.. 2024. 4. 25. 이전 1 2 3 4 ··· 18 다음 반응형
