본문 바로가기

코딩테스트 파이썬134

10828 스택 파이썬 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다.. 2021. 8. 30.
1158 요세푸스 파이썬 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 처음부터 K번째 사람을 차례대로 pop하는 문제이다. 다만 po.. 2021. 8. 30.
11659 구간합구하기 파이썬(재시도-0) 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 변수 n,m=수의 개수, 합을 구해야할 횟수 arr=숫자 배열 투포인터로 분류되어 있어서 풀려했는데, 유형이 달라서 당황했다. 특정합이 아닌 범위를 주고 구하는 방식이었다. 첫풀이는 인덱스 슬라이싱을 이용한 완전탐색이었다. .. 2021. 8. 27.
동빈북 투포인터 출처: "이것이 취업을 위한 코딩테스트다" 투포인터: 리스트에 순차적으로 접근해야 할 때 2개의 점 위치를 기록하면서 처리하는 알고리즘 1- 특정합 M을 만족하는 부분 수열의 합 구할 때 1: 시작점과 끝점이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 2: 현재 부분합이 M과 같으면 카운트. 3: 현재 부분합이 M보다 작으면 end를 1증가시킨다. 4. 현재 부분합이 M보다 크거나 같으면 start를 1증가시킨다. 5. 모든 경우를 확인할 때 까지 2~4 반복 n=5#데이터의 개수 n m=5#찾고자 하는 부분합 m data=[1,2,3,2,5] count=0 interval_sum=0 end=0 #start를 차례로 증가시키며 반복 for start in range(n): #end가능한 만큼 이동시.. 2021. 8. 26.
동빈북 최단거리 전보 파이썬 문제 어떤 나라에 N개의 도시가 있다. X에서 Y로 향하는 통로가 있으면 X->Y는 보낼 수 있지만 Y->X로는 따로 통로가 있어야 한다. C에서 보낸 메세지를 받게 되는 도시의 총 개수와 도시들이 모두 메세지를 받는데까지 걸리는 시간은 얼마인지 계산하는 프로그램 작성 입력 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다. (1 2021. 8. 25.
동빈북 미래도시 파이썬 문제 방문원 A는 시작점 1번회사에 있고 K번에 있는 사람과 소개팅을 한다고 한다. 그리고 방문원 A는 X 회사로 가야한다. 이 때, 총 N개의 도시와 M개의 도로가 주어질 경우 A가 갈 경로의 최단 거리를 구하라 입력 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다(1 2021. 8. 25.

티스토리툴바