하루이의 개발 노트

예시: hello.c 파일#include int main() { printf("Hello, World!\n"); return 0;}이 프로그램을 컴파일한 후, 어셈블리 코드로 변환하면 (gcc -S hello.c -o hello.s), hello.s 파일에는 다음과 같은 어셈블리 명령어가 생성된다.hello.s 파일 예시 (x86-64 아키텍처 기반): .section .rodata.LC0: .string "Hello, World!" .text .globl main .type main, @functionmain: pushq %rbp movq %rsp, %rbp leaq .LC0(%rip), %rdi call ..

hello.c를 실행할 때 호출되는 시스템 호출(system call)과 어셈블리 파일의 내부 구조에 대해 자세히 알아보자.전처리 및 컴파일1. 소스 코드 작성 및 컴파일C 소스 코드 작성: hello.c 파일에 "Hello, World!"를 출력하는 코드가 작성된다.컴파일: 소스 코드는 컴파일러에 의해 어셈블리 코드로 변환된다. 이 과정에서 다음과 같은 어셈블리 코드가 생성된다:leaq .LC0(%rip), %rdi ; 문자열 "Hello, World!"의 주소를 레지스터 %rdi에 저장call printf ; printf 함수 호출이 어셈블리 코드는 고수준의 printf 호출이 저수준의 명령어로 변환된 결과다.2. 라이브러리 함수 호출라이브러리 함수 준비: 컴파..

레지스터는 CPU 내부에서 매우 빠른 속도로 데이터를 저장하고 처리하는 작은 크기의 메모리 공간이다.  x86-64 아키텍처에서는 다양한 범용 및 특수 목적 레지스터가 존재하는데 ,  각각의 레지스터는 특정 용도나 연산에 최적화되어 있다.1. 범용 레지스터 (General Purpose Registers)범용 레지스터는 다양한 목적에 사용될 수 있으며, 기본적인 데이터 처리나 주소 계산 등에 활용된다. x86-64 아키텍처에서는 레지스터가 64비트 크기로 확장되었다.64비트32비트16비트8비트 상위8비트 하위설명RAXEAXAXAHAL주로 연산 결과를 저장하는 레지스터RBXEBXBXBHBL범용 레지스터로 임의의 데이터를 저장RCXECXCXCHCL루프 카운터로 자주 사용됨RDXEDXDXDHDL입출력 작업이나..

동적 계획법(DP)는 하나의 알고리즘이라기보다는 문제를 해결하기 위한 방법론에 가깝다. 이는 문제를 작은 하위 문제들로 나누고, 그 결과를 재사용하여 최적화하는 방식이다. 동적 계획법은 문제마다 각기 다른 점화식을 세우고, 그에 맞는 알고리즘을 스스로 만들어가야 하기 때문에, 처음에는 이 방법을 쉽게 떠올리기 어려울 수 있다.그래서, 동적 계획법의 흐름을 따라가며 개념을 이해하는 방법을 예시를 통해 정리해보고자 한다. https://developsvai5096.tistory.com/76 위의 포스트 또한 dp를 통해 점화식을 구하는 내용이 자세히 정리 되어있다. 같이 보면 도움이 되지 싶다.1. Reduction & Recursion (문제를 작은 문제로 나누기)동적 계획법은 큰 문제를 작은 문제로 나누..

배낭 문제 는 동적 계획법(DP) 문제의 대표적인 예로, 주어진 아이템을 배낭에 담아 최대 가치를 구하는 문제다. 이걸 이하는데 시간이 매우 오래 걸렸지만 아직도 dp의 접근 방식과 , 점화식을 세우는건 좀 부족하다. 그래도 이해 한 만큼 에 대해서는 정리를 해보고자 한다. 1. 문제 정의주어진 무게 제한 k가 있는 배낭에 n개의 아이템을 넣으려고 한다.각 아이템 i는 무게 v[i]와 가치 w[i]를 가지고 있다.목표는, 무게 제한을 넘지 않으면서 배낭에 담을 수 있는 아이템들의 가치 합을 최대화하는 것이다.2. 문제의 특징각 아이템은 한 번만 선택할 수 있다. 즉, 선택하거나 선택하지 않는 두 가지 선택지뿐이다. (0/1 문제)선택을 할 때, 배낭의 용량을 넘지 않도록 해야 한다.목표는 최대 가치를 얻..

