haejun IT

다이나믹 프로그래밍 (DP) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(Top-down, Bottom-up)으로 구성된다. 동적 계획법이라고도 부른다. 일반적으로 프로그래밍 분야에서 동적(Dynamic)이란 어떤 의미를 가질까? 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 ..

3. 프로그램의 기계 수준 표현 3.2 프로그램의 인코딩 gcc 명령은 소스 코드를 실행 코드로 변환하기 위해 일련의 프로그램들을 호출한다. C 전처리기가 #include로 명시된 파일을 코드에 삽입해 주고, #define으로 선언된 매크로를 확장해 준다. 두 개의 소스파일의 어셈블리 버전인 p1.s, p2.s를 생성한다. 어셈블러는 어셈블리 코드를 바이너리 목적 코드인 p1.o와 p2.o로 변환한다. 목적코드는 기계어 코드의 한 유형이다. 마지막으로 링커는 두 개의 목적코드 파일을 라이브러리 함수들을 구현한 코드와 함께 합쳐서 최종 실행파일인 p를 생성한다. 이것이 프로세서가 실행할 정확한 코드의 형태이다. 3.2.1 기계수준 코드 컴퓨터 시스템은 보다 간단한추상화 모델을 이용해서 세부 구현내용을 감추..

백준 숫자카드2 풀이 일단 처음에 문제를 보고 입력이 500,000까지의 범위에 시간 제한이 1초인 것을 보고 문제를 최소한 O(n^2) 이하의 알고리즘으로 구현해야겠다고 생각했다. 입력을 보고 이런 생각을 하는 것을 연습중인데 꽤나 도움이 되는 것 같다. 시간 내에 몇개의 원소가 있는지 확인하려면 Hash를 사용하여 숫자를 Counting하여 비교하면 되겠다고 생각했다. 이를 구현하기 위해서 collections.Counter 라이브러리를 사용했다. Counter 라이브러리의 결과값을 타겟 리스트(m_list)와 비교하여 타겟 리스트의 요소가 Counter 결과값에 존재하면 counting 한 value 값을 프린트 해주면 된다. from collections import Counter import s..

1978. 소수 찾기 풀이 소수란 1과 자신만을 약수로 갖는 수를 뜻한다. 따라서 1 이상의 수에서, 나누기를 했을 때 나머지가 0일 때마다 카운팅을 해 주는데 이때 카운팅이 1이라는 것은 1을 제외하고 자기 자신뿐이라는 뜻이다. 따라서 이때 결과를 카운팅해주면 된다. import sys sys.stdin = open("1978_소수찾기_input.txt", "r") n = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readline().split())) result = 0 for num in nums: cnt = 0 # 숫자마다 카운팅을 해야하기 때문에 초기화 if num > 1: for i in range(2, num+1): if num % i..