시나위

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS로 풀수있는 쉬운 문제이다. from collections import deque def main(): n, k = map(int, input().split()) memo = [200000 for _ in range(100001)] q = deque() q.append(n) memo[n] = 0 answer = None while q: cur = q.popl..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 파이썬으로는 int나 long long등 변수 값의 최대 크기를 생각하지 않아도 되기 때문에 상당히 쉬운 문제이다. 일차원 변수를 사용해서 nCm = n! / ( (n-m)! * m! ) 으로 구현했다. def main(): n, m = map(int, input().split()) fact = [1 for _ in range(n + 1)] for i in range(2, n + 1): fact[i] = fact[i - 1] * i print(fact[n] // fact[n-m] // fact[m]) if __n..

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/14697 14697번: 방 배정하기 정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 www.acmicpc.net 상당히 쉬운 브루트포스 문제이다. 0,0,0 부터 각 방이 가질수 있는 최댓값까지 돌리는 방법으로 구현했다. def main(): *room, total = map(int, input().split()) for i in range((total // room[0]) + 1): tmp1 = room[0] * i for j in range((total // room[1]) + 1): tmp2 = ..

https://www.acmicpc.net/problem/22942 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 주어진 데이터가 조건에 맞는지 확인하면되는 문제이다. 처음 시도한건 브루트포스이다. 추가할때 이미 추가된 원들과 비교하면서 들어갈수 있을때 추가하는 방식으로 풀었는데 시간초과가 났다. ''' boj 22942 wrong answer ''' # import sys; input = sys.stdin.readline def check(cur, circles): x, r = cur for xx, rr in circles: # 동심원인데 반지름까지 같은 경우 if x == xx and r == rr: return F..

https://www.acmicpc.net/problem/11365 11365번: !밀비 급일 당신은 길을 가다가 이상한 쪽지를 발견했다. 그 쪽지에는 암호가 적혀 있었는데, 똑똑한 당신은 암호가 뒤집으면 해독된다는 것을 발견했다. 이 암호를 해독하는 프로그램을 작성하시오. www.acmicpc.net 굉장히 쉬운문제이다. 파이썬으로 풀면 다음처럼 풀수있다. while 1: s=input() if s=="END": break print(s[::-1]) 이렇게 넘어가기엔 너무 양심이 없는거같아서 오랜만에 C/C++로 접근했다. 처음엔 C++로 풀었는데 cin은 개행문자뿐만아니라 whitespace(' ', '\t', '\n')가 나오면 입력을 멈추기때문에 원하는 값을 얻을수 없었다. 그래서 scanf를사용..

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/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 2월의 첫문제는 union find 문제이다. union에서 같은 부모를 연결하게 될 떄 cycle이 된다. 이를 사용하면 cycle 체크와 union을 같이 진행할수 있다. # import sys; input = sys.stdin.readline def find(a, parent): if parent[a] == a: return a parent[a] = find(parent[a], pare..

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)] 이랑 ..