반응형 백준41 [백준 30106] 현이의 로봇 청소기 문제 출처 : https://www.acmicpc.net/problem/30106 DFS나 BFS를 활용하여 풀 수 있는 플러드 필 문제 입니다. 하지만 DFS로 풀었을 때에는 시간초과가 발생했습니다. 같은 로직의 BFS로는 시간초과 없이 통과 되었습니다. 파이썬으로 문제를 풀 때에는 DFS보다는 BFS로 문제를 해결하는 습관을 들이는 것이 좋을 것 같습니다.문제 이해하기이 문제가 다른 플러드 필 문제와 다른 점은 연결이 되어있지 않아 여러 구역으로 나누어지는 것이 아니라 높이로 인해 건너갈 수 없어 여러 구역으로 나누어진다는 사실 입니다. 따라서 높이의 차를 통해 연결 여부를 따져야 합니다.코드 작성하기그럼 코드를 작성해 보겠습니다.입력 받기mii = lambda : map(int, input().sp.. 2024. 5. 7. [백준 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. [백준 1328] 고층 빌딩 문제 출처 : https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 이해하기 빌딩을 왼쪽에서 보았을 때, 오른쪽에서 보았을 때를 가지고 빌딩의 순서를 출력하는 문제 입니다. 어려운 문제이지만 차근차근 생각하면 해결할 수 있습니다. 이 문제를 풀 때에는 모든 빌딩이 바닥에서부터 쏟아오른다고 생각하면 좀 더 쉽습니다. 문제의 예로 나온 N = 5, L = 3, R = 2를 생각해 보겠습니다. 총 5개의 건물이 있고 왼쪽에서는 3개의 빌딩이 보이고,.. 2024. 4. 1. [백준 30090] 백신 개발 문제 출처 : https://www.acmicpc.net/problem/30090 30090번: 백신 개발 평소 정보 보안에 관심이 많은 진흥이는 최근 들어 유행하고 있는 컴퓨터 바이러스에 대한 백신을 개발하려고 한다. 바이러스는 $N$개의 문자열로 이루어져 있다고 한다. 진흥이가 열심히 연구 www.acmicpc.net 이 문제는 제 1회 청소년 IT 경시대회 초등부 B번, 고등부 A번 문제 입니다. 겹치는 문자열을 이어 붙여 가장 짧은 문자열을 만드는 문제 입니다. 예제를 확인해보면 3개의 입력이 주어집니다. RUST, VIRUS, STAND 입니다. 이 3개의 문자를 겹치는 부분을 하나로 만들어 잘 이어주면 VIRUSTAND 라는 문자열이 가장 짧은 문자열이 되고 이 문자열의 길이인 9를 출력하는 .. 2024. 3. 13. [백준 30089] 새로운 문자열 만들기 문제 출처 : https://www.acmicpc.net/problem/30089 30089번: 새로운 문자열 만들기 $T$개의 줄마다 영어 대문자로만 이루어진 문자열 $S$가 주어질 때, 각 줄마다 아래 조건을 모두 만족하는 문자열 $X$를 출력하여라. $X$는 $S$로 시작하여야 한다. $X$를 뒤에서부터 읽은 문자열 $X'$ www.acmicpc.net 이 문제는 제 1회 청소년 IT 경시대회 초등부 A번, 중등부 A번으로 출제되었습니다. 문자열 S가 주어졌을 때 뒤집어도 문자열 S가 나오는 가장 짧은 문자열 X를 출력하는 문제 입니다. 테스트 케이스가 100개 이하이고, 문자열 길이가 20 이하이기 때문에 시간 복잡도에 구애받지 않고 어렵게 생각하지 않고 풀어도 됩니다. 문제 이해하기 이렇게 앞으.. 2024. 3. 12. 이전 1 2 3 4 5 다음 반응형
