시나위

https://www.acmicpc.net/problem/9421 9421번: 소수상근수 양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다. 700은 상근수이다. 72 + 02 + 02 = www.acmicpc.net 소수인 상근수를 찾는 문제이다. 소수를 에라토스테네스의 체로 구해놓고 소수가 상근수인지 찾으면 된다. from math import isqrt def findPrime(N): prime = [1 for _ in range(N + 1)] prime[0] = prime[1] = 0 for i in range(2, isqrt(N) + 1): if prime[i]: for j in r..

https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 제목에 쉬운거라고 써있는데 생각하기 조금 어려웠다. N의 최대값이 50000이어서 입력값을 받으면서 한번에 찾아야한다는 생각이 들어서 머리가 잘 돌아가지 않았나보다. (힌트를 봐서 다행히 빨리 풀수 있었다) 알고리즘은 스택을 사용해서 항상 오름차순이 되도록 만들고, 현재 입력값(건물의 높이)와 이전 건물의 높이를 비교해서 풀면된다. 이렇게만 말..

https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 이분탐색 문제이다. 손질된 김밥(꼬다리를 제거한 김밥)을 사용해서 김밥 조각 M개 이상을 만들면 되고, 이분탐색으로 김밥 조각을 내는 길이를 찾으면 된다. # import sys; input = sys.stdin.readline def remove_kkodari(dist, K): if dist = K: dist -= K return dist def bin..

https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net floyd warshall을 사용해야할까 생각했는데 값이 너무 많아서 다른 방법인 union find로 풀었다. 알고리즘 자체는 어렵지 않았지만 꽤 많이 틀린 문제였다. union-find를 구현하면서 생각보다 많이 틀렸는데 find를 할때마다 값을 갱신하는게 꼭 필요했다. 그 외엔 TC 변수를 i로 둬서 root = [i for i in range(n)] 이랑 ..

https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 이차원 배열을 사용한 누적합 문제이다 밝기의 평균을 구할때마다 항상 더하고 나누는 연산을 하는건 꽤 오래 걸린다. 그래서 누적합을 구한다음 특정 범위에서의 합을 구하고 해당 범위의 넓이로 나누면 된다. 일차원 배열에선 누적합을 구할땐 이전 인덱스 값만 계속 더해주면 되는데, 이차원 배열에서 누적합을 구할 땐 행과 열에서 이전 인덱스(memo[i-1]..

https://www.acmicpc.net/problem/14467 14467번: 소가 길을 건너간 이유 1 3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다. www.acmicpc.net 오늘은 쉬운 문제 하나만... 값이 없으면 추가하고, 있으면 들어있는 값과 비교해서 다른 경우에 길을 건너갔다고 체크하면된다. # import sys; input = sys.stdin.readline def main(): N = int(input()) cow = [None for _ in range(11)] answer = 0 for _ in range(N): a, b = map(int, inpu..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 시뮬레이션과 백트래킹으로 모든 조합을 만들면 된다. i번째가 i번째로 가는 시뮬레이션 부분은 어렵지 않지만 백트래킹으로 조합을 만들때 중복되는 거 없이 수를 최소한으로 줄여야 통과할수 있었다. #include #include using namespace std; int N, M, H; int ladder[32][12]; int answer; bool check() { int i, r, c; fo..

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/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가 가..