접근법 문제 유형이 투포인터라는 점과, 수열을 확인하며 각 수열마다 겹치는 원소를 확인하는 방법은 굉장히 비효율적이며, 시간초과가 날 것이라는 생각이 들어 다음과 같이 생각했다. 각 자리에 있는 원소들에서부터 만들 수 있는 조건에 맞는 수열은 중복되는 원소가 나오기 전까지의 수열의 갯수이다. 예로 {1, 2, 3, 4, 3, 5, 6} 을 살펴보자.{1}, {1,2}, {1,2,3}, {1,2,3,4} 가 된다. 이 것은 수열 {1,2,3,4} 의 원소의 갯수와도 같다. 처음 원소인 1에서 만들 수 있는 조건에 맞는 수열은 중복된 원소가 나오는 순간 순열의 처음부터 끝까지 움직이며 어느 위치에 해당 중복되는 원소가 있는지 확인한다. 2-1) 이 과정에서 중복된 원소가 아닌 원소에서도 조건에 맞는 수열들이..
문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 ..
2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입..
문제 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 위 문제와 사실상 동일한 문제, 하지만 이 문제에서는 수 자체를 비교하지 않고 수가 등장한 빈도와..
문제 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..
문제 11502번: 세 개의 소수 문제 정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다. '5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 www.acmicpc.net 풀이 이 문제는 여러 가지 테스트케이스에서 어떤 수가 주어졌을 때, 세 개의 소수의 합으로 나타낼 수 있는지를 확인하는 문제입니다. 그렇다면 우선 소수를 걸러내는 에라토스테네스의 체가 필요할 것이며, 매 테스트 케이스마다 소수를 새로 구하지 않고 한 번만 계산하는 것이 좋아 보입니다. 소수들을 찾았으면 소수들의 합으로 나타내야 합니다. 이는 세번의 for문으로도 충분히 풀리게 되는데 그 이유는 1000까지의 소수의 개수가 16..
