지난 글에서는 SPARC의 (근데 찾아보니 아마도 기본적인 컴퓨터 공통의) 메모리 맵을 정리하면서 BSS 섹션의 내용을 추가로 정리하였다. bss 섹션은 정적 메모리 영역 중 하나로, 이곳에 할당한 변수는 모두 0으로 초기화되는 특징이 있었다. 이번 글에서는 다시 '스택' 영역으로 돌아와서, 새로운 스택 영역의 메모리를 할당하는 단위인, '스택 프레임' 에 대해 정리하고자 한다. Stack Frame (스택 프레임) 스택 프레임은 나중에 정리할 '서브루틴' 과 관련되어 있다. 서브루틴(함수)는 호출될 때마다, 레지스터 공간과 함께 스택 공간을 새로 할당한다. 이때 각 함수마다 할당하는 스택 공간의 크기를 임의로 지정할 수 있는데, 이 스택 공간을 '스택 프레임' 이라고 한다. 즉, 스택 프레임은 서브루틴..

지난 글에서는 set 합성 명령어의 구조와 작동 원리를 알아보았다. set 명령어는 sethi 명령어와 or 명령어의 조합으로 이루어져 있으며, sethi 명령어는 피연산자로 들어온 메모리 주소값의 상위 22비트를 마찬가지 피연산자로 들어온 레지스터의 상위 22비트에 쓰는 명령어이다. or 명령어로는 나머지 하위 10 비트의 데이터를 레지스터의 하위 10비트에 쓴다. (32비트의 주소값 데이터를 2번에 걸쳐 레지스터에 쓴다.) 이번 글에서는 SPARC의 메모리 맵을 다시 한번 살펴보면서 지난번에 정리하지 못했던 정적 메모리 영역 중 bss 영역에 대해 추가적으로 정리하고자 하려고 했으나... 강의록에 bss 부분에 대한 내용이 너무 없어서 그냥 SPARC 메모리 맵을 복습하는 느낌으로 작성하려고 한다. ..

https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 학교 동아리 스터디에서 세그트리 연습문제로 나와 풀게 되었다. 스터디 수업때 다뤘던 연습문제와 세그트리를 적용하는 결이 달라 한참 고민을 하고 풀었다. 보통 '세그먼트 트리' 하면 유명한 연습문제가 '구간 합 구하기' 이다. https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,0..

data영역 메모리에 데이터를 저장하고 나서 메모리에 저장된 데이터를 가져오기 위해 그 메모리 위치를 label로 표시할 수 있다. 이때, 문자열로된 label로부터 실제 메모리 주소값을 가져오는 명령어가 set 이다. .data i_m: .word 4 j_m: .word 9 k_m: .word 3 위 코드에서는 data 영역에 4바이트 크기의 메모리 공간 3개에 각각 4, 9, 3을 저장하고, 각 메모리 주소를 i_m, j_m, k_m 으로 표시하였다. 이때 i_m, j_m, k_m 이 가리키는 메모리 주소는 아래와 같이 가져올 수 있다. set i_m, %o0 위 코드는 i_m의 주소값을 가져와서 %o0 레지스터에 저장하는 코드이다. 한편, 지난 지연주기 최적화 글에서 set은 nop에 바로 넣을 수..

https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 에라토스테네스의 체를 구하는 과정을 응용하여 푸는 문제이다. 수가 10만개 이므로, 임의 두 수의 쌍을 모두 구해서 대결을 시키는 것은 시간내에 풀 수 없다. 1. 미리 1부터 100만까지 모든 수에 대한 점수를 저장할 리스트를 만들어 두고, None으로 초기화를 시켜둔다. (점수가 음수가 될 수 있기 때문이다) 2. 플레이어가 가진 수로 주어진 모든 수에 대해 점수를 0으로 설정한다. 3. 각 플레이어..

