시나위

https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 트리 문제이다. 입력으로 주어지는 값은 양방향 그래프이고 인접리스트를 사용해서 노드끼리 연결 시킨다. 그리고 트리를 순회할때 parent 노드와 다른 번호의 노드만 순회를 하면 leaf 노드를 찾을수 있다. leaf node를 찾으면 1을 리턴해주고 이 값들을 모두 더해주면 leaf 노드의 개수를 찾을수 있다. import sys; input = sys.s..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 최단거리를 찾는 BFS 문제이다. 2차원 배열에서 방문하지 않은 점을 방문하면서 탐색하면 되고, 탐색도중 그람이 있으면 그 위치부터 맨해튼 거리값을 더해서 최소 값이 되는지 확인하면 된다. #include #include #include using namespace std; int map[100][100] = { 0 }; int N, M, T; int d[8] = { -1,0,0,..

https://www.acmicpc.net/problem/17829 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 분할 정복문제이다. 두번째로 큰 값을 찾고, 새로운 이차원 행렬을 계속 만드는 방식으로 # import sys; input = sys.stdin.readline def second_max(r, c, arr): s = [arr[r][c], arr[r][c + 1], arr[r + 1][c], arr[r + 1][c + 1]] s.sort() s.pop() ret..

https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문자열 문제이고 정규표현식(regex, regular expression)으로 풀었다. 쉽게 풀줄 알았으나 match를 사용하면 패턴을 제대로 찾지 못하는 값들이 있었다. 예를 들면 '100111001' 이런 문자열이 들어왔을 때 '10011' '1001' 로 나눌수 있기 때문에 True 값이 나와야한다. 하지만 정규 표현식은 탐욕적으로 값을 구하기 때문에 '100+1+' 패턴중 가장 ..

https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net 자기전 쉬운문제 하나 Counter를 한번 사용해보기 위해 풀어봤다. import sys; input = sys.stdin.readline from collections import Counter def main(): N = int(input()) c = Counter([input().rstrip() for _ in range(2 * N - 1)]) for k, v in c.items()..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net Union find 알고리즘을 사용하는 문제이다. 두 노드를 받아서 연결을 시키고, 친구가 될수 있는 최소 비용도 같이 갱신한다. 모든 노드를 받은 후 전체적으로 각 노드의 root값을 한번 더 갱신하고, 각 트리의 루트 비용를 더하면 된다. # import sys; input = sys.stdin.readline from collections imp..

https://www.acmicpc.net/problem/19622 19622번: 회의실 배정 3 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net DP 문제이다. #include using namespace std; #define max(x, y) (x > y) ? x : y int main(){ cin.tie(0); ios::sync_with_stdio(0); int N, i, s, e, m; int memo[100000]; cin >> N; for (i = 0; i > s >> e >> m; if (i ..

https://www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 뒤에서부터 바꿀수 있는 값을 탐색하고, 값이 정해지면 교환한 다음 그 이후 값들을 정렬하면된다. import sys; input = sys.stdin.readline def find_answer(word_list): ret = ''.join(word_list) for i in range(len(word_list) - 2, -1, -1): # 맨 뒤는 제거 # 문자간 distance가 가..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 시뮬레이션 문제이다. 드래곤 커브를 만들면서 구해지는 꼭짓점을 모두 찾으면 되는 문제인데 이게 조금 복잡했다. 드래곤 커브를 만들때 다음과 같은 순서로 꼭짓점을 구했다. 1. 0세대 드래곤 커브를 구하고 현재 위치를 드래곤 커브의 마지막 점으로 설정한다. 2. 현재까지의 드래곤 커브로 다음 세대를 구한다. 1) 마지막 꼭짓점부터 역방향 순회하고, 드래곤 커브의 꼭짓점 차..

https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 시뮬레이션 문제이다. 구현만 하면 된다. def check_partition(a, b, _..