본문 바로가기

내 이야기

(70)
자료구조 트리 (tree) 트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가 추가된 자료구조이다. 나무를 뒤집어 놓은 것과 비슷하게 생겼다 하여 이름 붙여진 트리는, 알고리즘 문제를 풀 때 단골로 등장하는 자료구조이다. 다음은 이진트리를 이용해 정렬된 숫자들을 탐색하는 이진 탐색 트리의 예시이다. 위에서 언급했듯 트리는 그래프의 일종이므로 그래프의 특성을 공유한다. 거기에 추가되는 노드 간 부모 - 자식 관계가 더해지는 것이 트리의 특징이다. 트리는 그래프 이상의 다양한 종류로 분류된다. 종류를 분류할 기준을 크게 3가지로 나누어 적어보았다. 자식의 개수별 분류 트리 : 자식의 개수에 대한 제한이 없는 트리 이진트리 : 모든 노드에 대하여 자식의 개수가 2개 이하인 트리 N진 ..
자료구조 그래프 (graph) 그래프는 입력된 자료들을 특정한 규칙을 이용해 관계를 맺어 줄 수 있는 형태의 자료구조이다. 예를 들면 사람들의 지인 관계는 그래프로 나타내기 좋은 형태이다. 그래프는 다양한 방법으로 구현할 수 있기 때문에, 어느 한 가지 구현 방식만이 그래프라고 생각하지 않는 것이 좋다. 대표적으로 사용되는 그래프 구현 방식은 class, struct 등을 이용하여 정의한 노드와 포인터를 이용한 방식 (주로 c++) 배열을 이용한 방식 (인접 행렬, 세그먼트 트리 등등) 연결 리스트를 이용한 방식 (인접 리스트, map 자료구조를 이용한 방식 등등) 등이 있다. 그래프를 사용하는 방법 또한 다양한 방법이 있기 때문에, 어느 한 가지 사용법만이 그래프 자료구조를 이용했다고 생각하지 않는 것이 좋다. 대표적으로 그래프 구..
자료구조 큐 (queue) 큐는 선입 선출(First In First Out : FIFO) 형태의 자료구조이다. 큐는 들어온 순서를 이용하는 기능에서 적절하게 사용할 수 있다. 더보기 들어온 순서를 이용하기 위해 큐를 이용한 예시 : 2022.07.15 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 알고리즘 : 너비 우선 탐색(BFS) 알고리즘 : 너비 우선 탐색(BFS) 우선 그래프, 트리, 큐 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는것이 좋다. 더보기 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 그래프 (graph) 자료구 dev-game-standalone.tistory.com 선착순 대기열 기능이 좋은 예시이다. 어떠한 서비스를 이용하고자 하는 사용자 4명이 ..
자료구조 스택 (stack) 스택은 선입 후출(First In Last Out : FILO) 형태의 자료구조이다. 스택은 직전 단계로 돌아가는 기능이 필요한 경우 적절하게 사용할 수 있다. 인터넷 브라우저의 뒤로 가기 기능이 좋은 예시이다. 인터넷을 이용하는 과정에서 1번 페이지에서 2번 페이지로, 2번에서 3번, 3번에서 4번 페이지 순으로 이동했다고 가정해보자. 4번 페이지에서 뒤로 가기 버튼을 누르면 3번 페이지로 이동해야 한다. 마찬가지로 3번 페이지에서 한번 더 뒤로 가기 버튼을 누르면 2번 페이지로 이동해야 한다. 위의 예시처럼 이전 상황을 복원해야 하는 상황에서 스택은 좋은 선택이 될 수 있다. 스택은 대부분의 프로그래밍 언어에서 라이브러리로 지원되고 있다. C++ / Java의 경우 push(삽입), pop(삭제), ..
BOJ 7579번 앱 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net DP를 이용한 문제이다. 일반적으로 이러한 문제를 만나면, 확보되는 메모리를 인덱스로한다. 그렇게 해야 DP 테이블을 구한 뒤 문제에서 요구하는 인덱스의 값을 바로 출력 해 줄 수 있기 때문이다. 그런데 이 문제의 경우에는 확보할 메모리의 범위가 너무 넓다 (1 ~ 10,000,000) 비용의 범위가 (0 ~ 10,000) 인 것을 감안하면 결국 2byte 이상의 변수를 이용해야 하는데 그렇게되면 DP 테이블의 크기만 거의 20MB 가 되기 때문에 꺼려진다. (msvc..
BOJ 2239번 스도쿠 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net DFS를 이용해 해결 가능한 문제다. 자료를 담고 있는 컨테이너의 형태가 트리, 그래프 형태가 아니더라도 깊이 우선 탐색은 사용 할 수 있다고 생각한다. (컨테이너의 형태가 다를때, 다른 이름으로 부르는 정식 명칭이 있다면 알려주시면 감사합니다.) 아이디어는 간단하다. 좌측 상단부터 시작하여 0이 들어있는 인덱스를 찾고, 해당 인덱스에 들어갈 수 있는 숫자를 오름차순으로 넣어보며 탐색을 계속 하는 것 이다. 그렇게 모든 탐색이 끝난다면 해당 순간의 스도쿠 ..
22년 6월 24일 해야할일 1. 스터디 미비 보완 2. 스터디 미비 보완 포스팅 3. 포스팅 1) 프로세스의 메모리에 대하여 (스택, 힙, 데이터 등등) 2) 메모리 + 어셈블리 3) 어셈블리 + 함수의 호출방식 (stdcall, cdeclcall, fastcall 등등) 4) 변수와 구조체 (지역변수, 전역변수, 동적할당, 반환값, 매개변수 등등) 5) 구조체 + 캐시에 대하여 6) 캐시 + 페이지에 대하여 4. 성능 프로파일러 구현 5. 뱀게임 클라이언트 설계 6. 뱀게임 서버 설계
프로그램이(프로세스가) 실행 될 때, 메모리의 구조 (code, text 영역) 컴퓨터의 성능을 수치로 나타낸다면 어떤 것을 수치화 해야할까. CPU의 코어 개수, 코어당 클럭, 캐시 메모리의 크기, RAM의 크기, GPU의 클럭, GPU의 로컬 메모리 등등 여러 가지 기준이 있을 수 있지만 컴퓨터에 큰 관심이 없는 사람들 기준으로 생각해보면 SSD의 용량(하드 용량), RAM의 크기 두 가지가 상당히 자주 쓰일 것이라 생각한다. 여러 가지 항목들 중 우선 프로그램이 실행될 때, RAM에 프로그램이 어떤 식으로 적재되고 동작 과정에서 어떻게 변하는지부터 천천히 정리하고자 한다. 코드(.cpp) 를 실행 가능한 프로그램 (.exe) 로 컴파일을 한 상황을 생각해보자. 우선 코드를 전처리한 후, 컴파일하고, 링킹을 하여 최종적으로 프로그램을 받을 수 있을 것이다. 이때 전처리를 담당하는..