안녕

0. 문제 링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 풀이 방법 에라토스테네스의 체로 maps에 소수인 부분은 True 설정한다. 기존의 방식(left, right를 양 끝에서 시작하여 점점 조여 오는 방식)이 아닌 left, right를 왼쪽부터 시작한다. total은 left와 right 사이에 있는 소수를 모두 더한 숫자이다. total을 기준으로 left 혹은 right을 옮긴다. 이때 left, right가 위치하는 index는 반드시 maps[index] == True여야 한다.(소수) total == n이라면 정답 += 1을 하고, l..

0. 문제 링크 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 풀이 방법 2023.08.13 - [Computer Science/알고리즘] - [백준 - Python] 1766 - 문제집 [백준 - Python] 1766 - 문제집 0. 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸..

0. 문제 링크 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 1. 풀이 방법 **코드 길이 주의 해당 알고리즘은 브루트포스로 풀었다. 최대 길이는 19이고, 따라서 연산자는 최대 9개가 가능하다. 중첩된 괄호는 불가능하므로, 연산자는 최대 5개까지 선택이 가능하다. 물론 연산자 5개는 단 한 번만 가능하다. 연산자 4개를 뽑는 경우도 의외로 적다. 중첩된 괄호라는 조건을 제외하면 최대 9C5 + 9C4 + 9C3 + 9C2 ..

0. 문제 링크 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. 풀이 방법 해당 문제의 핵심은 그룹 번호이다. DFS를 수행하던 도중 같은 그룹 번호를 만난다면 이는 싸이클이 생긴 것이고, Safe Zone을 하나 추가해야 한다. 하지만 만약 다른 그룹 번호를 만난다면, 그 그룹은 이미 Safe Zone이 있으므로, 그냥 break 하면 된다. 내 그룹이 해당 그룹에 편입한다고 생각하면 편할 것이다. (..

0. 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. 풀이 방법 해당 문제는 위상 정렬 알고리즘을 사용해야 한다. 위상 정렬 알고리즘은 싸이클이 없는 그래프에서, 각 노드들이 순서를 지켜야 할 때 사용된다고 한다. 해당 문제의 풀이 방법은 다음과 같다. 우선 나의 자식이 되는 문제들을 입력한다. -> 즉 인접한 노드를 입력한다. 또한 자식 노드는 앞서서 몇 개의 문제를 풀어야 하는지 기록해 놓는다...

0. 문제 링크 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 1. 풀이 방법 이분 탐색 + 매개변수 탐색 풀이로 풀었다. 정답이 시간이므로, 시간의 리스트 내에서 매개 변수를 탐색하는 방식 start, end 시간은 아래의 코드와 같이 설정했음. 이유는 최솟값은 무조건 불가능한 것, 최댓값은 무조건 가능한 것으로 설정해야 하기 때문 이후 while 문을 돌면서, 각 심사대마다 정해진 시간만큼 받을 수 있는 인원 세었음. 받을 ..

0. 문제 링크 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 1. 풀이 방법 스택이 비어있다면, 매 숫자마다 스택에 넣는다. 그리고 다음 숫자로 이동한다. 만약에 스택에 숫자가 들어가 있다면, 스택의 길이를 측정한다 -> l 현재 숫자의 위치인 cur과 스택의 마지막 숫자를 비교하며 좌우로 넓혀가며 팰린드롬을 만족하는지 확인한다. 이때 스택의 길이가 남은 숫자의 길이보다 길다면 이 또한 팰린드롬을 만들 수 없다. 만약 스택에 들어있는 숫자 3개와 현재 숫자의 위치인 cur에서 cur + 2까지의 3개의 숫자가 팰린드롬을 만족한다면, 스택을 모두 비운다. 그리고 T..

0. 문제 링크 https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 1. 풀이 방법 현재까지의 누적합 값을 구함. 해당 누적합 값 - k의 값이 딕셔너리에 존재한다면 개수만큼 정답에 더하면 됨 0이 들어갈 수도 있으므로 누적합 값이 키로 있는 딕셔너리 값도 계속해서 업데이트해줘야 함 2. 코드 import sys input = sys.stdin.readline def bf(): c..

0. 문제 링크 https://www.acmicpc.net/problem/1596115961번: 회전 초밥첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net2023.05.15 - [Computer Science/알고리즘] - [백준 - Python] 2531 - 회전 초밥 [백준 - Python] 2531 - 회전 초밥0. 문제 링크 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d,..

0. 문제 링크 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 1. 풀이 방법 4개씩 투포인터로 범위를 잡는다. set으로 만든 후에, 중복되지 않는 개수를 센다. 만약 행사로 주는 쿠폰에 해당하는 번호가 없으면, 1을 더해서 개수를 센다. 마지막으로 '회전 초밥' 이므로, 맨 뒤에서 맨 앞까지 먹는 경우도 계산해야 한다. 해당 코드는 매우 느리다. 최적화 작업은 하지 않았다. 통과는 된다. 아래는 내가..