기록장

이번 시험은 쉽게 나온 편이라고 하셨다.나도 풀면서 많이 어렵게 느껴지지는 않았다.다만 큐 라이브러리 사용하는 연습을 안 해서 라이브러리 임포트하고 함수 사용하는 데 시간을 많이 썼던 것 같다.1. 숫자 카드https://www.acmicpc.net/problem/10815문제 의도는 이분 탐색이지만 set으로 풀어도 되는 문제이다.해시함수를 이용해서 각 값의 인덱스를 구한 후 그 곳에 저장하면 O(1)의 속도로 접근할 수 있다.import sysn = int(sys.stdin.readline())arr1 = list(map(int, sys.stdin.readline().split()))m = int(sys.stdin.readline())arr2 = list(map(int, sys.stdin.readli..

문제https://www.acmicpc.net/problem/13334풀이 그림 순서:1 3 52 4 현재 철로 범위 내에 가장 많은 (시작점, 끝점) 범위가 포함되려면 끝점을 기준으로 검사해야 한다. 코드import sys, heapqn = int(sys.stdin.readline())office = []for _ in range(n): start, end = map(int, input().split()) if start>end: start, end = end, start heapq.heappush(office, (end, start)) # (우선순위, 값) -> 종료 시간 기준으로 최소힙 정렬d = int(sys.stdin.readline()) # 고려할 구간의 길이pos..

문제https://www.acmicpc.net/problem/10000원 n개로 나뉘어지는 영역의 개수를 구하는 문제이다.모든 원의 중심 좌표는 x축 위에 있고 교차하지 않지만 접할 수 있다.아래 그림과 같이 원이 접할 경우 총 6개 영역으로 간주됨풀이이 문제를 처음 접했을 때 괄호 문제를 떠올렸다.'('이면 스택에 넣고 ')'이면 스택의 top이 '('인지 확인한 후 pop하면서 cnt+=1해주는 방식 원 영역도 똑같이 영역의 개수를 세면 된다.원의 시작 점, 끝 점을 구한 후 좌표가 작은 순서대로 순회하면서원의 시작 점이면 스택에 넣고 끝 점이면 스택의 top을 확인 -> top이 시작 점이면 원 하나로 간주하여 시작점을 pop, cnt+=1 그러나 이 경우만 고려하면 안 된다. 이런 경우는 어떨까...

보호되어 있는 글입니다.

문제 분석https://www.acmicpc.net/problem/2812숫자 k개를 지워서 만들 수 있는 가장 큰 수를 구하는 문제이다.풀이가장 큰 수를 만들려면 최대한 큰 숫자가 앞에 위치하게 해야 한다.예를 들어 4177252841에서 4개를 지워서 가장 큰 수를 만들면 4177252841 즉 775841이 된다.원리를 생각해보면 앞에서부터 순회하면서 뒤에 더 큰 숫자가 있다면 해당 숫자를 지워서 더 큰 숫자가 앞에 위치하도록 하고 있다.이때 스택을 활용하면 적절하게 구현 가능하다. 스택은 조건에 따라 불필요한 데이터를 제거하고 필요한 데이터를 유지할 때 적합하다.이 문제에서 조건은 현재 값보다 다음 값이 크면 현재 값을 삭제하는 것이므로 구현 방법을 다음과 같이 떠올릴 수 있다.n=7 k=4765..

문제https://www.acmicpc.net/problem/2470풀이이것도 나중에 다시 풀어봐야 할 문제다.투포인터로 풀면 쉽겠다고 생각했는데 점점 반례가 많아지면서 조건문을 덕지덕지 붙이게 됐다.오답노트처음 짠 코드를 보자. 탐색 시작 지점, 탐색 종료 조건, 포인터 이동 조건 모두 잘못됐다.left, right를 배열의 중간 지점(n//2)에서 시작해서 양쪽으로 옮기고 있음-> left, right의 탐색 시작점을 중간에서 시작하면 left, right 각각 양방향 중 어디로 포인터를 옮길지 결정해야 한다. -> 내 코드에서 가장 잘못된 선택임 이것 때문에 조건문이 이상하게 많이 붙었음. 투포인터를 사용하는 목적도 장점도 모르고 쓴 결과-> 양쪽에서 시작하면 left는 오른쪽으로만, right는 ..

