문제 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 주어진 짝수의 골드바흐 파티션 개수 출력하기(인데 함정맛...) Reference https://ps.dabyeol.com/solutions/boj/17103/python Problem Solving 기본에 충실한 문제 풀이 ps.dabyeol.com https://www.acmicpc.net/board/view/82413 글 읽기 - 파이썬) 시간 초과 관련 질문 (골드바흐 파티션) 댓글을 ..

문제 https://www.acmicpc.net/problem/4134 4134번: 다음 소수 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. www.acmicpc.net 주어진 숫자보다 같거나 큰 소수를 출력하시오. (예: 6->7) 풀이 이 문제를 풀기 위해서는 필요한 게 하나 있다. def isprime(a): sqrt = int(a ** 0.5) if a == 1: return False for i in range(2,sqrt+1): if a % i == 0: return False else: return True 바로 에라토스테네스의 체를 예전에 백준 푼다고 루트 N 버전으로 코딩한게 그것. 근데 저거 저대로 쓰면 틀리..

문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 간격을 일정하게 심으려면 나무가 최소 몇 개 필요한가? Reference https://jyzinn.tistory.com/111 [Python] 백준 2485번 가로수 문제 직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예 jyzinn.tistory..

문제 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 분수 두 개의 합을 '기약분수'로 출력하시오 풀이 이거는 우리가 초등학생때 배웠던 약분과 통분을 활용해 풀어야 하는 문제이다. 통분은 더할라면 필요하고 약분은 기약분수 만들라면 필요하다. 그러면 뭐 갖고와야 하냐고요? # 알아두면 좋은 유클리드 호제법 def Euclidean(a, b): while b != 0: [a, b] = [b, a%b] return a 유클리드 호제법이요. 이 문제는 투트랙으로 접근할건데 첫번째로 두 줄에 걸쳐 입력되는..

문제 https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 1934번이랑 같은 문제다. 두 수의 최소공배수를 출력하면 된다. 풀이 https://koreanraichu.tistory.com/329 백준 1934번 풀이 문제 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수..

문제 https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 입력받은 문자열에서 서로 다른 부분 문자열이 몇 개인지 세면 된다. Reference https://reo91004.tistory.com/140 [백준 / BOJ] 11478번 서로 다른 부분 문자열의 개수 (C++, Python) 링크 : https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www...

문제 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 두 집합의 차집합들의 길이 합을 출력해보자 풀이 이거 풀이가 투트랙인데 둘 다 맞긴 맞았다. import sys N, M = map(int, sys.stdin.readline().split()) set_x = set(map(int,sys.stdin.readline().split())) set_y = set(map(int,sys.stdin.readline().split())) 일단 기본 ..

문제 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 두 집합(듣지 못함/보지 못함)의 교집합을 출력하시오 풀이 이 문제는 굉장히 심플한 문제다. 푸는 것 자체는 그런데 출력이 씁... import sys N, M = map(int, sys.stdin.readline().split()) not_heard = set() #듣지 못한 사람 not_saw = set() # 보지 못한 사람 for _ in range(N): not_heard.add(..

문제 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 주어진 두 수의 '최소공배수'를 출력하시오 Reference https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 나무위키 손으로 계산할 때는 제수와 피제수의 값 크기를 비교해서 적절하게 배열하지만 수식이나 코드로 나타낼 때는 신경쓰지 않아도 되는데, ..

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 숫자 카드에서 특정 숫자가 몇 개인지 찾아서 출력하기 Reference https://www.daleseo.com/python-collections-counter/ 파이썬 collections 모듈의 Counter 사용법 Engineering Blog by Dale Seo www.daleseo.com https://chancoding.tistory.com/..

문제 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 로그 데이터를 바탕으로 회사에 있는 사람이 누구인지 사전 역순으로 출력하기 풀이 로그 데이터는 이름이랑 상태가 있는데 상태가 enter면 출근한거고 leave면 퇴근한거다. 그니까 이걸 토대로 현재 회사에 있는 사람을 찾으면 되는데... 아 이거 머리 터진다 그죠? 근데 머리 터질 일이 1도 없음. 일단 이 문제의 카테고리가 집합인 것을 잊지 말자. i..

문제 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 주어진 집합 안에 있는 단어가 아래 집합에서 몇 개나 포함되는지를 확인하시오 풀이 솔직히 김구라짤 넣고싶다... 보자마자 눈으로 욕했기때문... 사실 이 파트 들어갔으면 해시 테이블에 대해 서술을 해야 하는데 이거는 내가 이해를 못했음... 부스트코스 복기해야되나... OTL 아무튼 풀어봅시다. 이게 보자마자는 뭔 개소린가 싶을텐데 일단 예제를 보자. 5 11..

문제 https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 연립일차방정식의 해를 찾는 문제. 문제에서는 해가 존재하는 연립일차방정식을 가정한다. (그래서 이 풀이대로 짜면 답이 없을 때 출력이 없음) 풀이 이 문제를 읽은 본인의 심정: 너는 고등학교 이과 선택하지 마라... 연립일차방정식 그거 푸는거 귀찮아서 코딩할 정도면 나중에 삼각함수 미적분..

문제 https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 직접 가서 보십시오. 난 당최 뭔 소린지 모르겠음. Reference https://everyday-image-processing.tistory.com/520 BOJ 24313번: 알고리즘 수업 - 점근적 표기 1 핵심 포인트 시간 복잡도 제출코드 a0, a1 = map(int, input().split()) c = int(input()) n0 = int(input()) flag = 1 for i in..

문제 https://www.acmicpc.net/problem/24267 24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 이번에도 삼중 반복문인데... 아... 아무튼 실행 횟수랑 시간 출력하는거 맞음. Reference https://kevinitcoding.tistory.com/entry/%EB%B0%B1%EC%A4%80Python-24267%EB%B2%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EC%9..