자료구조와 알고리즘은 컴퓨터 과학에서 기초로 다룰 만큼 근간이 되는 학문입니다. 이번 포스팅에서는 자료구조와 알고리즘에 대해 알아보고 둘의 관계를 다루어 보겠습니다. 이번 글에서는 전반적으로 흐름에서 자료구조와 알고리즘의 관계에 대해 다룰 예정입니다. 구현 방법, 예시 등은 다른 글에서 다루었으니 필요하시면 찾아보세요! 1. 자료구조 자료구조란? 효율적으로 데이터를 접근/수정하기 위해 데이터를 조직화하는 방법입니다. 그렇다면 자료구조는 왜 중요할까요? 어떤 자료구조를 사용하느냐에 따라 데이터의 처리 속도나 메모리 사용량이 크게 달라집니다. 따라서 자료구조는 프로그램의 실행 속도를 결정짓는 매우 중요한 개념입니다. 자료 구조의 특징 상황에 맞는 자료구조를 선택하려면 다음 세 가지 특징을 만족해야 합니다. ..

이진 트리의 자식 표현 방법 이진 트리는 트리와 달리 자식의 Left, Right에 대한 정보가 반드시 필요하다. 따라서 일반적인 그래프로 구현하기 힘들다. 배열, 구조체, 연결리스트 등으로 표현가능하지만 트리의 구조를 이용하여 배열로 간단하게 나타낼 수 있다. 이진 트리의 4가지 순회 방법 1. 레벨 순회(Lever Travel) Level Travel은 트리이 깊이를 순차적으로 탐색한다. 방문 순서는 cur → Left Child → Right Child이다. 레벨 순회는 BFS와 유사한 구조를 가진다. 구현은 일반적인 BFS처럼 해주면 된다. 이를 코드로 구현하면 다음과 같다. void levelTravel(){ queue q; q.push(1); while(!q.empty()){ int cur =..

이번 포스팅에서는 유니온 파인드 알고리즘에 대해서 알아보겠습니다. 유니온 파인드를 알기 위해 간단한 트리의 개념을 알아야 합니다. 트리가 처음이라면 먼저 간단하게라도 트리의 개념과 트리 순회를 알아보고 오는 것을 추천드립니다.유니온 파인드 알고리즘은 기본 구현보다 최적화 방법과 문제 적용이 더 중요합니다. 최적화 원리까지 이해하고 문제 적용하는 것을 강력 권장합니다. 1. 유니온 파인드란?다음과 같이 여러 노드간의 연결 관계가 주어졌다고 해봅시다.임의의 두 노드가 주어졌을 때 유니온 파인드 알고리즘을 이용하면 두 노드가 같은 집합에 속하는지 확인할 수 있습니다. 예를 들어 1과 2는 같은 집합, 3과 5도 같은 집합, 4와 6은 다른집합입니다. 유니온 파인드를 이용하면 이러한 연산을 O(1)에 바로 알 ..

문자열 처리 알고리즘

1. 가중치가 1인 무방향 그래프인 경우: BFS로 풀면 최초 방문 위치가 최단 경로가 보장된다.2. 가중치가 있는 방향이 있는 그래프인 경우: 데이크 스트라 알고리즘3. 플로리드 알고리즘(음수 간선도 가능)4. 벨만 포드 알고리즘

일반적으로 힙을 이용해 구현 배열이나 연결리스트로도 구현할 수 있다ㅣ. https://jungeu1509.github.io/algorithm/use-priorityqueue/ C++ STL priority_queue 우선순위 큐 사용법 C++ stl을 사용한 우선순위 큐 내용정리. How to use priority_queue in C++ stl jungeu1509.github.io * 구현체는 기본적으로 vector으로 정의된다. 이말인 즉슨 우리가 쓰는 priority_queue가 실제로는 vector 위에서 돌아가고 있다는 것이다. vector가 아니더라도 deque 등을 넣어도 잘 돌아간다. stl에서 힙을 구현하기에 충분한 자료구조면 다 된다. (random access iterator가 지원되..