반응형 분류 전체보기163 [백준 31963] 두 배 이 문제는 2024 정보올림피아드 1차 대회 초등부 2번, 중등부 1번 문제 입니다. 문제는 아래 링크에서 확인 바랍니다.https://www.acmicpc.net/problem/31963 수열을 오름차순으로 만드는 문제로 앞의 수보다 다음 수가 작다면 두 배씩 커지게 만들어 수열을 오름차순을 만들어 주면 됩니다. 첫 번째 예제를 확인해 보며 문제를 이해해 보겠습니다.3, 1, 4, 1, 5첫 번째 예제의 숫자입니다. 두 번째 숫자인 1은 3보다 작기 때문에 오름차순이 되지 않습니다. 따라서 여기에 2를 곱해줍니다. 2를 곱하면 2가 되어 아직 3보다 작습니다. 따라서 2를 더 곱해주어 4를 만들어 줍니다. 이제 오름차순이 되었기 때문에 다음 숫자를 확인합니다. 세 번째 숫자는 4로 오름차순이기 때문에 .. 2024. 9. 26. [백준 31962] 등교 문제 출처 : https://www.acmicpc.net/problem/31962 이 문제는 2024년 정보올림피아드 1차대회 초등부 1번 문제입니다.문제 이해하기문제의 말이 조금 어렵게 느껴질 수 있지만 결국은 학교에 제시간에 등교를 하면서 가장 늦게 가는 버스를 타고 싶다는 것입니다. S는 버스를 타는데 걸리는 시간입니다. 즉 S가 가장 큰 것이 버스를 가장 늦게 타는 것입니다.다음으로 생각해야 하는 부분이 버스가 정류장에서 학교에 도착하는 시간 T입니다. 학교에 도착하는 시간은 정류장에서 출발하는 시간 S와 학교에 도착하는 시간 T의 합계 입니다. S 와 T의 합계가 X분 이하라면 학교에 제시간에 도착할 수 있습니다.결국 이 문제는 학교에 제시간에 도착하면서 가장 늦게 가고 싶다는 것이기 때문에 S.. 2024. 9. 14. [백준 20437] 문자열 게임 2 문제 출처 : https://www.acmicpc.net/problem/20437 문제 이해하기1. 문자의 개수 파악하기양의 정수 K로 문자열의 길이를 찾는 문제 입니다. 문자는 소문자로 이루어져 있기 때문에 a부터 z까지 총 26개의 문자에 대해 확인을 해야겠지만 K개 이하의 문자는 확인을 하지 않아도 됩니다. 첫 번째 예제의 문자열로 확인을 해보겠습니다.superaquatornado, K = 2위 문자에 대해 K는 2이기 때문에 2개이상 존재하지 않는 문자는 신경 쓰지 않아도 됩니다. 그럼 먼저 각 문자가 몇 개씩 존재 하는지 부터 확인해 보겠습니다.superaqtond12112311211K가 2이기 때문에 2개 이하로 존재하는 이들은 확인할 필요가 없습니다. 여기서 확인해야 할 문자는 u, r, a.. 2024. 7. 28. [백준 5676] 음주 코딩 문제 출처 : https://www.acmicpc.net/problem/5676 세그먼트 트리에 대한 이해가 필요한 문제 입니다. 기본적인 세그먼트 트리에 대해 아직 잘 모른다면 아래 링크를 통해 확인하시기 바랍니다.https://wikidocs.net/209446 06. 세그먼트 트리세그먼트 트리(Segment Tree)는 구간의 합, 구간의 최솟값, 구간의 최댓값등을 빠르게 구할 때 사용합니다. 앞에서 배웠던 누적합과 비슷하다고 느낄 수 있지만 누적합은 합…wikidocs.net 문제 이해하기제목은 음주 코딩이지만 음주와는 전혀 관련 없는 문제 입니다. 주어진 수열이 있고 이 수열의 수들을 곱했을 때 양수가 될지, 음수가 될지, 0이 될지만 확인하면 됩니다.다만 숫자가 너무 커질 것을 대비해서 직접 .. 2024. 6. 15. [백준 28432] 끝말잇기 문제 출처 : https://www.acmicpc.net/problem/28432 문제 이해하기끝말잇기를 하기 위해서 앞의 단어의 마지막 글자와 다음 단어의 첫 번째 글자를 알아야 합니다. 그리고 그 문자가 끝말잇기 리스트에 포함되서는 안됩니다. 여기서 또 한가지 문제는 ?가 맨 처음에 위치할 수도 있고, 마지막에 위치할 수도 있다는 것입니다. 따라서 처음과 마지막일 경우의 처리도 생각하면서 문제를 해결해야 합니다. 우리가 고려해야할 사항을 적어보았습니다.?가 처음에 위치할 경우?가 마지막에 위치할 경우문자중에 ?가 있는지 확인위 세 가지를 고려해서 문제를 해결해 보겠습니다.코드 작성그럼 코드를 작성해 보겠습니다.입력 받기N = int(input())S = []idx = 0for i in range(N).. 2024. 6. 8. [백준 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. 이전 1 2 3 4 ··· 19 다음 반응형