🎯 To-do List
✅ 백준 1문제 풀기
☑️ 6장 공부
☑️ c++ 공부
📝 c언어, 알고리즘 특강
재귀 복습
재귀는 점화식이다
def hanoi(n):
if n==0:
return 0
return 2*hanoi(n-1)+1하노이의 탑
int count(struct Node* r)
{
if(r == NULL)
{
return 0;
}
return 1+count(r->left)+count(r->right);
}트리의 모든 노드 수
C 언어 개념
포인터 크기 비교
| sizeof() | 32비트 시스템 | 64비트 시스템 |
|---|---|---|
int* | 4 | 8 |
char* | 4 | 8 |
int* p는 총 몇 MB를 가리킬 수 있나?
32bit : 0x00000000 ~ 0xFFFFFFFF 4byte의 메모리 크기만큼의 공간을 가리킬 수 있음
64bit : 0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF 8byte만큼 가리킬 수 있음
엔디언 Endianness
리틀 엔디안 : intel, AMD
빅 엔디안 : 모토로라
혼용 : ARM
리틀 엔디안 : 값을 거꾸로 읽어서 저장함
빅 엔디안 : 값을 그대로 읽어서 저장함
대부분은 인텔 기반 윈도우 쓰니까 리틀 엔디안인데
네트워크로 통신할 땐 빅 엔디안 씀
연산자
단항 연산자 (unary operator) : 피연산자가 1개, +,-, ...
이항 연산자 (binary operator) : 피연산자가 2개, +=, -=, = ...
삼항 연산자 (ternary operator) : 피연산자가 3개, a ? b : c
int *p = 0x01;
int d = 0x01;p++ 하면 (32bit: 5, 64bit: 9)
d++ 하면 2
c++에선 피연산자 타입마다 동작 다르게 할 수 있음
python도 사실
"ab"+"cd"="abcd"
ab + cd = 5
이렇게 타입 따라 연산자 동작 다름
포인터
int**p = 0x01;
p++;32bit 5 (주소값 공간 4byte)
64bit 9 (주소값 공간 8byte)
int A[5];
int *A; // 둘 다 같은 거임A[0] = 1
A = 1;
(A+1) = 2;
(가상) 메모리 구조
static int s=0;
char *a = "abcd"
int main() {
int b;
int *c;
d = malloc(sizeof(int));
return 0;
} s, a는 initialized, uninitialized data에 쌓임
b, c는 stack에 쌓임
d는 headp에 쌓임
stack은 위에서 아래로 쌓임
heap은 아래에서 위로 쌓임
char*
char *s = "abcd";
printf("%d", s); // 주소가 적힘
printf("%s", s); // abcd (NULL이 나올때까지의 값들을 문자로 변환하여 출력)포인터와 이중 포인터
포인터 : int를 담고 있는 메모리를 가리킴
이중 포인터 : int* 를 담고 있는 메모리를 가리킴
이중 포인터는 언제 쓰는가?
Call by Value, Call by Reference 개념을 알아야 됨
C는 무조건 Call by Value임
python은 타입마다 다름
int func(int b)
{
a++;
return 0;
}
int b=0;
func(b);
printf("%d",b); // 출력 0Call by Value라서 이렇게 되는거
b 값을 바꾸고 싶으면 매개변수에 &b를 넣었어야 함
근데 return으로 해도 되는거 아님?
: 맞긴 한데 여러 개 바꿀 땐 포인터가 간편
그리고 상황 따라 return 못 쓰는 경우도 있음
📖 CS:APP
📝 Chapter 6 메모리 계층구조
크고 느린 저장장치들은
작고 빠른 저장장치들을 위한 준비 장소(캐시)로 사용된다
메모리 계층구조는 성능에 영향 많이 끼침
데이터가 CPU 레지스터에 있으면 0사이클에 접근 가능
캐시에 저장돼있으면 4~75 사이클
메인 메모리에 저장돼있으면 수백 사이클
디스크라면 수천만 사이클
지역성 : 지역성이 좋으면 비슷한 데이터들만 자주 사용. 자주 사용하는 것만 작고 빠른 메모리 더 많이 사용하게 하면 됨.
크고/작고 느리고/빠르고 는 상대적인거니까
나열해놓으면 메모리 계층(Memory Hierarchy)
6.1 저장장치 기술
6.1.1 랜덤-접근 메모리
랜덤-접근 메모리(RAM)은 두 종류
- 정적 램(SRAM) : DRAM보다 빠르고 훨씬 더 비쌈. 캐시 메모리로 쓰임.
- 동적 램(DRAM) : 메인 메모리, 그래픽 시스템의 프레임 버퍼로 사용됨
일반적으로 데스크톱은 SRAM 수십MB와 DRAM 수천MB 가짐
정적 램(SRAM)
불안해도 빠르게 안정적으로 변함. 역삼각형 세워놓으면 계속 떨어지는 느낌.
그래서 전원이 공급되는 한 값이 휘발되지 않고 안전하게 유지됨.
각 셀은 4~6개의 트랜지스터로 이루어진 회로를 사용해서 1비트를 저장함. 그래서 비쌈.
근데 접근 속도 빠르고 방사선같은 외부 방해 요소에 크게 영향 안 받음.
동적 램(DRAM)
각 비트를 축전기에 엄청 작은 전하로 저장함. 외부 자극에 민감함. 햇볕 한 번 쬐면 전압 변함.
전류가 자꾸 새서 전하가 점점 감소하므로 메모리의 모든 비트를 전부 읽었다가 다시 써서 refresh해줘야됨.
메모리 셀을 여러 개 묶은 슈퍼셀에 비트 하나를 저장해서 데이터 안정성 향상시킴.
보낼 때도 슈퍼셀로 묶어서 보내면 주소도 줄어들고 좋음.
Fast page mode DRAM (FPM DRAM)
슈퍼셀 행 보낸 데이터들 그냥 버리는게 아니라 같은 행 주소에 있는 데이터 필요하면 행 버퍼에 있던거 바로 줌
Video RAM(VRAM)
VRAM은 그래픽 시스템의 프레임 버퍼로 사용됨.
FPM DRAM하고 비슷한데 둘의 큰 차이는
1. VRAM 출력은 내부 버퍼의 전체 내용을 순차적으로 이동시켜서 만듦
2. VRAM은 메모리를 동시에 읽고 쓸 수 있음
그래서 프레임 버퍼 내에 픽셀들로 화면을 칠할 수 있고(읽기), 동시에 새로운 갑을 다음 갱신을 위해 쓸 수 있음(쓰기)
비휘발성 메모리
DRAM과 SRAM은 전원이 꺼지면 정보도 잃어버리는 휘발성 메모리들임.
비휘발성 메모리들은 전부 Read-only memory(ROM)이라고 부름.
사실 읽기도 되고 쓰기도 되는데 역사적인 이유로 그렇게 부름.
-
Programmable ROM(PROM)은 딱 한 번만 프로그래밍할 수 있음. 메모리 셀에 전류 세게 주면 한 번에 끊어지는 퓨즈 갖고 있음.
-
Erasable programmable ROM(EPROM)은 자외선이나 X-Ray로 정보 지울 수 있음
-
Electrically erasable PROM(EEPROM)은 PCB에서 재프로그램할 수 있는 EPROM임.
-
Flash memory는 EEPROM에 기반을 둔 비휘발성 메모리의 일종.
ROM에 저장된 프로그램들은 펌웨어(firmware)라고 부르기도 함.
컴퓨터 키면 ROM에 저장된 펌웨어를 실행시킴.
일부 시스템은 펌웨어에 BIOS(basic input/output system) 같이 적은 수의 기본 입출력 함수를 제공함.
그래픽카드나 디스크 드라이브 컨트롤러 같은 복잡한 장치들도 CPU로부터의 입출력 요청을 처리하기 위해 펌웨어에 의존함.
메인 메모리 접근하기
데이터는 버스(Bus)라고 하는 전기 회로를 타고 프로세스와 DRAM 메인메모리 사이를 이동함.
버스는 해당 CPU의 워드 사이즈만큼의 데이터를 실을 수 있음.
6.1.2 디스크 저장장치
⚔️ 백준
📌 15650 N과 M (2)
N, M = map(int, input().split())
arr = [i for i in range(1,N+1)]
def permutation(arr, case):
if len(arr) == N-M:
for i in range(len(case)-1):
if case[i] > case[i+1]:
return
for n in case:
print(n, end=' ')
print()
return
for i in range(len(arr)):
case.append(arr[i])
permutation(arr[:i]+arr[i+1:len(arr)],case)
case.pop()
permutation(arr,[])오름차순이라고 하는게 수열들이 오름차순이라는 줄 알고 이전 코드 그대로 복붙해봤는데 안됨.
다시 보니까 원소들이 오름차순이라는 의미.
그 전 코드에 수열들이 오름차순인지 확인하고 아니면 거르는 것만 추가했더니 일단 맞긴 했다.
오름차순이 아닌 수열들도 탐색을 한 뒤 다시 제거를 하는 불필요한 과정이 들어갔기에 효율적인 코드는 아님.
찾아보니 애초에 오름차순인 수열만 찾아내는 방법도 있고
트리를 이용하는 방법도 있었다
백트래킹을 트리 구조로 이해해도 좋을듯?
전역 변수로 지정된 배열에 이미 사용된 숫자들을 넣어도 되는건가? 생각했는데
트리로 구체화해서 생각해보니 이해가 간다.
