[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.
[C, C++] 포인터

[C, C++] 포인터

서늘한 이 감각, 이걸 또 보게 되다니 ㅠㅠ포인터의 개념변수의 메모리 주소 값을 말한다. 이 포인터를 담는 변수를 포인터 변수라고 한다.포인터 변수가 어떤 변수의 주소를 저장하고 있다는 것은, 포인터 변수가 그 변수를 가리키고 있다를 의미한다.포인터 변수를 이용하여, 연결된 주소의 변수 영역을 액세스 할 수 있다.포인터 변수를 간단하게 포인터라고 부른다.포인터의 사용 예제int i;int *ptr = &i;자료형 *포인터이름;자료형 : 포인터 자체의 자료형이 아니라 포인터에 저장 할 주소에 있는 일반 변수의 자료형을 적는다.*포인터이름 : 일반 변수 이름과 구별되도록 앞에 *를 붙여 포인터임을 나타낸다.포인터 연산자주소 연산자 : &변수의 주소를 얻기 위해 사용한다주소 연산자의 사용 형식은 이와 같다.p..

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

Greedy

번역할 때는 탐욕법이라고 번역을 하기도 하고, 그냥 그리디 알고리즘이라고도 부른다.여기서 그리디는 뒷일 생각하지 않고 가장 좋아보이는 것부터 하나씩 순서대로 처리하는 것이다.부분 가방 문제 등이 해당한다.명확한 기준 하나를 정하고 그 기준에 따라 미리 정렬을 한 다음에 하나씩 처리해나가는 방식이 있다.하나씩 순서대로 처리하기 때문에 :문제 크기가 순차적으로 줄어드는 구조이다.전체의 시간 복잡도가 정렬의 시간 복잡도에 의해 결정된다.최적화 문제를 다룬다는 점에서 비슷한 점이 있는 Dynamic Programming과 비교해보자.DP는 결정 트리에서 분기하는 경우들을 다 따져본다. 근본적으로는 여러가지 가능성을 전부 고려한다고 볼 수 있다.그리디는 분기를 고려하지 않는다. 분기를 고려 할 필요가 없는 상황에..

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