시나위

https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 각 노드들의 son, parent를 딕셔너리로 기록하고 사촌의 수를 찾았다. import sys; input = sys.stdin.readline def find_sibling(me, son, parent): p, grand_p = None, None if parent.get(me): p = parent[me] if parent.get(p): grand_p = parent[..

https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 손풀겸 푸는 문제 2 가장 넓게 색을 입히는 방법으로 리스트의 앞 뒤를 인덱스로 접근해서 풀었다. 가리키는게 다른 색이면 앞에서만, 같은 색이면 양쪽에서 인덱스를 이동한다. def main(): N = int(input()) s = input() f, b = 0, N - 1 cnt = 0 while f = 0: init_f = s[f] init_b = s[b] cnt += 1 # 순방향 순회 w..

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)이 필요하다. ..