시나위

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제 3 # N & M (9) import sys; input = sys.stdin.readline def backtrack(lst=None): global N, M, nums, visit, answer if lst is None: lst = [] if len(lst) == M: answer.add(tuple([nums[i] for i in lst])) return for i in ra..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹이 조금 부족한거 같아서 푼 문제 2 # N & M (8) import sys; input = sys.stdin.readline def backtrack(lst=None, prev=0): global N, M, nums if lst is None: lst = [] if len(lst) == M: print(*[nums[i] for i in lst]) return for i in r..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹이 조금 부족한거 같아서 푼 문제 # N & M (5) import sys; input = sys.stdin.readline def backtrack(ind, limit, size, nums, visit, lst=None): if lst is None: lst = [] if ind == limit: print(*[nums[i] for i in lst]) return for i in..

https://www.acmicpc.net/problem/3040 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 손풀기용 문제 combination으로 두개의 값을 고르고, 그 두개의 값을 뺐을때 100이 되는 값을 찾는다. 그 두개의 값을 제거한뒤에 모든 값을 출력하면된다. # import sys; input = sys.stdin.readline from itertools import combinations def main(): dwarves = [int(input()) for _ in range..

https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 트리 문제이다. 트리를 만들고 순회하면 된다. 특정 노드의 부모가 가진 색깔과 노드가 원하는 색깔이 다른 경우 1 을 더한값을 계속 올려주면 된다. import sys; input = sys.stdin.readline sys.setrecursionlimit(10**9) def order(cur_node, cur_color, parent, adj_list, color): ret = 0 if..

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+' 패턴중 가장 ..

1. 작심삼주 사실 이번주는 이 주제를 쓰지 않으려 했다. github 1일 1커밋도 잘 되고 있고, 블로그 1일 1포스팅도 잘 지키고있는데 딱 하나. solved.ac 에 있는 잔디에 빵꾸가 났다. 이번주엔 꽤 바빠서 전날에 미리 풀어두고 커밋과 포스팅을 12시 넘겨서 한적도 있다. 커밋은 12시에 올려도되고 블로그는 예약 포스팅이 가능했지만 문제풀이는 무조건 하나 풀어야했다. 1일 1커밋과 1일 1 포스팅을 하려는 이유가 꾸준히 공부하기 위한 것이긴 하지만 하나가 뚫려버리니 마음이 살짝 아프다. 앞으로도 1일 1커밋, 1일 1포스팅은 지키겠지만, 1일 1알고리즘은 조금 달라질지도 모르겠다. (아마 내 마음가짐이....) 뭔가 바쁜 일정이 있다면 하루에 여러 문제를 풀고 예약 포스팅, 예약 커밋으로 올..