윤깡패 블로그

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드(Union-Find) 알고리즘 유니온 파인드(Union-Find) 알고리즘 유니온 파인드(Union-Find) 알고리즘 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 + 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 유니온 파인드 핵심 이론 union 연산 각 노드 soobin0821.tistory.co..

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 탐색 알고리즘 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘 DFS(깊이 우선 탐색) 알고리즘 * DFS : Depth-First Search 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 soobin08..

탐색 알고리즘 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘 DFS(깊이 우선 탐색) 알고리즘 * DFS : Depth-First Search 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 기능 - 그래프 완전 탐색 기법 특징 - 재귀 함수로 구현 - 스택 자료구조 이용 (스택 오버플로에 유의) 스택(Stack)과 큐(Queue) 자료구조 스택(Stack)과 큐(Queue) 자료구조 스택(Stack) 자료구조 삽입과 삭제 연산이 후입선출(LIFO : Last-In First-Out)로 이뤄지는 자료구조 * 후입선출 ⇒ 삽입과 삭제가 한 쪽에서만 일어난다. - 새 값이 스택에 들어가면 top이 새 값을 가리킨 soobin0821.tistory.com 시간 복잡도(노드 수 : V, 에지 수..

Previous Post 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상 읽기/출력/저장 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상 읽기/출력/저장 OpenCV(Open Source Computer Vision Library) : 실시간 컴퓨터 비전을 목적으로 한 라이브러리 https://opencv.org Home OpenCV provides a real-time optimized Computer Vision library, tools, and hardware. It also supports model execution for Ma soobin0821.tistory.com Goal 원본 영상에 Salt and Pepper 노이즈 추가 노이즈 추가된 영상을 출력 및 저장 Conte..

OpenCV(Open Source Computer Vision Library) : 실시간 컴퓨터 비전을 목적으로 한 라이브러리 https://opencv.org Home OpenCV provides a real-time optimized Computer Vision library, tools, and hardware. It also supports model execution for Machine Learning (ML) and Artificial Intelligence (AI). opencv.org Goal 원본 영상 읽기 원본 영상을 화면에 출력 원본 영상을 파일에 저장 Content 읽어 올 영상 파일을 실행 파일과 같은 폴더에 위치시킨다. Code #include #include using nam..

스택(Stack) 자료구조 삽입과 삭제 연산이 후입선출(LIFO : Last-In First-Out)로 이뤄지는 자료구조 * 후입선출 : 가장 나중에 삽입된 데이터를 가장 먼저 삭제한다. ⇒ 삽입과 삭제가 한 쪽에서만 일어난다. - 새 값이 스택에 들어가면 top이 새 값을 가리킨다. - 스택에서 값을 빼낼 때 pop는 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다. 스택 용어 top : 삽입과 삭제가 일어나는 위치 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 top : top 위치에 현재 있는 데이터를 단순 확인하는 연산 큐(Queue) 자료구조 삽입과 삭제 연산이 ..

문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리(Tree) 자료구조 트리(Tree) 자료구조 트리(Tree) 자료구조 노드와 에지로 연결된 그래프의 특수한 형태 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리 soobin0821.tistory.com 코드 #include #include using namespace std; voi..

트리(Tree) 자료구조 노드와 노드가 에지로 연결된 그래프의 특수한 형태 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 정보의 단위 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리의 최상단 노드 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 리프 노드 : 트리의 최하단 노드 (자식 노드가 없는 노드) 서브 트리 : 전체 트리에 속한 작은 트리 트리의 특징 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다. 데이터베이스 시스템이나..

문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 유니온 파인드를 위한 대표 노드 자료구조를 초기화한다. (진실을 아는 사람 데이터, 파티 데이터) 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결한다. 각 파티의 대표 노드와 진실을 아는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인함으로써 과장된 이야기를 할 수 있는지 판단한다. 유니온 파인드(Union-Find) 알고리즘..

유니온 파인드(Union-Find) 알고리즘 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 + 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 유니온 파인드 알고리즘 핵심 이론 union 연산 각 노드가 속한 집합을 1개로 합치는 연산 void unionfunc(int a, int b) { // a와 b의 대표 노드 찾기 a = find(a); b = find(b); if(a != b) { parent[b] = a;// 두 원소의 대표 노드끼리 연결 } } find 연산 자신이 속한 집합의 대표 노드를 찾는 연산 int find(int a) { if(a == parent[a]) { return a;// a가 대표 노드면 반환 } else { // a의 대표 노드값을 find..