Graph : 그래프

이전 글에서 트리를 다룬적이 있다. 그래프랑 트리는 노드와 간선을 필요한 컴포넌트를 갖고 논하는 자료구조이지만,그 사용 목적에서 중요한 차이 때문에 많은 사람들은 구분해놓고 사용하곤 한다.트리는 일종의 계층적인 영역에 가깝고, 그래프는 연결을 표현하는데에 보다 최적화되어있다.이 문장에 바로 감이 안온다면, 트리는 조직도, 그래프는 카카오톡 등록 상태를 사람 단위로 나눠 본다고 생각해보자.그래프의 특징에 대해 정리해보겠다.트리보다 일반적이다. 노드와 간선으로 데이터를 연결한다는 점은 공통점이다.간선은 방향이 있는경우, 없는경우로 나뉜다. 이것을 Directed, Undirected로 나눌 수 있다.사이클이 허용된다. 그렇기 때문에 트리보다 더 복잡한 상태를 나타낼 수 있다.사이클은 시작 노드에서 출발해, ..

• format_list_bulleted 별 잡다
• · 2025. 3. 28.

Linked List : 연결 리스트 & Array

연결 리스트는 배열과 연속한 형태 내용을 나열한다라는 공통점이 있지만 그 상세한 방식에는 다소 차이가 있다.빠르게 생각해보면연결 리스트는 원소가 본인의 contents 뿐만 아니라, 같이 이전 원소 또는 다음 원소에 대한 위치 정보를 가지고 있다.굳이 따지고 들어가면 연결 리스트의 원소는 기억해야 할게 다량 있기 때문에 메모리상 cost가 다소 있는 편이다.또 메모리 상에서 연속적이지 않다. 이건 컴퓨터의 cache memory랑 연결되는 건데, cache에 많이 의존하는 프로그램은 연결리스트 사용에 다소 조심스럽게 접근해야 할 것 같다.cache는 지역성 성질 때문에 물리적으로 위치가 유사한 곳에 있을 때 보다 빠른 성능으로써의 사용이 가능한 점을 참고하기하지만 처음 정의에서 특정한 크기를 정의하지 않..

• format_list_bulleted 별 잡다
• · 2025. 3. 28.

Hash

해시, 해쉬 어쩌구저쩌구 논하는 이것은 먹을 것에 논하는 것은 아니다.대신, 자료구조에서 각각의 데이터를 고유한 숫자 값으로 변환을 하고 이 변환된 값을 이용하여 특정 데이터의 존재 여부를 확인하거나 데이터를 추출하는 작업을 말한다.보통 이 과정에서 데이터는 고정된 길이로, 그 자체로는 특별한 의미가 없는 데이터로 변환된다.이러한 Hashing의 과정에서는, 데이터를 고정된 길이로 바꿔줄 해시 함수와 해시 테이블이 사용 된다.Hash Function해시 함수란, 주어진 데이터(Key)를 고유한 숫자 값인 Hash Value으로 표현해주는 함수이다.키(Key)란, 해시 함수의 입력 부분이며, 입력 데이터 자체이거나 입력 데이터를 구분하는 값을 의미한다.해쉬 값(Hash Value)란, 해시 함수의 출력 부..

• format_list_bulleted 별 잡다
• · 2025. 3. 28.

WIL 02

지난 주에 이리 시간이 남는게 맞냐고 논하는 질문 자체가 잘못되었다.나는 시간이 왜 남냐는 말을 하지 말고 다음에 뭘 미리 해야하냐를 물어봤어야했다. 이렇게 내가 모자르다.https://hyeonistic.tistory.com/48 하자있는 채로 풀었던 내용들" data-og-description="내가 직접 손 쓴 것이 거의 없는데 과연 블로그에 글을 쓰는게 맞을까라는 생각이 들었던 이번 주였다.그래서 시간이 남는다면 (부디 그렇다면 좋겠다) 다시 눈여겨 봐야 할 문제들에 대해 정리 " data-og-host="hyeonistic.tistory.com" data-og-source-url="https://hyeonistic.tistory.com/48" data-og-url="https://hyeonist..

• format_list_bulleted WIL
• · 2025. 3. 28.

[PY] <!> 하자있는 채로 풀었던 내용들

내가 직접 손 쓴 것이 거의 없는데 과연 블로그에 글을 쓰는게 맞을까라는 생각이 들었던 이번 주였다.그래서 시간이 남는다면 (부디 그렇다면 좋겠다) 다시 눈여겨 봐야 할 문제들에 대해 정리 해두려고 한다.우선순위 큐를 사용해서 해낼 수 있는 문제(들) :1655 : 가운데를 말해요https://www.acmicpc.net/problem/1655우선순위 큐는 최대 힙 또는 최소 힙을 사용해서 만들어지는데, 꼭 큐의 형태를 생각하지 않더라도 항상 첫번째 원소가 최대 또는 최소를 가리키는 배열 두 개를 갖고 중앙값을 찾아야 하는 문제라고 생각하면 보다 직관적으로 생각 할 수 있었다.하지만.. 이 아이디어에서 더 진도를 나가지 못했다. 뭔가 더 많이 떠올려야 하는데 이어가지질 않았다.뒤에 일정이 예정 되어 있는..

• format_list_bulleted 문제풀이
• · 2025. 3. 28.

트리 순회에 대해 논하기

트리의 정의1개 이상의 유한한 개수의 노드, 또는 vertex의 집합을 말한다.루트 노드와 0개 이상의 겹치지 않는 하위 나무 구조들의 집합으로 이루어져 있다.트리는 node와 edge라는 것으로 표현된다.원소가 들어있는 경우가 바로 node이며, 여기에 특정한 정보를 저장한다.그 node들 끼리 잇는 선을 edge라고 부르며 정보들간의 관계를 나타낸다.node, edge만큼은 아니지만 사용하는 용어가 좀 더 있다.path는 edge에 의해 연결 된 node들의 집합을 말한다.root node는 최상위의 노드를 말한다.parent, children, siblin, grand-는 기준이 되는 것의 직계 상위, 아래층, 같은 부모의 노드 등을 정의한다.leaf는 자식이 없는 node를 말한다.subtree는..

• format_list_bulleted TIL
• · 2025. 3. 27.