그래프 구현 및 핵심 알고리즘 탐구: 인접 행렬과 인접 리스트
그래프 자료구조의 기본 개념과 주요 알고리즘
그래프는 노드(정점)와 이 노드를 연결하는 간선(에지 또는 아크)으로 구성된 자료구조입니다. 컴퓨터 과학에서 다양한 시스템, 네트워크, 관계 등을 모델링하는 데 활용됩니다. 이 글에서는 그래프의 기본적인 개념부터 주요 표현 방식, 그리고 BFS, DFS, 최단 경로, 위상 정렬 등 핵심 알고리즘들을 C 언어 기반으로 살펴보 ...
7월 15일 22:01에 게시됨
구조체를 이용한 동적 단일 연결 리스트 구현
단일 연결 리스트 개념
단일 연결 리스트(Singly Linked List)는 노드(Node)라 불리는 요소들이 포인터로 연결된 선형 자료구조입니다. 각 노드는 두 가지 핵심 요소로 구성됩니다:
데이터 영역: 실제 값을 저장하는 공간
포인터 영역: 다음 노드의 주소를 저장하는 공간
리스트의 시작을 헤드 노드(Head)라 하며, 마지막 노드의 포인터는 NULL 값을 가집니다. 리스 ...
7월 12일 22:25에 게시됨
Codeforces Round 987 (Div. 2) 문제 해설
A번 문제: 최소 변경 횟수
이 문제는 비내림차순 수열로 만들기 위해 필요한 최소 변경 횟수를 구하는 문제입니다. 주어진 수열이 비내림차순이 아니므로, 가장 많은 원소를 그대로 유지할 수 있는 경우를 찾아야 합니다.
비내림차순 수열에서 가장 많이 유지할 수 있는 원소들은 동일한 값의 연속된 부분입니다. 따라서 가장 긴 동일한 값의 연속 부분의 길이를 찾으면 ...
7월 10일 22:00에 게시됨
스택과 큐 자료구조 구현
스택과 큐는 컴퓨터 과학에서 가장 기본적인 자료구조 중 하나로, 각각 후입선출(LIFO)과 선입선출(FIFO) 특성을 가집니다. 이번 글에서는 배열 기반과 연결 리스트 기반의 두 가지 구현 방법을 모두 다룹니다.
스택(Stack) 자료구조
스택은 후입선출(LIFO) 원칙을 따르는 자료구조로, 가장 마지막에 추가된 요소가 가장 먼저 제거됩니다.
배열 기반 스택 구현
/* 스택 헤 ...
7월 7일 20:13에 게시됨
트리(Tree) 자료구조의 기본 개념과 활용
자료구조는 프로그램의 효율성과 직결되는 중요한 요소입니다. 다양한 자료구조 중에서도 트리(Tree)는 계층적 데이터를 효과적으로 표현하는 비선형 자료구조의 대표적인 예시입니다. 특히 웹 프론트엔드 개발에서 자주 접하는 DOM(Document Object Model)이 트리의 한 형태로 구현되어 있어, 트리에 대한 이해는 웹 개발자에게 필수적입니다. 이 글에서는 트리 ...
7월 5일 02:58에 게시됨
연결 리스트 노드 조작: 쌍 교체, 순위 기반 삭제, 교차점 탐지, 순환 감지
노드 쌍 교체
인접 노드 교체를 위해 가상 헤드 노드를 생성합니다. 현재 포인터를 가상 헤드에 위치시킨 후, 다음 두 노드가 존재할 때까지 반복합니다. 세 개의 임시 포인터를 활용해 노드 연결 관계를 재구성합니다.
class ListNode:
def __init__(self, value=0, next_node=None):
self.val = value
self.next = next_node
def swap_node_pairs(h ...
7월 2일 04:37에 게시됨
Codeforces 라운드 #478 (Div. 2) 문제 해설
A. 아람 문자 문제
문제 설명: 아람어에서 단어는 객체만을 나타낼 수 있습니다. 아람어 단어에는 특성이 있습니다:
단어에 같은 문자가 한 번 이상 나타나지 않으면 루트입니다.
루트와 모든 순열은 동일한 객체를 나타냅니다.
단어 y의 루트 x는 y에 나타나는 모든 문자를 각 문자가 한 번만 포함하는 단어입니다. 예를 들어, "aaaa", "aa", " ...
7월 2일 03:08에 게시됨
순환 연결리스트를 이용한 원숭이 왕 선정 알고리즘
문제: head가 헤더 노드가 없는 순환 연결리스트를 가리키고 있을 때, 각 노드에는 데이터 필드(num)와 포인터 필드(link)가 포함됩니다. 데이터 필드에는 정수가 저장되며, i번째 노드의 데이터 필드 값은 i입니다. 함수를 작성하여 순환 연결리스트를 사용하여 원숭이 왕을 선택하는 과정을 시뮬레이션하세요: 첫 번째 노드부터 시작하여 "카운트"를 반복하고, ...
6월 29일 01:47에 게시됨
알고리즘 노트 및 문제 해결 전략
P2569 https://www.luogu.com.cn/problem/P2569
이 문제를 참고하세요.
/*단조큐로 dp 최적화
주식을 매수하는 전이 방정식에서 j는 순차적으로 열거됩니다. 주식을 매수하는 것이므로 보유한 주식은 점점 증가할 것이며,
현재의 결정이 나중에(j가 더 클 때) 사용될 수 있으므로 먼저 구해야 합니다.
마찬가지로 주식을 매도할 때 보유한 주식은 점점 줄어들고,
즉 현재 ...
6월 27일 03:51에 게시됨
C 언어 양방향 연결 리스트(Doubly Linked List) 구현 및 구조 분석
1. 기초 데이터 타입 및 상태 코드 정의
연산의 성공, 실패, 메모리 할당 오류 등의 상태를 명확하게 처리하기 위해 열거형(enum)을 활용한 상태 코드를 정의합니다. 또한, 노드에 저장될 데이터의 타입을 별도로 지정하여 추후 확장성을 높입니다.
#ifndef COMMON_DEFS_H
#define COMMON_DEFS_H
#include <stdio.h>
#include <stdlib.h>
typedef enum {
...
6월 25일 19:04에 게시됨