Total

[14221] 편의점 (다익스트라)

14221번: 편의점 처음 줄에는 정점의 개수 n, 간선의 개수 m이 주어진다.(2 ≤ n ≤ 5,000, 1 ≤ m ≤ 100,000) 다음 m줄에는 a,b,c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 것이다.(1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000) www.acmicpc.net 분석 각 시작점(편의점)마다 dijkstra 함수를 호출하여 집까지의 최단거리 구해서 비교 : 시간초과 문제에서 구하고자 하는 것은 편의점으로부터 가장 가까운 지점에 있는 집 후보 정점 번호이므로 아무 시작점(편의점)에서 가장 가까운 집 노드 번호만 알면 됨 시작점 (0.4), (0, 5), (0, 6) 모두 힙에 넣어서 dijkstra 실행 1 queue [(0,4), (0, 5), (0, 6), ..

[1947] 선물 전달하기 (완전 순열, 교란 순열)

1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 분석 완전 순열 : n개의 원소가 모두 자기 자신이 아닌 값으로 배정되는 순열 (모든 원소의 위치를 바꾸는 순열) A가 B에게 선물을 줬다고 가정 1. B도 A에게 선물을 줬을 때 (양방향 교환) : N명 중 2명이 교환을 완료했으므로 남은 경우의 수는 D[N-2] 2. B는 A가 아닌 다른 사람에게 선물을 선달할 때 (단방향 교환) : N명 중 B만 받은 선물이 정해진 상태이므로 남은 학생은 N-1이며 경우의 수는 D[N-1] 풀이 n=int(input()) mod=1000000000 d=[0]*10000001 d[1]=0 # 혼자서는 선물을 교환할 수 없음 d[2]=1 # ..

[17298] 오큰수 (스택)

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 분석 스택에 새로 들어오는 수 > top에 존재하는 수 : 새 수는 오큰수, top pop하면서 새 수 push 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1 출력 순서 스택이 채워져 있거나 a[idx] > a[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장. pop은 조건을 만족하는 동안 계속 반복 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감 수열의 길이만큼 반복하고 스택에 남아있는 인덱스에 -1 저장 풀이 import sy..

[2164] 카드2 (큐, 덱)

2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 분석 공주 구하기 (큐, 덱) 문제 왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시 계방 karla.tistory.com 풀이 """ N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드..

[12891] DNA 비밀번호 (슬라이딩 윈도우)

12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 풀이 """ DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다. 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 ..

[1874] 스택 수열(스택)

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net """ 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 첫 줄에 n (1 ..

[2018] 수들의 합 5 (투 포인터)

2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 분석 [2003] 수들의 합2 (투 포인터) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmic karla.tistory.com 풀이 """ 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은..

[1940] 주몽 (투 포인터, 정렬)

1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net """ 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지 출력 첫째 줄에는 재..

[10986] 나머지 합 (합배열)

10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 분석 (A+B)%C = ((A%C)+(B%C))이므로 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일 구간 합 배열을 이용한 식 S[i]-S[j]는 원본 리스트의 j+1부터 i까지의 구간 합이므로 합배열의 나머지 값이 같으면 두개 뽑아서 합배열 값-합배열 값으로 나누어떨어지는 구간 찾을 수 있음 S[i]%M의 값과 S[j]%M의 값이 같다면 (S[i]-S[j])..

[11660] 구간합 구하기5 (2차원 합배열)

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 분석 2차원 합배열 채우기 : d[i][j] = d[i-1][j] + d[i][j-1] - d[i-1][j-1] + a[i][j] 2차원 구간합 구하기 : d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1] 풀이 import sys input=sys.stdin.readline n,m = map(int, input().split()) # 리스트 a=[[0]*(n+1)] # 합배열 d=[[0..