[PY] 12865 : 평범한 배낭

https://www.acmicpc.net/problem/12865점화식 세우지 못한 상황을 받아들이고 그냥 한 번 아이디어 보면서 만들어보니 되긴 되더라.근데 막판에 인덱스 관련해서 좀 많이 얼타가지고 파일럿 코가 해결해주었다.어느 순간 파일럿 코에게 코드의 끝 마무리 할 기회를 던지는 것 같아서 기분이 안좋다. 처음부터 끝까지 내가 한 코드가 있는걸까.핵심 식은 2차원 배열에 각 가방과 짐에 대한 점진적 배치 또는 증가 식을 놓는다.담을 수 없어?그럼 [i - 1][j] 과 동일하다.담을 수 있어?그럼 [i - 1][j] 랑 해당 아이템을 포함한 데이터를 구성하여 그 중 더 많은 가치의 값으로 구성한다.itemList[j].value + bag[i - itemList[j].kg][j] 뭐 이런식.. ..

• format_list_bulleted 문제풀이
• · 2025. 4. 6.

책 열심히 읽기

책을 읽으면서 기술적인 연습문제에 대해 논하고 싶다가도 뭔가 저작권이 걸릴까봐 특정한 연습문제를 언급하는게 아니라면 못하겠다. 그래도 하루에 뭔가 하고 있다를 티를 내야하는데..이번 주, 양 너무 많다 진심. 다음 주는 과목 전개가 완전 달라져서 더 심각할거라고 한다.다들 슬슬 딴 길로 빠지는 듯한 분위기가 보여서 슬프다.나조차 놀고 싶고 쉬고 싶은 마음이 가득한지라 그것들의 유혹에 강하다라고 함부로 보장 할 수는 없다.근데 어떻게 보면 지금이 제일 중요하다. 지금 당장 안해도 되는 것들은 제발 좀만 나중에 다루고 싶다.서류 하나 떼는 작업 조차 흐름 끊기는 것 같아서 기분이 안좋다.

• format_list_bulleted 별 잡다
• · 2025. 4. 5.

[PY] 11047 : 동전 0

https://www.acmicpc.net/problem/11047그리디 알고리즘을 사용하는 아주 간단한 문제이다.아이디어는 이렇게 구상한다.입력으로 동전 갯수, 필요한 요구 금액, 동전 종류를 입력받는다.동전 종류는 내림차순으로 정렬한다. 큰 수부터 대 봐야 하기 때문이다.동전이 빠져도 유효한 상황인 경우에만 동전의 금액을 필요한 요구 금액에서 뺀다.여기서 유효한 상황은, 동전이 빠졌을 때도 잔액이 0 이상이여야한다.끝!import sysinput = sys.stdin.readlinecoinCnt, req = map(int, input().split())coinList = [0] * coinCntresultCnt = 0for i in range(coinCnt): insertCoin = int(in..

• format_list_bulleted 문제풀이
• · 2025. 4. 5.

[PY] 2748 : 피보나치 수 2

https://www.acmicpc.net/problem/2748정직 우직 묵직한 나의 DP 두둥등장 fArr = [0] * 100fArr[0] = 0fArr[1] = 1for i in range(2, 91): fArr[i] = fArr[i - 1] + fArr[i - 2]finding = int(input())print(fArr[finding])

• format_list_bulleted 문제풀이
• · 2025. 4. 5.

[PY] 1904 : 01타일

https://www.acmicpc.net/problem/1904뭐 이딴 문제가 있나 싶었는데 그냥 피보나치 수열 문제였다. (15746 이라는 별 상관없는 숫자를 나눠야 하는)Arr = [0] * 1000001Arr[1] = 1Arr[2] = 2Arr[3] = 3for i in range(4, 1000001): Arr[i] = (Arr[i - 1] + Arr[i - 2]) % 15746num = int(input())result = Arr[num] print(str(result))

• format_list_bulleted 문제풀이
• · 2025. 4. 5.

Amortized Analysis : 분할 상환

알고리즘의 성능을 분석하는 방법 중 하나이다. 최악의 경우에도 평균적인 실행 시간을 측정하는데 사용한다.단일 연산에 초점을 맞추는 대신, 여러 연산을 수행 한 후 전체 평균 비용을 계산한다.간단한 예시 : 증가 가능한 배열, Resizing Array정적 배열에서 크기가 부족 할 때 동적으로 배열 크기르 늘리는 상황을 생각해보자.배열이 full이면 배열의 크기를 두 배씩 늘린다고 가정한다.각 크기 증가 시, 기존 배열의 모든 요소를 새 배열로 deepcpy 해야한다.계산 과정배열에 요소를 추가 할 때대부분의 경우 요소 추가 비용은 N(1) 상수 시간에 가능하다.하지만, 배열 크기를 늘릴 때는 복사 비용이 발생하므로, O(n) 비용이 든다. (n : 배열의 기존 크기)이 연산을 Amortized Analy..

• format_list_bulleted 컴퓨터 이론
• · 2025. 4. 4.