![]()
#1. 문제https://www.acmicpc.net/problem/3176 #2. 풀이 1. LCA [알고리즘]#7_LCA(Least Common Ancestor)#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가webddevys.tistory.comLCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. LCA 알고리즘은 Binary Lifting 기법을 활용해 최적화를 수행하며, 일반적으로 두 노드의 공통 조상을 찾거나, 두 노드 사이의 거리 혹은 최단/최대 거리를 찾는데 활용됩니다. 2...
![]()
#1. 문제https://www.acmicpc.net/problem/1761 #2. 풀이 1. LCA 알고리즘 [알고리즘]#7_LCA(Least Common Ancestor)#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가webddevys.tistory.comLCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘은 Binary Lifting 기법을 통해 최적화..
![]()
#1. 문제https://www.acmicpc.net/problem/1240 #2. 풀이 1. BFS [자료구조]#6_그래프#0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와webddevys.tistory.comBFS는 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. BFS는 현재 레벨의 가장 인접한 정점들을 우선적으로 탐색합니다. 일반적으로, BFS는 큐 자료구조를 활용합니다. 2. BFS = 탐색 or 최단 경로(가중치가 모두 동일한 환경에서만!)먼저, 트리 자료구조는 그래프의 한 종류입니다. 따라서, DFS 혹은 BFS를 트리 자료구조에서도 역시 활용 가..
![]()
#1. 문제https://www.acmicpc.net/problem/10282 #2. 풀이 1. 다익스트라 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입..webddevys.tistory.com다익스트라 알고리즘은 양의 가중치를 갖는 그래프에서 '단일 출발 최단 경로'를 구하는 길 찾기 알고리즘입니다. 일반적으로, 다익스트라 알고리즘은 하나의 출발 정점에 대하여 다른 모든 정점을 도착 정점으로 하는 최단 경로를 찾는 알고리즘으로, 우선순위 큐와 최단 경로 목록을 활용합니다. 주의할 점은 간선의 방향성 여부에 따라서 중복 업데이트 방지를 위해 각 정점의 방문 여부를 기록할 것인지 고..
![]()
#1. 문제 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net #2. 풀이 1. 최소 신장 트리 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 최소 신장 트리는 가중치 그래프에서 간선들이 갖는 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 대표적인 최소 신장 트리 알고리즘은 Kruskal 알고리즘(간선..
![]()
#1. 문제 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net #2. 풀이 1. 위상 정렬 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 위상 정렬은 DAG(비순환 유향 그래프)에서 각 정점들의 선행 관계를 유지하며 정점을 나열하는 방법입니다. 위상 정렬 알고리즘은 일반적으로 스..
![]()
#1. 문제 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net #2. 풀이 1. 크루스칼 알고리즘 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 크루스칼 알고리즘은 간선 중심의 최소 신장 알고리즘입니다. 크루스칼 알고리즘은 그래프의 간선들을 가중치 기준 오름차순 정렬하여, ..
![]()
#1. 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #2. 풀이 1. 스택 [자료 구조]#0_선형 자료구조 [자료 구조] #0_선형 자료구조 선형 자료구조에 대해 알아보겠습니다. Overview 개념 스택 큐 원형 큐 덱 배열 벡터 리스트 이중 연결 리스트 #0. 개념 1. 선형 자료구조? [정의] : 선형 자료구조는 데 webddevys.tistory.com 스택은 '후입 선출' 방식으로 동작하는 선형 자료구조입니다. 스택은 동일한 유형의 데이터 항목을 데이터 목록의 한쪽 끝에서만 삽입/삭제하는 특징이 있습니다. 2. 히스토그램 유형 문제 [BO..
![]()
#1. 문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net #2. 풀이 1. 그래프 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 그래프 자료구조는 노드와 간선의 집합으로 이루어진 비 선형 자료구조입니다. 그래프 자료구조의 노드 간 연결 관계를 간선으로 표현하며, 간선의 방향성, 연..
![]()
#1. 문제 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net #2. 풀이 1. 그래프 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 그래프 자료구조는 노드와 간선의 집합으로 이루어진 비 선형 자료구조입니다. 그래프 자료구조의 노드 간 연결 관계는 간선으로 나타내며, 간선의 방향성, 연결 강도를 통..