원래는 12월에 올해 회고로 몰아서 쓰려고 했는데, 이번 달은 뭔가 이벤트가 많았다보니 이 경험들을 지금 생각날 때 글로 정리하고 싶어서 미리 쓰게 되었다. 작년 회고글 마지막에 2023년에 하고 싶은 것들 쭉 적어둔게 있었는데, 그거는 2023년 회고에서 얼마나 이뤘는지 리뷰를 해보려고 한다. 그런데 그때는 프론트에 관심이 많았지만, 지금은 프론트 관심이 조금 떨어져서 그런가 그때 세운 목표와 내가 지금까지 해온 것들의 차이가 있다. 암튼 이 내용은 2달 뒤에 정리해서 적어봐야겠다. 지난 회고글을 월별로 나눠서 적었는데, 지금 읽어보니까 조금 읽기 불편한 방식으로 글을 구성한 것 같아서 이번에는 이벤트 단위로 끊어서 시간 순으로 적되, 제목을 확실히 달아서 쭉 적어보려고 한다. 추석 연휴 (~10/3)..

https://www.acmicpc.net/problem/30105 30105번: 아즈버의 이빨 자국 집안의 먹을 것들이 계속해서 사라지는 당신은 이웃집의 곰 아즈버(azber)를 의심하고 있다. 오늘, 당신은 드디어 결정적인 증거를 찾아냈는데, 그것은 바로 쵸코바에 찍힌 이빨 자국이었다! 당신 www.acmicpc.net 처음 문제를 읽었을 때는 감이 안왔는데, 시간 제한을 보고 브루트포스라는 감을 잡아 풀었다. N의 사이즈가 4000개이므로, 임의 2개의 점 사이 모든 간격을 구하는데 1.6 * 10^7 의 연산이 필요하고, 이는 3초안에 충분히 가능한 연산이다. 나는 임의 두점 x1, x2 사이의 거리를 구하고, 해시맵에 그 거리를 key 로 하여 그 거리를 구성한 점들을 set으로 저장했다. Ma..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 개수와 각 추의 무게가 주어졌을 때, 주어진 추들을 양팔 저울에 올려 측정할 수 있는 무게의 종류를 구하는 문제이다. 추를 양팔 저울의 한 쪽에만 올리는 경우와 다른 반대쪽에도 올릴 수 있는 경우가 있다는 점이 이 문제의 어려운 점이다. 측정하려는 무게를 x, 현재 사용하는 추의 무게를 w, 이전까지 측정한 적 있던 무게를 p 라고 하자. 그렇다면 측정하려는 무게를 양팔저울의 왼쪽에 놓았을 때..

지난 글에서는 이진 탐색트리의 개념과 Search, Add, Delete 의 구현에 대해 정리하였다. 이번 글에서는 BST의 핵심인 '탐색' 과 탐색 시간에 대해 좀 더 깊게 정리해보자. BST의 탐색 시간 모든 BST의 기능 중에서 제일 중요한 것은 BST 의 이름에도 들어있는 '탐색' 기능이다. 탐색 시간이 얼마나 걸리는지 ( 탐색을 위해 비교를 몇 번이나 하는지) 는 어떻게 측정할까? 답은 정확하게 BST 의 노드 중 찾으려는 노드의 depth + 1 (level + 1) 이다. 더보기 [트리에서 Depth, Height, Level ] Depth = 루트 노드의 depth를 0 으로 정의할 때, 자식 노드의 depth는 부모 노드의 depth + 1 이다. Level = Depth 와 같다. de..

이진 탐색 트리 (Binary Search Tree, BST) 는 노드가 정렬되어 있어 탐색을 수행할 수 있는 이진 트리를 말한다. 각 노드는 여러개의 필드로 이루어진 데이터를 가지고 있다고 가정한다. 데이터 중에서 탐색을 하기 위해 사용되는 데이터를 '키' 라고 한다. node v 의 키를 key(v) 라고 정의하면, BST 는 모든 노드 u 에 대해서 아래를 만족하는 이진트리이다. (1) 만약 v 가 u 의 왼쪽 서브트리에 있다면 key(v) key(u) 이다. 등호는 좌, 우 둘 중 하나 어디든 들어가도 되지만, 왼쪽에 들어간 것으로 생각하자. 이 정의를 통해 이진 탐색 트리는 매우 효율적으로 원하는 key 를 탐색할 수 있다. 이제 이렇게 생긴 BST가 있다고 가정해보자. 이 트리에서 3이라는 값..