문제 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 [백준] 17298 오큰수 (Python) 문제 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 해당 문제의 입력이 백 developer-jason.tistory.com 위 문제와 사실상 동일한 문제, 하지만 이 문제에서는 수 자체를 비교하지 않고 수가 등장한 빈도와..
문제 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 해당 문제의 입력이 백만 개가 들어올 수 있으므로 O(N)만큼의 시간복잡도로 해결해야 하는 문제. 단순히 각 원소를 접근할 때 마다 오른쪽의 원소와 비교하며 오큰수를 발견 시 이를 출력하게 되면 O(N^2)로 문제 해결이 되지 않는다. 따라서 문제 해결을 위해 다른 방법을 찾아야 했다. 필자는 다음과 같이 생각했다. 1) 오른쪽에 작은 수가 들어오게 되면 해당 수는 쓸모가 없는 수가 되는 것일까 2) 오른쪽에 큰 수가 들어오게 되면 이전 수에도 영향을 미치지..
문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 풀이 첫 시도에서는 replace로 문제를 해결하려고 했다. 하지만 시간 초과가 발생하여 이를 해결하기 위해 stack으로 구현하였다. 코드 word = input() boom_word = input() stack = [] for i in word: stack.append(i) if len(stack) >= len(boom_word) and stack[-len(boom_word):] == list(boom_word): for _ in r..
문제 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 풀이 bfs로 그래프를 탐색하여 그림의 개수와 가장 큰 그림을 찾아내는 문제. 첫 시도에서 Value Error가 발생. input : 1 1 0 이라는 케이스에서 max(cnt_list)에서 에러가 발생하여 예외처리를 했더니 문제 해결. 코드 from collections import deque direction = [(-1, 0), (0, -1), (1, 0), (0, 1)] def bfs(graph, node): queue = deque() queue..
문제 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 풀이 지인들 중 연결고리가 가장 긴 사람을 기준으로 그 길이로 점수를 매기고, 해당 점수가 가장 작은 사람을 회장 선출한다. 다익스트라 알고리즘으로 문제를 해결해도 될 것 같지만, 해당 문제의 입력 크기가 50으로 매우 작으므로 단순하게 그래프로 구현하여 bfs로 가장 연결고리가 긴 사람을 구했다. 코드 from collections import deque def bfs(graph,root,members): queue = deque([root]) fr..
문제 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 틀린 코드 N,M = map(int,input().split()) num_list = [-1]+list(map(int,input().split())) for _ in range(M): start_index,end_index = map(int,input().split()) print(sum(num_list[start_index:end_index+1])) 문제 풀이 처음 이 문제를 단순 구현으로 생각해서 시간초과가 났었습니다. 정수 범위를..
문제 11502번: 세 개의 소수 문제 정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다. '5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 www.acmicpc.net 풀이 이 문제는 여러 가지 테스트케이스에서 어떤 수가 주어졌을 때, 세 개의 소수의 합으로 나타낼 수 있는지를 확인하는 문제입니다. 그렇다면 우선 소수를 걸러내는 에라토스테네스의 체가 필요할 것이며, 매 테스트 케이스마다 소수를 새로 구하지 않고 한 번만 계산하는 것이 좋아 보입니다. 소수들을 찾았으면 소수들의 합으로 나타내야 합니다. 이는 세번의 for문으로도 충분히 풀리게 되는데 그 이유는 1000까지의 소수의 개수가 16..
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 이 문제는 연속된 순열의 합 중 가장 큰 수를 구하는 것입니다. 해당 문제를 접근하기 위해 다음과 같이 가정했습니다. 1. 어떤 한 부분의 연속된 합을 구할 때 앞서 선행된 계산들이 완료되었다. 2. 해당 부분의 가장 긴 연속된 합은 (앞서 선행된 계산 + 현재의 값)과 (현재의 값)을 비교하여 더 큰 값이다. 이 조건들이 만족된다면 가장 큰 연속 합을 구할 수 있습니다. 정답 코드 # 다이나믹 프로그래밍으로 해당 위치까지 도착했을 때의 가장 큰 합을 저장한다. n ..
