[알고리즘] 위상정렬

위상 정렬방향 그래프의 정점들을 "선후 관계(의존 관계)"에 따라 나열하는 정렬 방법이다.단, 위상 정렬은 비순환 방향 그래프(DAG : Directed Acyclic Graph)에서만 가능하다 만약 순환이 있다면, 어떤 노드도 “처리 순서를 앞에 둘 수 없기 때문에” 선형 정렬 자체가 불가하다.(진입 차수가 0이 될수 없는 구간이 존재하고, 그러면 각 정점은 우선순위가 없으며 위상 정렬을 통해 탐색 순서를 정의할 수 없다) 위상 정렬 예시 : 라면 끓이기DFS 기반 위상 정렬깊이 먼저 따라가서, 끝에서 역순으로 쌓는다사리 부수기 → 사리 넣기 → 물넣기스프넣기 → 물넣기끓이기 → 물넣기밥 준비하기 (독립)✔️ 결과 예시 (역후위 순회) :밥 준비하기 → 사리 넣기 → 사리 부수기 → 스프 넣기 → 끓이..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 4. 3.

[알고리즘] 트리 구조

트리 구조루트 : 트리의 가장 위쪽에 있는 노드. 루트는 트리에 1개만 존재리프 : 가장 아래쪽에 있는 노드. aka 단말 노드 (terminal node), 외부 노드 (external node). 가지를 더 이상 뻗을 수 없다비단말 노드 (non-terminal node) : 리프를 제외한 노드. aka 내부 노드자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라 한다.부모 : 어떤 노드와 가지가 연결되었을 때 위쪽 노드를 부모라 한다형제 : 부모가 같은 노드를 형제라 한다조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드를 조상이라 한다자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드를 자손이라 한다레벨 : 루트에서 얼마나 멀리 떨어져 있는지. 루트의 ..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 4. 3.

[크래프톤정글] 정글에서의 생활

정글에 입소하기 전에 가장 걱정했던 부분 중 하나는 기숙사의 환경과 밥을 어떻게 해야하는지였다. 추후 정글을 지원하려는 분들을 위한 기록용으로 간단하게만 소개한다.기숙사 입소입소 당일에 짐이 너무 많아서 택시를 타고 왔다. 다행히 집이랑 그리 멀지 않기도 하고, 늦게 출발하니 막히는 시간에서 벗어나서 거의 하이패스로 도착할 수 있었고 택시비도 예상보다 훨씬 덜나왔다. (네이버 지도보다 약 1만원 정도 덜나와서 기분 좋았다) 그리고 기사님이 짐 많은 중생을 많이 도와주셔서 덕분에 잘 도착할 수 있었다.기숙사는 안내되는 바와 같이 2인 1실이다. 지금은 짐이 다 차있어서 그나마 입소하자 마자 찍어둔 사진으로나마 공유한다.참조로 기숙사에는 책상이 없다. 공부는 무조건 강의실에 와서 하거나 캠퍼스 곳곳에 놓여있..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 3. 23.

[알고리즘] Backtracking

백트래킹현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.이를 활용해 의사결정을 하는 예로는, 미연시나 역전재판같은 롤 플레잉 게임에서, 하나의 선택지마다 다른 결과값을 불러올 수 있으며, 이를 뒤로가기 하면 다른 방식으로 탐색할 수 있다.백트래킹을 활용한 알고리즘 함수에 포함할 내용은 다음과 같다. 아래는 전역 변수로 설정할 변수이다.n, m 입력값array : 수열을 담을 빈 배열visited / issued : 쓰였는지 확인하는 true/false 배열. 이 배열은 위 수열의 개수만큼 필요하고, 초기값은 0 (false)로 설정한다.함수의 형태는 1) 종료조건과 만족 시 값 리턴 2) 아니면 원하는 조건의 함수 호출한다.예제로 백준의 N과 M 문제를 풀어보았다.15649 : N..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 3. 19.

[알고리즘] 퀵 정렬 (Quick Sort)

Quick Sort피벗을 실행하여 배열에서 두 그룹으로 나눈다피벗 보다 작은 원소는 오른쪽에서 왼쪽으로, 피벗 보다 큰 원소는 왼쪽에서 오른쪽으로 이동한다.왼쪽 포인터와 오른쪽 포인터가 교체하는 지점에서, 왼쪽과 오른쪽 포인터 값을 교환한다그룹 내에서 새로운 피벗을 생성하고, 그 피벗을 기준으로 정렬이 마무리 될때까지 위 과정을 반복한다퀵 정렬은 큰 문제를 작은 문제로 나누어 푸는 과정의 반복으로, 시간복잡도는 O(n log n)이다. 다만 매번 1개의 원소와 나머지 원소로 나뉘면 최악의 경우의 시간복잡도는 O(n^2) 이다. 원소 수가 적은 경우에는 다른 방식으로 정렬하는 것이 더 유리하다.재귀적인 구현에서는 처음에 전체 배열을 재귀 함수의 매개변수로 전달하며, 각 단계에서 피벗을 기준으로 왼쪽 오른쪽..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 3. 18.

[크래프톤정글] Week 1 : 컴파일 시스템

컴퓨터 시스템의 기초에 대해 알아보자. 사용자가 명령어를 입력하면 그 화면이 출력되기 까지의 절차까지를 알아보겠다.  정보의 단위소스 프로그램은 0과 1로 이루어진 비트의 연속이다. 바이트는 8 비트 단위로 구성된다. 모든 텍스트 파일은 ascii 문자로 이루어진 파일을 의미하며, 그 외 모든 파일은 바이너리 파일이다. 컴파일 시스템컴파일이란?우리가 보는 프로그램은 사람이 이해하고 쓸수 있는 형태로 되어 있지만, 컴퓨터에게 일을 시키기 위해서는 저급 기계어로 바꿔줘야 한다. 이 과정을 컴파일이라 한다.  컴파일은 다음과 같은 단계를 거친다. 전처리 단계 : hello.c -> hello.i 라는 새로운 C 프로그램이 생성되며, 본래의 프로그램을 #문자로 시작하는 디렉티브에 따라 수정한다컴파일 단계 : h..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 3. 18.