자료구조와 탐색 시간 지금까지 자료구조를 정리하면서 주요하게 다뤘던 내용 중 하나는 바로 "탐색" 이었다. 그리고 원하는 자료를 탐색하기 위해 수행한 가장 근본적인 동작은 바로 키를 비교하는 것이었다. 어떤 키가 다른 키와 같은지 다른지, 혹은 큰 지 작은 지를 비교하여 원하는 값을 탐색해내갔다. 여기 3글자 알파벳 소문자로 이루어진 이름과 4개의 숫자 쌍을 저장하는 간단한 주소록 프로그램이 있다. 그리고 이 주소록 프로그램에서 주소록 정보를 BST를 이용해 저장한다고 해보자. 만약 1000개의 주소록 데이터를 BST에 저장한다면, 최적의 경우 BST의 높이는 log(1000) 이므로 대략 10이라고 할 수 있고, 최악의 경우의 높이는 대략 1000이 될 것이다. 또 평균적으로는 1000개의 데이터를 B..
지난 글에서는 함수를 호출하는 call 명령어와, 이와 비슷하게 코드의 실행을 조정하는 jmpl 명령어, 그리고 이전 주소로 복귀하는 ret 명령어와 retl 명령어에 대해 정리하였다. 이번 글에서는 call 명령어를 호출한 이후, 함수의 시작을 알리는 역할로 불리는 save 명령어에 대해 정리하고자 한다. 'Save' Instruction save 명령어는 서브루틴을 위한 공간을 할당하는 명령어로서, 함수의 시작을 나타낸다. save 명령어는 2가지 기능을 한다. 첫번째 기능은 스택 메모리에 사용자가 지정한 사이즈 (스택 프레임의 사이즈) 만큼 공간을 할당한다. 공간을 할당하는 것은 %fp, %sp 의 이동과 같다. %fp 은 스택 프레임의 시작점, %sp 는 스택 프레임의 끝 점을 의미한다. 스택 공..
지난 글에서는 우선순위 큐와 이를 효율적으로 구현하기 위한 자료구조인 Heap 에 대해 정리하여 보았다. 이번 글에서는 한번 파이썬의 Heapq 를 뜯어보고자 한다. 뜯어보는 방법은 간단하다. 파이썬의 heap 모듈인 heapq 를 선언하고, ctrl 키를 누르고 클릭하면, 해당 모듈의 코드를 읽어볼 수 있다. Heap 개념 설명 코드 상단부에는 이렇게 heapq 모듈에 대한 설명과 사용 방법이 소개되어 있다. 위에 정의를 보면 우선순위큐를 heap queue 알고리즘이라고도 표현하는 것을 볼 수 있다. 파이썬의 공식 모듈에서 정의한 Heap은 모든 k 에 대해 a[k]
우선순위 큐 우선순위 큐는 우선순위를 가지는 아이템들을 가지는 큐이다. 일반적인 큐와 마찬가지로 push(), pop() 두가지 기능을 제공하지만, 우선순위 큐는 데이터를 저장할 때 단순히 데이터의 값 뿐만 아니라 데이터의 우선순위를 같이 저장하는 점이 다르다. 그래서 우선순위 큐에는 push(x, p) 와 같은 형태로 데이터를 저장한다. x 는 저장하는 데이터, p 는 저장하는 데이터의 우선순위이다. 그리고 pop을 할 때는 우선순위가 높은 데이터부터 나온다. 우선순위 큐의 구현 우선순위 큐의 개념은 간단하다. 그런데 우선순위 큐의 구현은 간단하지 않다. 만약 일반적인 큐를 구현할 때처럼 연결 리스트를 사용한다면 어떨까? 데이터를 pop 할 때, 우선순위가 높은 순부터 뽑아야 하므로 아래 2가지 방법중..
지난 글에서는 구조체가 메모리에 어떻게 저장되는지를 정리하였다. 구조체도 배열과 마찬가지로, 먼저 선언된 변수가 낮은 주소의 값 (%fp에서 먼 쪽)을 가진다. 그래서 먼저 선언된 변수의 위치를 기준으로 직접 경계 정렬을 하여 전체 구조체가 가지는 사이즈를 계산한 뒤, 구조체의 시작 위치를 구조체 내 변수중 가장 큰 사이즈의 배수로 맞추어 선언하면 되었다. 이번 글부터는 서브루틴에 대해 좀 더 자세하게 정리하고자 한다. 서브루틴 서브루틴은 '특정 작업을 여러번 수행하는 연속된 명령어의 나열' 으로 볼 수 있다. 서브루틴의 실행 과정을 한번 정리해보자. 1. 인자값 설정 o-register 에 값을 할당하여 매개변수로 넘길 값을 설정한다. (인자값은 o0 ~ o5 까지 6개 레지스터 범위에서 사용가능하며,..
벌써 11월 한달이 지나갔다. 1달동안 무슨 일이 있었는지, 느꼈던 점은 무엇인지 기록으로 남겨보고자 한다. 우아한테크코스 프리코스 3, 4주차 ( 11/1 ~ 11/15 ) 1달간 진행되는 우테코 프로코스의 중간 절반이 11월 중순까지 진행되었다. 마지막 과제는 크리스마스 연말 이벤트를 구현하는 문제였는데, 개인적으로 제일 재미있게 한 과제였다. 우테코에 시간을 많이 할애하지 못한 것이 아쉬웠고, 그래서 우테코에 붙을 것 같다는 기대는 버린지 오래지만 프리코스 기간동안 받았던 과제, 그리고 공통 피드백과 요구사항들만으로도 꽤 많은 것을 배우고 알아갈 수 있는 시간이었다. 또 프리코스 디스코드방에서 서로 의견을 나누고 공유하는 내용을 보면서 내가 아직도 배워야 할 점이 많다는 걸 느낄 수 있었다. 그래서..
지난 글에서는 다차원 배열에 대한 내용을 정리하였다. row-major, column-major 에 따라 주소값을 구하는 방식이 달라지는 것에 유의하여야 함을 기억하자. 또, 배열 원소 하나의 사이즈에 따라 주소값 계산식에 W 를 다르게 넣어야 함도 유의하여야 했다. 이번 글에서는 스택 메모리 공간에 구조체를 저장할 때 어떻게 저장되는지 정리하고자 한다. 구조체가 메모리에 들어갈 때 다음과 같은 구조체가 있다고 해보자. struct s { int a, b; char c; short d, e; int f, g; } 이때 이 구조체 변수 하나를 스택에 선언하면, 실제 메모리에는 어떻게 저장될까? 구조체도 배열과 마찬가지로 선언된 순서대로 점점 주소가 높아진다. (즉, 마지막에 선언된 변수가 %fp에 가깝다)..
지난 글에서는 일차원 배열에 대한 내용을 정리하였다. 일차원배열을 스택에 선언하는 경우, 배열의 주소는 낮은곳부터 높은 곳순으로 증가하지만, 배열 공간이 선언되는 위치는 지역변수가 선언되는 것과 마찬가지로 높은 주소부터 쌓이는 식으로 선언되었다. 이번 글에서는 다차원 배열에 대해 정리하고자 한다. 다차원 배열의 표현 다차원배열은 결국 선형구조인 메모리에 저장되어야 한다. 이때 선형 구조인 메모리에 어떻게 저장하느냐에 따라 크게 2가지로 나눌 수 있다. 1. row major 2. column major row major 는 우리가 흔히 사용하는 방식으로, 먼저 row 를 기준으로 구역을 나눈 뒤, column 인덱스가 증가할 때 메모리 주소가 순차적으로 증가하고, 모든 column이 다 차면 그때 row..
어셈블리 과제 + 정리하다가 만난 오류이다. 처음 만났을 때는 구글링 실력이 모자라서 그런가, 아무리 검색해도 해결방법이 나오지 않았다. 그러다가 오늘 코드를 한줄 한줄 주석했다가 풀어보면서 이 오류를 발생시키는 코드를 찾았고, 이 오류가 발생하는 원인을 발견했다. data 섹션에 데이터를 선언하고, 이렇게 라벨링을 하였을 때 이렇게 라벨링 된 값을 그대로 가져다가 사용하면 위 에러가 발생한다. 이렇게 반드시 set 명령어를 사용해서 레지스터에 주소값을 옮겨준 후, 연산을 해야 한다.
운좋게 ICPC 본선에 진출하게 되었다. 처음 ICPC를 갔다오면서 경험했던 것들을 글로 정리하고자 한다. ICPC 예선 사실 그 동안 ICPC라는 대회의 존재는 알고 있었는데, 이제야 나가게 되었다. 원래 같이 나가려고 했던 팀원 분 중에 한 분이 왜인지 나이제한에 막히시는 바람에 다른 팀원을 구해서 같이 나가게 되었다. 예선은 학교 멀티미디어실에서 진행했다. 개인노트북을 지참하고, 멀티미디어실에 있는 모니터에 연결해서 문제를 풀었다. 이때 팀노트는 따로 사용하지 않았고, 노트북 한대에 키보드와 모니터를 연결하고, 노트북 화면은 꺼둔채로 교수님 감독하에 대회를 진행햇다. ICPC 예선은 문제지 중 일부가 한국어로 나와서, 한국어 문제를 보고 빠르게 풀려고 노력했다. 팀원 중에서 내가 제일 구현을 익숙하..
