시나위

https://www.acmicpc.net/problem/1668 1668번: 트로피 진열 민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열 www.acmicpc.net 손 풀 겸 쉬운 브론즈 문제 # import sys; input = sys.stdin.readline def main(): N = int(input()) tropy = [int(input()) for _ in range(N)] ans = '' max_h, ret = 0, 0 for i in range(len(tropy)): if max_h < tropy[i]: max_h = tropy[i] ret += 1..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 처음 풀어보는 플로이드 와샬 문제이다. 플로이드 와샬을 몰랐기 때문에 다익스트라로 먼저 접근했다. 알고리즘 순서는 다음과 같다. 한 도시를 시작으로 다른 도시까지의 거리를 탐색한다. 모든 도시를 다 탐색해야하기때문에 반복문으로 돌리고 값을 받아온다. 한도시에서 다른 도시까지의 거리를 바탕으로 사이클을 탐색한다. 도시 사이 거리는 단방향이므로 양방을 모두 더해줘서 ..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net nCk = n! / {(n-k)! * k!} (mod bignum)이다 곱셉에선 모듈로 연산이 각각 들어가도 되었지만 나눗셈도 가능한지 몰랐다. 그래서 구글링을 했고 페르마의 소정리라는 것을 알게 되었다. 모듈로 연산에 쓰이는 값이 소수인경우 곱셉의 역원으로 b^-1 (mod pn) = b^(pn-2) (mod pn)가 된다. 1,000,000,007 이란 값은 소수이므로(이것도 구글링해봤다.) nCk 또한 페르마 소정..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 이 문제는 s에서 출발해서 t까지의 최소 가중치를 구하는 문제이다. 다익스트라를 사용하면 쉽게 구할 수 있다. #include #include #include using namespace std; #define INF 1234567890 int dijkstra(int start, int end, int size, vector linked_list) { int cur, cur_dist, adj..

https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 동적계획법으로 누적합을 사용하는 문제이다. 출석체크 한 사람을 구한뒤에 출석하지 않은 학생을 하나하나 찾아서 계속 시간초과가 걸렸다. 누적합으로 구한뒤에 구간별로 출력하니 통과. import sys; input = sys.stdin.readline # 0 입력 N, K, Q, M = map(int, input().split()) sleep = set(m..

https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N 0: if owned[x]: land = x x >>= 1 return land N, Q = map(int, input().split()) owned = [False for _ in range(N + 1)] for i in range(Q): x = int(input()) owned_land = check_owned(x, owned) if not owned_land: owned[x] = True print(owned_land) #include using namespace std; bool owned[(1 >= 1;..

https://www.acmicpc.net/problem/13902 13902번: 개업 2 해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 www.acmicpc.net 문제 자체는 어렵진 않으나 시간초과의 벽이 조금 있었다. 이 문제를 풀기위해서 동적계획법을 사용해야한다. 최대 두개의 웍을 사용해서 처리할 수 있는 양을 구해야하는데 set이라는 자료구조를 사용했다. 두개로 처리할수 있는 양을 동적 계획하여 0부터 N번째 양까지 계산하면 된다. import sys; input = sys.stdin.readline N, M = map(int, input().split())..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동적 계획법은 볼때마다 새롭다. 요즘 계속 풀던 문제가 완전 탐색이었기 때문에 조금 더 오래 걸린 듯하다. 1, 5, 10 등 흔히 사용하는 동전만 나온다면 그리디 알고리즘으로 하는게 낫지만, 그렇지 않은 경우 동적 계획법을 사용해서 풀어야한다. 예를 들면 동전이 1, 4, 5이 있고 12원을 만들어야하는 경우 그리디 알고리즘으로 풀면 4개의 동전(5*2 + 1*2)이 필요하다. ..

https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 투포인터를 시간초과가 되지 않고 풀 수 있다. 투포인터에 대한 내용은 최하단에 블로그를 참고하면 된다 N, K = map(int, input().split()) numbers = list(map(int, input().split())) ptr1, ptr2 = 0, 0 cnt, ans, dist = 0, 0, 0 while ptr1 != N and ptr2 != N: if numbers[ptr1] % 2: if cnt > 0: p..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제를 이해하기까지 꽤 오래걸렸다. 근데 알고리즘이 어렵진 않았다. 문제를 요약하자면 각 목적지 별로 최단 경로를 찾는데 그 최단 경로 안에 g와 h 사이 도로를 포함하는 후보만 출력하는 것이다. 출발지, 교차로 g, h 에서 각 한 번 씩 최단 거리를 탐색하면 충분히 찾을수 있다. 각 지점에서 다익스트라로 최단거리를 파악하고, '출발지에서 목적지 까지'의 최단거리와 '출발지 - g - h ..