2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입..
1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. 이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다. 주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이..
문제 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..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 단순 구현 문제 코드 from collections import deque def solution(priorities, location): answer = 0 priorities = deque(priorities) while priorities: now_printing = priorities.popleft() location -= 1 print(now_printing,location) if len(priorities) > 0 and max(priorities) > now_printing: pr..
