목록코딩 (332)
미새문지
프로세스(Process) 운영체제에서 실행 중인 프로그램의 인스턴스 프로세스는 각각 독립된 메모리 영역을 가지고 있고, 다른 프로세스와 격리되어 있다. 이 메모리 공간은 일반적으로 코드 섹션, 데이터 섹션, 스택 섹션 세 가지로 구분되어 있으며 힙 영역이라는 동적 메모리 할당 영역도 존재한다. 코드 섹션 프로세스가 실행할 프로그램 코드를 저장한다. 이 영역은 읽기 전용이며, 프로세스가 실행되는 동안 변경되지 않는다. 데이터 섹션 프로세스의 전역 변수와 정적 변수를 저장한다. 이 영역은 프로세스가 실행되는 동안 값이 변경될 수 있다 스택 섹션 함수 호출과 관련된 정보(지역변수, 반환주소 등)를 저장한다. 함수 호출이 발생할 때마다 스택 프레임이 생성되고, 함수 호출이 완료되면 스택 프레임이 제거된다. 각 ..
배열과 포인터의 관계 배열: 배열은 여러 개의 데이터를 연속적인 공간에 저장하는 자료구조이다. 예를 들어, 5개의 정수를 저장하는 배열은 메모리에서 연속된 5칸을 차지한다. 배열은 인덱스를 사용하여 특정 위치의 값을 읽거나 쓸 수 있습니다. 포인터: 포인터는 주소값을 가지는 변수이다. 자신이 데이터를 저장할 공간을 가지지 않고, 데이터가 저장된 주소를 가리킨다. 포인터는 변수이므로 값을 변경할 수 있다. 배열과 포인터의 관계 배열의 이름은 배열의 첫 번째 요소를 가리키는 포인터로 간주될 수 있어 포인터처럼 동작한다. 따라서 배열의 이름은 사실상 포인터이다. 하지만 배열의 이름은 포인터와 달리 재 할당이 불가능한데, 배열의 이름은 그 자체로 주소이며, 변경할 수 없는 상수이다. 배열의 이름과 포인터 변수의..
레드-블랙 트리(Red-Black Tree) 자가 균형 이진 탐색 트리(Self Balance Binary Search Tree) RB트리를 만족하기 위한 조건 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 빨간색 노드의 자식은 검은색이다. 빨간색 노드가 연속으로 나올 수 없다. 모든 리프 노드에서 Black Depth는 같다 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 조건 5번 속성을 만족해야 성립하는 개념 노드 x의 black height 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트..
동적 메모리 할당 실행 중(런타임)에 사용할 메모리 공간을 할당하는 것을 의미한다. 정적 할당(static allocation) 프로그램이 실행되기 위해서는 메모리가 필요한데 컴파일러는 컴파일 시점에 소스 코드를 읽고 변수 타입들의 크기에 따라 메모리를 할당한다. 동적 할당(dynamic allocation) 컴파일 타임이 아닌 프로그램 런타임에 필요한 만큼의 메모리 공간을 확보하는 것을 의미한다. 동적 할당이 필요한 이유 사용할 때마다 필요한 만큼만 메모리 공간을 확보하고 다 사용했다면, free시켜줌으로써 메모리 공간을 해제해 한정된 메모리 공간을 효율적으로 사용할 수 있게 된다. 함수가 종료되거나 변수의 영역을 벗어나면 자동으로 메모리가 해제되는 정적 할당은 스택에 저장된다. 하지만 동적 할당은 힙..
c언어에서는 두 종류의 소스 코드 파일이 있다 c파일(.c) 실제 프로그램을 돌게 하는 로직 코드 파일 내용 : 함수, 매크로, 변수 등 헤더 파일(.h) 여러 소스 코드 파일에 공통적으로 필요한 것들을 저장하는 파일 내용 : 함수 선언, 매크로, extern 변수 선언 등 #include로 헤더 파일을 작성 헤더 파일의 필요성 함수가 선언된 헤더 파일을 작성하면 여러 파일과 공유가 가능하다. 수정할 때 관련 파일이 많으면 모두 고치기 불편하기 때문에 유지 보수에 어려움이 생긴다. 포인터 데이터가 저장된 메모리의 주소 값을 저장하는 변수이며, 포인터 변수라고도 부른다. 메모리의 주소가 어디인지를 저장하는 전용 변수 특징 포인터를 통해 프로그램의 변수에 접근하여 읽고 쓰거나, 함수를 실행할 수 있다. 자료..
가장 긴 부분수열 수열 A가 입력되면 가장 긴 증가하는 부분 수열 구하기 import sys input = sys.stdin.readline def longLCS(a): # 받은 문자열의 길이를 체크 length = len(a) # 처음 시작을 1로 해야 원소가 처음 나올때 1이 체크된다. list = [1]*length # 처음껀 비교대상이 없기 때문에 1부터 시작 for i in range(1, length): # i 이전 수들끼리 비교해야 하기 때문에 i까지 반복 for j in range(i): # i값이 j값보다 크고(증가 수열) 리스트에 i를 넣었을 때 기존 리스트보다 길면 갱신 if a[i] > a[j] and list[i] < list[j]+1: list[i] = list[j]+1 # 리스..
스택과 레지스터의 용도와 장점 스택 프로시저 호출 시 지역 변수와 매개변수를 저장하기 위한 메모리 공간이며, LIFO(Last in First Out)이라는 마지막에 들어온 값이 먼저 나가는 구조를 가지고 있다. 용도 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장된다. 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다. 장점 동적으로 메모리를 할당하고 해제할 수 있다. 구현이 간단하며, 메모리 관리의 오버헤드가 낮다. 레지스터 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용 용도 중간 연산 결과 저장 : 연산 중 생성되는 중간 값을 빠르게..
피보나치2 피보나치를 재귀방식이 아닌 DP방식으로 풀기(동적 프로그래밍) import sys def fibo(n): list = [0, 1] + [0]*(n-1) for i in range(2, n+1): list[i] = list[i-1] + list[i-2] return list[n] n = int(sys.stdin.readline()) print(fibo(n)) 01타일 1또는 00만을 이용해서 n개의 타일을 깔수있는 경우의 수를 구하기(동적 프로그래밍) import sys n = int(sys.stdin.readline()) pibo = [0, 1] m1 = 0 m2 = 0 i = 0 while i != n: m1 = pibo[0] + pibo[1] m2 = pibo[1] pibo[0] = m2 ..