트리 예시우선, 다음과 같은 간단한 이진 트리를 가정하자: 1 / \ 2 3 / \ 4 5위의 트리에서 노드 1이 루트 노드이고, 2와 3이 각각 루트의 왼쪽과 오른쪽 자식 노드이며, 4와 5는 2의 자식 노드다.1. 전위 순회 (Preorder Traversal)전위 순회에서는 루트 -> 왼쪽 -> 오른쪽 순으로 노드를 방문한다.1. 루트(1)를 먼저 방문2. 왼쪽 서브트리로 이동하여 2를 방문3. 다시 왼쪽 서브트리로 이동하여 4를 방문4. 4의 부모 노드인 2로 돌아가 오른쪽 자식인 5를 방문5. 루트 노드의 오른쪽 서브트리로 이동하여 3을 방문방문 순서: 1 → 2 → 4 → 5 → 32. 중위 순회 (Inorder Traversal)중위 순회에서는 왼쪽 -> 루..

Union-Find 자료 구조는 Disjoint Set(서로소 집합)이라고도 불리며, 집합 간의 합집합(Union)과 특정 원소가 속한 집합을 찾는(Find) 연산을 효과적으로 수행하기 위한 자료 구조다. 이 자료 구조는 주로 그래프 알고리즘에서 사이클을 판별하거나, 서로 연결된 컴포넌트를 찾는 데 사용된다.기본 개념집합(sets): 각 원소는 하나의 집합에 속하며, 처음에는 모든 원소가 자신만을 포함하는 집합에 속하게 된다.합집합(Union): 두 집합을 하나의 집합으로 합친다.찾기(Find): 특정 원소가 속한 집합의 대표 원소(루트)를 찾는다.주요 연산Union-Find 자료 구조는 두 가지 기본 연산을 제공한다:Find(x):원소 x가 속한 집합의 루트(대표 원소)를 찾는다.경로 압축(Path C..

위상 정렬(Topological Sorting)의 개념위상 정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서 노드들을 선후 관계에 따라 순서대로 나열하는 것이다. 여기서 선후 관계란 그래프의 방향을 나타내는 간선(Edge)에 의해 결정되는 노드 간의 의존성을 의미한다. 위상 정렬의 목적은 이 의존성을 지키면서 모든 노드를 나열하는 것이다.위상 정렬의 기본 개념방향 그래프(Directed Graph):그래프의 각 간선이 방향을 가지며, 이는 한 노드에서 다른 노드로의 일방향성 연결을 의미한다.예를 들어, 작업 A가 끝나야 작업 B를 시작할 수 있다면, 이는 A에서 B로 향하는 방향 간선으로 표현된다.사이클이 없는 그래프(Acyclic Graph):그래프에 사이클(Cy..

다익스트라 알고리즘이란?다익스트라 알고리즘(Dijkstra's algorithm)은 그래프에서 단일 출발점에서 모든 다른 노드로의 최단 경로를 찾는 알고리즘이다. 가중치가 있는 그래프에서 가중치가 양수일 때 사용할 수 있으며, 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 1956년에 고안한 알고리즘이다.다익스트라 알고리즘의 동작 원리초기화:시작 노드를 선택하고, 시작 노드에서 다른 모든 노드까지의 거리를 무한대(∞)로 초기화한다.시작 노드의 거리는 0으로 설정한다.아직 방문하지 않은 모든 노드를 포함하는 집합(보통 우선순위 큐를 사용)에 시작 노드를 추가한다.반복:큐에서 가장 작은 거리를 가진 노드를 꺼낸다. 이 노드를 현재 노드로 설정한다.현재 노드의 인접 노드들을..

다익스트라 알고리즘을 공부 하면서 풀어볼수 있는 문제를 찾다가 미로만들기 문제를 풀어보았는데 다익스트라가 어떤 알고리즘 인지 보여주는데 적합한 문제인것 같아 정리 해보았다.문제 개요"미로 만들기" 문제(백준 문제 번호: 2665)는 흑백 미로에서 최소한의 방을 바꾸어 시작점에서 도착점까지 도달하는 최단 경로를 찾는 문제이다.문제 설명미로는 NxN 크기의 정사각형으로, 각 칸은 흰 방(0) 또는 검은 방(1)으로 이루어져 있다.흰 방(0)은 그대로 지나갈 수 있지만, 검은 방(1)은 흰 방으로 바꾸어야만 지나갈 수 있다.목표는 시작점 (0, 0)에서 도착점 (N-1, N-1)까지 도달하는데 필요한 최소한의 검은 방 변환 횟수를 구하는 것이다.다익스트라 알고리즘을 사용한 접근그래프 모델링각 방을 그래프의 ..