본문 바로가기

분류 전체보기176

(자료구조 & 알고리즘 정리) 최소 비용 신장 트리, Kruskal, Prim (2023.06.25) 1. 최소 비용 신장 트리 1) 신장트리(Spanning Tree) 란? - 그래프 내의 모든 정점을 포함하는 트리 - 최소 연결을 해서 간선의 수가 가장 적음 2) 최소 비용 신장 트리란? - 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 3) 최소 비용 신장트리의 특징 - 각 간선의 가중치가 동일하지 않을 때, 단순히 가장 적은 간선을 사용한다고 최소 비용 신장 트리를 구할 수 있는 것이 아님 - 가중치를 고려하여 최소비용을 선택해야 함 - N개의 정점을 가지는 그래프에서는 반드시 N-1개의 간선만을 사용 - 사이클이 포함되어서는 안됨 으아리.,ㄴㅁ얼매ㅑ어리ㅏㅁㄴ 2. Kruskal 알고리즘 1) 탐욕적인 방법을 사용하여 간선을 하나씩 선택해서 MST를 찾는 알고리즘 2) 구현 방식 최초.. 2023. 6. 25.
(자료구조 & 알고리즘 정리) 서로소집합, 유니온파인드 (2023.06.24) 1. 서로소 집합 1) 개념 - 집합 A와 집합 B에 공통된 원소가 존재하지 않으면 A와 B를 서로소 집합이라고 함 2) 서로소 집합 표현 방법 - 연결리스트 - 트리 3) 연산 - Make-Set(x) : 유일한 멤버인 x를 포함하는 새로운 집합을 생성하는 연산 //슈더 //p[x] : 노드 x의 부모 저장 //rank[x] : 루트 노드가 x인 트리의 랭크 값 저장 Make-Set(x) { p[x] = x rank[x] = 0; } // for(i=1; i rank[y]: p[y] = x; else p[x] = y if(rank[x] == rank[y] : rank[y] ++; 4) Union 연산의 효율을 높이기 - 기존 코드 //슈더 Union(x,y) p[Find-Set(y)] = Find-Se.. 2023. 6. 24.
(자료구조 & 알고리즘 정리) 그래프(DFS, BFS) (2023.06.23) 1. 그래프 표현 방식 1) 인접행렬 - 노드의 개수가 N일 때, N*N 행렬(N*N의 2차원 배열)을 만들어 x행과 y행이 연결 되어 있으면 1, 되어 있지 않으면 0을 행렬 값으로 가지도록 표현 - 무방향 그래프 모든 간선이 양 방향으로 이동이 가능한 것이라 간주 x번째 노드와 y번째 노드가 연결되어 있고 그 배열을 adj라 하자 => adj[x][y] = adj[y][x] = 1 행렬은 왼쪽 대각을 기준으로 양쪽이 대칭이 됨 => 대각을 기준으로 양쪽을 모두 사용하지 않고 행 행인 경우 중 하나만 사용해도 됨 - 가중 그래프 행렬의 값을 가중치로 저장 가중치>=0 이라면 간선이 없는 곳의 값을 -1 로 하 - 특징 구현 간단 특정 두 노드가 인접한지 상수시간에 파악 가능 메모리 낭비 심함(정점에 비.. 2023. 6. 23.
(Java)백준 1991. 트리 순회 1. 문제 조건 N개의 노드를 가진 트리가 노드 자신과 그 노드에 대한 왼쪽, 오른쪽 자식 주어지는 형태로 입력값이 들어옴. 주어진 트리를 전위, 중위, 후위 순회한 결과를 출력해야 함 2. 아이디어 문제에 대한 특별한 아이디어보다는 트리의 구현이 필요했던 문제. 입력되는 노드 값이 A ~ Z만 가능하므로 크기가 26인 배열을 활용해도 괜찮음(메모리 낭비 크지 않을 것이기 때문) 하지만 트리 구현 공부를 할 겸, 노드 클래스와 트리 클래스를 필요에 맞게 직접 만들어 구현해 봄. 3. 구현 - 아쉬운 점 : 트리 클래스의 search 부분 구현이 탐색과 삽입의 기능을 모두 하고 있어 아쉬움이 남음. search는 해당 data를 찾는 노드를 Root부터 찾기 시작해서 최종적으로 새로 들어갈 data가 들어.. 2023. 6. 20.
[Java] 람다식(Lamda) 개념 및 사용 정리 1. 람다함수 개념 1) 익명함수를 지칭하는 용어(메소드의 이름 필요 없음) 2) 수학에서 사용하는 함수를 보다 단순하게 표현, 함수를 하나의 식으로 표현 3) 함수형 인터페이스의 인스턴스를 생성하여, 함수를 변수처럼 선언 4) 1급 객체 -> Stream API의 매개변수로 전달 가능 2. 람다의 특징 - 람다식 내의 지역변수는 final을 붙이지 않아도 상수로 간주 - 람다식으로 선언된 변수명은 다른 변수명과 중복 불가 - 람다식으로 생성된 순수 함수는 함수형 인터페이스로만 선언 가능 3. 람다의 장단점 1) 장점 - 코드 간결해짐 - 개발자의 의도가 식에 드러나게 되어 가독성이 높아짐 - 함수를 만드는 과정 없이 한번에 처리해 생산성 높아짐 - 병렬 프로그래밍 용이 2) 단점 - 람다를 사용하여 만.. 2023. 6. 20.
(자료구조 & 알고리즘 정리) 분할정복 (2023.06.15) 1. 분할정복 1) 개념 - 분할 : 해결할 문제를 여러 개의 작은 부분으로 나누기 - 정복 : 나눈 작은 문제를 각각 해결 - 통합 : 해결된 답을 모으기 2) 코드 Recursive_Power(x,n) { if (n==1) return x; if n is even y = Recursive_Power(x, n/2); return y*y; else y = Recursive_Power(x, (n-1)/2); return y*y*x; 2. 문제 1) 2023. 6. 15.

티스토리툴바