문제https://www.acmicpc.net/problem/10830행렬 A의 B제곱을 구하는 문제이다. 1 ≤ B ≤ 100,000,000,000A^B의 각 원소를 1,000으로 나눈 나머지를 출력해야 하고 원소 개수 N에 대해 2 ≤ N ≤ 5를 만족한다. 풀이N번의 거듭제곱을 그냥 계산하면 시간 복잡도가 O(N)이다. 반면 분할 정복을 사용해 거듭제곱을 계산하면 O(logN) 안에 계산할 수 있다. 분할 정복을 이용한 거듭제곱# 분할정복을 사용한 거듭제곱 구현하기# 지수를 2로 나눈 나머지가 0인 횟수만큼 자기 자신과 곱셈하기 -> 시간 복잡도가 O(nlogn)n = 16 # 지수a = 2 # 밑ret = awhile n>=2: if n%2==0: # n이 짝수이면 ret *= r..

문제https://www.acmicpc.net/problem/1629자연수 A를 B번 곱한 값을 C로 나눈 나머지 구하기A, B, C는 모두 2,147,483,647 이하의 자연수풀이A, B, C가 매우 큰 값이므로 직접 A^B%C를 구할 수 없다. (오버플로우 발생)A^B라는 매우 큰 값을 작은 값으로 분할하여 나머지 연산을 해야 한다.분할 : A^B를 작은 값들의 곱으로 치환(아래 그림처럼 B가 짝수일 때, 홀수일 때 다르게 치환됨)-> A^1 될 때까지 분할하기2. 합병 : 작은 값들을 연산한 후 합쳐서 큰 값의 해를 구하기를 반복한다. 여기서 중요한 작업 : 작은 값들을 합쳐 큰 값의 해를 구할 때 [모듈러 연산의 분배 법칙]을 적용해준다.모듈러 연산의 분배 법칙(a + b) % m = ((a %..

문제https://www.acmicpc.net/problem/2805풀이https://nkdev.tistory.com/32 [백준/Java] 2805번 : 나무 자르기✏️ 문제 탐색https://www.acmicpc.net/problem/2805 N개의 나무를 절단해서 윗부분을 가지고 가려고 한다.목재 절단기 높이를 최대 얼마로 정해야적어도 M미터의 나무를 가져갈 수 있는지 구하는 문제이nkdev.tistory.com1월에 풀었던 문제다. 이 때 이분탐색 문제를 많이 풀면서 감을 익혔는데 벌써 어려워지다니풀이는 위 글과 같고 이번에 파이썬으로 풀면서 시간 초과가 떠서 좀 힘들었다. 알고 보니 범위 조절하는 조건문 마다 avail_len(pc)를 호출해서 시간 초과가 발생한 것.. 이 부분을 고쳐줬다. 그..

문제https://www.acmicpc.net/problem/9095n이 입력되면 1, 2, 3만으로 덧셈을 구할 수 있는 방법의 수를 출력한다. 나의 풀이재귀를 사용한 방법이다.1 2 3 중 하나를 선택하는 걸 반복하면서 sum에 더해주다가 sum이 n 되면 cnt를 올려준다.import syst = int(sys.stdin.readline())for i in range(t): N = int(sys.stdin.readline()) cnt = 0 def recur(n, sum_): global cnt if n 다른 풀이점화식과 초기값을 사용해 푼 방법이다. f(n) = f(n-3) + f(n-2) + f(n-1)f(1) = 1 (1)f(2) = 2 (1+1, 2)..