19951번: 태상이의 훈련소 생활 (acmicpc.net) 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 배열이 주어질때, 구간 [a,b]에 c를 더하는 쿼리가 여러개 주어지고, 모든 쿼리를 해결하고 나서 최종 배열을 구하는 문제 1 2 3 4 5 -1 -2 -3 -4 -5 라는 배열에서 [1,5]에 -3을 더하면... -2 -1 0 1 2 -1 -2 -3 -4 -5 여기서 [6,10]에 5를 더하면 -2 -1 0 1 2 4 3 2 1 0 여기서 [2,7]에 2를 더하면 -2 1 2 3 4 6..
1. 문제 1311번: 할 일 정하기 1 (acmicpc.net) 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다. 각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 이럴 때 최소비용은 얼마인가? 2. 풀이 이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후, 각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다. 3명이면 (1,2,3), (1,3,2), ..
1. 틱택토 게임 3*3 게임판에서 O와 X를 서로 번갈아 둔다. 가로나 세로, 대각선으로 1줄(3개)이 서로 같게 만들면 승리 3*3 게임판에서 각각의 cell은 O, X, '.' 3가지중 한가지가 들어갈 수 있으므로.. 모든 가능한 게임판의 경우는 $3^{9} = 19683$가지로 몇가지가 없다 이 경우 중간에 게임이 끝나서 더 이상 둘 수 없는 경우가 있기 때문에 그런 경우를 고려해서 제외하면 된다. BFS를 이용해서 모든 가능한 경우를 조사할 수 있다. 1) deque에 (['.']*9, (첫 시작이 두는 수))를 먼저 넣고 BFS를 수행 특히 배열이 9칸이기 때문에 배열을 deepcopy해도 시간이 그렇게 오래걸리지 않는다. 2-1) 큐에서 하나씩 뽑은 다음, 게임판 배열을 순회해서 둘 수 있는..
1. 문제 10972번: 다음 순열 (acmicpc.net) 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 2. 풀이 1부터 n까지 정수로 구성된 어떤 순열이 주어질때 바로 다음 순열을 찾는 문제 예를 들어 1부터 5까지 구성된 순열 1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 ... 5 4 2 3 1 5 4 3 1 2 5 4 3 2 1 1 2 3 5 4가 주어지면 1 2 4 3 5라고 답해야한다. 단순하게 1부터 n까지 리스트를 만들고 permutations로 순열을 구한다음 현재 순열의 위치를 찾고 다음 순열을 찾아볼 수도 있겠지만.. n이 10000까지라..
31423번: 신촌 통폐합 계획 (acmicpc.net) 31423번: 신촌 통폐합 계획 첫 번째 줄에 대학교의 개수 $N$이 주어진다. $(2 \leq N \leq 500 \, 000)$ 다음 $N$개의 줄의 $i$번째 줄에 대학교 이름을 의미하는 알파벳 소문자로 이루어진 문자열 $s_i$가 주어진다. 주어지는 대학교 www.acmicpc.net 문제는 단순한데 s[i] 뒤에 s[j]를 그대로 붙이고, s[j] = 0으로 만든다. 이를 n-1번 순서대로 반복해서 얻은 결과를 출력하면 된다 from sys import stdin n = int(stdin.readline()) s = [0] for _ in range(n): c = stdin.readline().rstrip() s.append([c]) fo..
1. 문제1 https://atcoder.jp/contests/abc341/tasks/abc341_d D - Only one of two AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 n,m,k가 주어지는데 n이나 m중 어느 하나만으로 나누어 떨어지는 정수들을 오름차순 정렬할때, k번째로 작은 양의 정수를 찾는 문제 예를 들어 n = 2, m = 3, k = 5이면 2,3,4,8,9,10,...은 각각 2나 3중 어느 하나만으로 나누어 떨어지는 정수들이다. 4는 2로 나누어 떨어지지만 3으로 나누어 떨어지지 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
