본문 바로가기

전체 글21

[컴퓨터 일반] 기억장치 계층 (레지스터, 캐시 메모리, 주기억장치, 보조기억장치) 정리 기억장치 계층컴퓨터의 기억장치는 속도와 용량에 따라서 다음과 같이 나눌 수 있다.레지스터 → 캐시 메모리 → 주기억장치 → 보조기억장치 왼쪽(레지스터)으로 갈수록 속도는 빠르지만 용량이 작고 가격이 비싸다.반대로 오른쪽으로 갈수록 속도는 느리지만 용량이 크고 가격이 저렴하다.그냥 이렇게 생각하면 된다.“빠른 기억장치는 비싸니까 조금만 사용하고, 느린 기억장치는 저렴하니까 많이 사용한다!” 레지스터(Register)레지스터는 CPU 내부에 존재하는 기억장치이다. CPU가 현재 처리하고 있는 명령어나 데이터 등을 임시로 저장한다.레지스터는 기억장치 중에서 속도가 가장 빠르다. CPU 안에 있으니까 데이터를 가져오기 위해 멀리 갈 필요가 없기 때문이다.하지만 레지스터는 만들기 어렵고 가격이 비싸기 때문에 용.. 2026. 7. 29.
[C언어] 전위 연산자, 후위 연산자 증감연산자 증감연산자는 말 그대로 변수 값을 1 증가시키거나 1 감소시키는 연산자이다. ++ : 증가연산자로 변수 값을 1 증가시킨다. -- : 감소 연산자로 변수 값을 1 감소시킨다. 증감 연산자는 ++/--(연산자)의 위치에 따라 전위 연산자와 후위 연산자로 나뉜다. 전위 연산자 ++변수, --변수 변수명 앞에 연산자가 붙어있으며, 증감연산이 끝난 변수를 이용해 남은 연산이 진행된다. 7번째 라인을 살펴보면 ++a를 출력하고 있다. ++연산자가 변수 앞에 붙어 있으므로 a의 값을 1 증가시켜 준 다음에 printf가 실행된다. 따라서 0 + 1의 값이 출력되는 것이다. 10번째 라인도 변수 앞에 --연산자가 붙어 있으므로 b의 값을 1 감소시켜 준 다음에 출력해 준다. 따라서 1 - 1인 0이 출력될.. 2023. 11. 15.
2022 국가 자료구조(나) 9번 해설 정답) 3 이 문제는 포인터 배열에 관한 문제이다. 우선 쉽게 설명하자면 *이 붙어있으면 값을 나타내고 *이 안 붙으면 위치(주소값)를 나타낸다고 생각하자. 5번째 라인을 살펴보면 *p = array + 2라고 선언되어 있다. 여기서 array는 배열의 시작주소가 들어가 있으며 array + 1은 두 번째 요소의 주소, array + 2는 세 번째 요소의 주소가 들어간다. 그냥 아래의 그림처럼 배열의 위치를 가리킨다고 생각하면 된다. 따라서 현재 p는 array + 2가 가리키는 위치가 들어가 있다. 이를 생각하며 문제를 풀어보자. 7번째 라인은 *(p-1)의 값을 출력하고 있다. 현재 p는 array + 2이며, 2의 주소값을 가리키고 있다. 여기서 p-1을 하게 된다면 1의 주소값을 가리키게 될 것이.. 2023. 11. 14.
2022 국가 자료구조(나) 8번 해설 정답) 4 이 문제는 도트연산자(.)와 화살표 연산자(→)에 관한 문제이다. 화살표와 도트 연산자는 구조체 변수에 접근할 때 사용하는 연산자인데, 간단하게 말하면 둘의 차이는 변수를 사용해서 접근하느냐, 포인트를 사용해서 접근하느냐의 차이이다. 도트연산자: 구조체 변수를 이용하여 접근 화살표연산자: 포인터를 사용하여 접근 A → x; (*A). x; 위의 두 결과는 같다. 단지 접근하는 방식이 다르다고 생각하면 된다. 이제 코를 살펴보자. MAX=5이기 때문에 노드 5개가 만들어진다. 이제 노드들을 연결시켜 주자. 노드들은 순서대로 연결이되는데 마지막 노드를 첫 번째 노드로 연결시켜 원형연결리스트를 만든다. 모든 노드의 합을 구하려면 노드의 값을 읽어와야한다. 그래서 (가)는 값을 불러오는 (*p). b.. 2023. 2. 12.
2022 국가 자료구조(나) 7번 해설 정답) 3 AVL 트리의 특징은 아래와 같다. 이진탐색 트리의 특징을 따른다. 왼쪽서브트리와 오른쪽 서브트리의 높이 차이는 1을 넘지 않는다. 높이 차이가 2 이상이면 RR회전, LL회전, RL 회전, LR회전을 통해서 균형을 맞춘다. 이 특징들을 따르는 AVL 트리를 한번 그려보자. 데이터 6, 7, 8을 순서대로 입력받으면 아래와 같은 트리가 그려진다. 8을 입력하고 보니 트리의 균형이 맞지 않다. 루트 6을 기준으로 왼쪽 서브트리 높이가 0, 오른쪽 서브트리 높이가 2이다. AVL 트리 특징 2번을 살펴보면 높이 차가 1을 넘어서는 안되기 때문에 이 트리는 회전이 필요하다. 현재 트리의 모양을 살펴보면 오른쪽으로 기울어져 있다. 그렇기 때문에 RR회전이 필요하다. 여기서 RR회전이 '오른쪽으로 회전.. 2023. 2. 3.
2022 국가 자료구조(나) 5 ~ 6번 해설 정답) 2 스택의 기본연산 push(i): 스택에 i 추가 pop(): 가장 마지막에 들어온 data 삭제 peek(): 스택 가장 윗 데이터 반환 여기서 pop()과 peek()의 차이점은 pop은 data가 삭제가 되지만, peek()는 삭제가 되지 않고 반환만 된다는 점이다. 이를 기억하고 문제를 풀어보자. 정답) 1 다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘이다. 모든 정점을 탐색하며 최단 거리를 계속해서 갱신하는 것이 특징이다. 글로는 이해하기 어려우니 문제를 통해서 살펴보자. 우선, 정점 A로부터 다른 정점까지의 거리를 표로 나타내었다.연결되어있지 않은 정점들은 ∞로 표시하고, (A, B) = K 는 A에서 B까지의 거리가 K라는 의미로 사용하겠다. A B C.. 2023. 2. 1.
2022 국가 자료구조(나) 4번 해설 정답) 3 ㄱ. 이진트리의 노드수가 최대가 되려면, 내부 노드가 모두 2개의 자식을 갖는 포화이진트리이면 된다. 포화 이진트리 노드의 개수는 2^(높이)-1로 구할 수 있다. 현재 높이가 5이므로 2^5 - 1 =31이 나온다. 공식이 생각나지 않더라도 노드의 개수가 2^0 + 2^1 + 2^2 + 2^3 ··· 이렇게 증가한다는 것을 알면 쉽게 구할 수 있다. ㄴ. 간선은 노드와 노드를 연결해주는 선이다. 2개의 노드를 연결하기 위해서는 1개의 선, 3개의 노드는 2개의 선.. 이렇게 생각해보면 간선의 개수는 노드-1개라는 것을 알 수 있다. ㄷ. 부모노드 인덱스를 i라고 가정하면, 왼쪽 자식은 2*i, 오른쪽 자식은 2*i + 1이 된다. 아래 트리를 통하여 알아보자. 트리에 노드들의 인덱스 값을 적.. 2023. 1. 26.
2022 국가 자료구조(나) 해설 1~3번 정답) 3 N : 노드의 개수 무방향 신장트리 : (N * (N - 1)) / 2 방향 신장트리 : N * (N - 1) 위의 식은 외워두는게 편하다. 공식에 대입해보면, (3 * 2)/ 2 = 3 이다. 정답) 3 중위 순회는 left → root → right 순으로 방문하는 것을 말한다. 루트를 중심으로 왼쪽자식을 방문한 후 오른쪽 자식을 방문하면 된다. 따라서 [4, 2, 5, 1, 6, 3, 7]이 나온다. 추가로 전위 순회와 후위 순회까지 살펴보면, 전위순회는 root → left → right 순으로 방문하고 [1, 2, 4, 5, 3, 6, 7]이 나온다. 후위 순회는 left → right → root 순으로 방문하며 [4, 5, 2, 6, 7, 3, 1]이 나온다. 전위, 중위, 후위는.. 2023. 1. 19.
2022 서울시 자료구조(A) 해설 14, 20번 정답) 1번 시간복잡도는 n에 관한 식을 정리하면 쉽게 구할 수 있다. n에 적당한 수를 넣어 n에 관한 식으로 정리해 보자. 위의 표는 N의 값에 따라서 첫 번째, 두 번째 for문이 몇 번 도는지 체크해 본 것이다. N = 2인경우만 살펴보면 N= i =2일 때 두 번째 for문이 j=0, j=1로 2번 돌아간다. 그다음 i /=2 조건 때문에 i가 1이 되고 j = 0일 때 한 번만 수행되어 총 2 + 1번 수행된다. 이제 N의 값에 대하여 for문 수행 횟수를 일반화시켜 보자. N = 2일 때 2 + 1번, N = 3일 때 3 + 1번, N = 5일 때 5 + 2 +1번이 수행된다. 이 식을 가만히 들여다보니 규칙이 보인다. N + N / 2 + N / 2^2 +... 이 식을 정리하면 N(1 +.. 2023. 1. 15.
2022 서울시 자료구조(A) 해설 17 ~ 19번 정답) 1 이 문제는 예시를 들어서 풀고 편의를 위해서 노드(진입차수, 진출차수)로 표현하겠다. 인접행렬은 A [x][y]는 노드 x에서 y로 가는 간선이 있다면 1, 없으면 0으로 표현할 수 있다. 그래서 위의 방향 그래프의 인접행렬은 아래와 같다. 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 인접행렬을 다 구했으니 진입차수, 진출차수를 구해보자. 0번 노드를 기준으로 살펴보면, 진입차수는 A [x][0]의 값을 다 더하면 구할 수 있음을 알 수 있다. 왜냐하면 진입차수란, 다른 노드에서 0번 노드로 들어오는 간선들의 개수이기 때문이다. 그렇다면 반대로 진출차수는 A [0][y]의 값을 다 더하면 구할 수 있을 것이다. 0의 진입차수는 0 [0][0] + 0.. 2023. 1. 11.
728x90

티스토리툴바