코드연습/BOJ (34) 썸네일형 리스트형 BOJ 1764 : 듣보잡 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 풀이 풀이 키워드 어떻게 풀어도 계속 시간 초과 발생 List, dictionary 자료 형 모두 시간 초과 set 자료형을 이용하고 시간 단축 해결 import sys if __name__ == '__main__': N, M = map(int, sys.stdin.readline().split()) data1 = set() data2 = set() for i in range(N): data1.add(input()) for i in range(M): data2.add(input()) result = sorted(list(data1 & data2)) print(len(r.. BOJ 10815 : 숫자 카드 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 풀이 시간복잡도 O(N)의 형태로 풀게 되면 시간 초과 이분 탐색 알고리즘을 사용해서 풀어야 하거나, 시간 복잡도가 \( O(log 2^N)) \ https://satisfactoryplace.tistory.com/39 Dictionary 자료형을 이용하면 시간 단축이 가능해서 / 이분 탐색 알고리즘을 사용 할 필요가 없음. https://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table [알고리즘] 이분 탐색(B.. BOJ 2477 : 참외밭 문제 시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다. 1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다. 예를 들어 참.. BOJ 2004 : 조합 0의 개수 입력 문제 자체를 이해 못해서, 풀지 못 하고 답안을 보고 해설을 참고한다. https://changsroad.tistory.com/95 [Python] 백준 #2004- 조합 0의 개수 문제 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 코드 My answer-(Wrong_answer) def counts(n,a): cnt=0 if(n Another answe.. changsroad.tistory.com 여러 해설들을 봤지만, 이게 가장 잘 상술 되어있었다. 요약하면, 조합(Combination)의 수식은 팩토리얼의 조합인 https://ko.wikipedia.or.. BOJ 2981 : 검문 문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 풀이 아래 블로그를 참고하였다. https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-2981-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B2%80%EB%AC%B8-%EA%B3%A8%EB%9.. BOJ 2609 : 최대공약수와 최소공배수 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 풀이 앞의 약수에서 참고한 알고리즘인 '유클리드 호제법'을 조금만 참고하면 된다. 두 수의 최대 공약수는 두 수의 나머지를 계속 나눔으로써, 언젠가 나누어 떨어지는 수를 의미한다. 그리고 최소 공배수는 두 수의 최대 공약수로 구성된 최소의 수 이므로 x(a를 최대공약수로 나눈 수)*y(b를 최대공약수로 나눈 수)*GCD(a,b)로 귀결된다. 이는 두 수(a = x* GCD(a,b), b = y*GCD(a,b))로 구성 되어 있기 때문에 각각의 최소 공배수는 위와 같이 구성된다. 최대공약수(GCD : Greatest Common Divisor) 최소공배수(LCM : Least Common Multiple) impo.. BOJ 1037 : 약수 문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 풀이 진짜 간단한 문제다. 하지만 나는 틀렸다. '유클리드 호제법'은 두 수들의 나누기를 통해서 그 나머지로 기존 수로 나누어서 나머지가 0이 될 때의 나머지 수가 최대 공약수인 방법이다. 여기서 모든 약수들 중에서 최소 약수와 최대 약수의 곱으로 기존 수를 구할 수 있다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclid.. BOJ 10814 : 나이순 정렬 문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 풀이 직전 문제와 동일하게 Nested List로 처리하면 금방 풀린다. 그러나 시간이 조금 필요했던 부분은 age를 string으로 받아서 ,int로 받았을 때와 결과가 다르게 나온다는 것. 이해하고 처리하니 금방 해결됐다. import sys if __name__ == '__main__': N = int(input()) data_list = {} for _ in range(N): age, name = sys.stdin.readline().split() if int(age) in data_list: da.. 이전 1 2 3 4 5 다음
