생각 생각

https://acmicpc.net/problem/1036 1036번: 36진수 첫째 줄에 수의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. N은 최대 50이고, 수의 길이도 최대 50이다. 마지막 줄에 K가 주어진다. K는 36보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 36**50이 너무 커서 연산이 느릴 줄 알았는데, 그정도 연산은 어렵지 않아하더라. 좀 치네? import sys input=sys.stdin.readline n=int(input()) words=[input().strip() for _ in range(n)] k=int(input()) # 속도를 위해 미리 str->int, int->str로의 변환 딕셔너리를 만들어둔다. a_to_n={chr..

https://acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 프림 공부 3. 10분컷 1트클, 안 어려운 알고리즘이고 다익스트라와 유사해서 이제 구현 방법을 확실히 익혔다. 오히려 크루스칼로 푸는 법이 헷갈려서 한 번 고민해 보는 중. 풀이 1. 프림 # 전기가 부족해 import sys,heapq input=sys.stdin.readline N,M,K=map(int,input().split()) visited=[Fals..

https://acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 프림 공부 2. 구현은 한 번에 정확히 했지만 시행착오를 겪었다. ‘우물을 팔 수 있다’ 라는 말 때문에, 노드가 활성화되지 않을 수 있다는 말처럼 들렸기 때문이다. 첫 풀이는 다음과 같았다. 풀이 1. # 오류 풀이 1: 시작 노드를 정해야 한다고 생각해서 임의로 시작 노드를 정해봄. import sys, heapq input=sys.stdin.readline N=int(..

https://acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 수업에서 프림 알고리즘 얘기가 있길래 생각나서 공부하고 수도 코드만 읽고 구현해봤다. 크루스칼보다 친숙한 graph-traveling 형태여서 어렵지 않았다. 다만 언제 크루스칼을 써야 하고 언제 프림을 써야 하는지가 조금 헷갈린다. 설명을 찾아보니 dense한 경우에 프림이 더 유리하다고 한다. 시간 복잡도는 heap을 사용한다는 가정 하에 동일하다. # 1414 - 불우이웃돕기 # 프림 알고리즘..

https://acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 별자리 만들기 문제를 풀 때, 이 문제가 별자리 만들기보다 어렵다는 평가를 보고 풀어봤다. 실제로 별자리 만들기보다 더 까다로웠다. 다른 것보다, MST에서 간선을 하나 빼면 두 개로 나뉜다는 발상이 어려웠다. 구현은 그냥 MST였다. import sys input=sys.stdin.readline N,M=map(int,input().split()) parent=[i..

https://acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 구현에는 좀 애를 먹었지만, LIS임을 바로 파악해서 기분 좋았던 문제. # 전깃줄 - 2 # 발상: 왼쪽 전봇대를 기준으로 오름차순 정렬을 한다. 그 후 오른쪽 전봇대의 LIS를 찾으면 자연스레 그것이 답. # 다만 O(n log n)의 풀이 + 역추적이 가능해야 하기 때문에 구현이 조금 까다로웠다. import bisect as bs import sys input=sys.stdin.readline..

https://acmicpc.net/problem/16565 16565번: N포커 첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라. www.acmicpc.net 결국 코딩은 수학이다. from math import comb n=int(input()) mod=10007 answer=0 for i in range(1,n//4+1): temp=(comb(13,i)*comb(52-(4*i),n-(4*i))) if i%2: answer+=temp%mod else: answer-=temp%mod print(answer%mod)

https://acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 이번 주동안 생각해보면서 여러모로 많이 틀리고 많이 배웠던 문제. 이항계수의 합을 공부하면서 쉽게 풀 수 있다는 생각을 했지만 아니었다. 이항계수의 합은 2**n이다. 기억하자. 오답 풀이 1. import sys from itertools import combinations input=sys.stdin.readline def mul(i): if i==0: return 1 if i%2==0: return (mul(i//2)**2)%mod else: return (2*mul((i-1)..