내가보려고만든 메자노트

최소 스패닝 트리(Minimum Spannig Tree) = 최소 신장 트리 : 스패닝 트리 중 가장 작은 가중치의 간선으로 구성된 트리를 의미한다. 조건 본래의 그래프의 모든 노드를 포함 간선의 가중치의 합이 최소여야 한다 모든 노드가 서로 연결되어있다 트리의 속성을 만족 (사이클이 존재하지 않는다) ↓스패닝 트리란? 더보기 스패닝 트리란? : 그래프의 최소 개수의 간선으로 이뤄진 트리 (n개의 노드가 존재한다면 간선은 항상 n-1개이다) 모든 노드가 연결되어야 함 사이클이 존재하지 않음 즉, 최소 스패닝 트리에서 최소 가중치의 합 조건만 빠진 트리를 의미. 이 최소 스패닝 트리 문제를 다루는 알고리즘에는 2가지가 있다. 1. 크루스 칼(Kruskal) 알고리즘 : 두 노드 간 제일 작은 가중치의 간선..

최소 스패닝 트리 2가지 알고리즘 내용 문제 보러 가기 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이 문제는 최소 스패닝 트리의 가장 기본적인 구현을 다루는 문제이다. 최소 스패닝 트리는 스패닝 트리 중(그래프 내의 모든 정점을 포함하는 트리) 연결된 간선 가중치가 가장 작은 것들로 구성된 트리를 의미한다. 모든 정점을 포함하기 위해서는 하나의 트리로 연결돼야 하는데 이때 사용하는 알고리즘이 크루스칼, 프림 2가지의 방법이 있다. 이 중 크루스칼을 이용하여 풀이하였다. 문제풀이 크루스칼 알고리즘은 Union-Find를 사용하여 구현할 수 있다. -> Union-Find 설명 - 간선의 정보를 ..

문제 보러 가기 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 이 문제는 유니온 파인드라는 알고리즘을 이용하여 합집합을 만들고, 판단하는 문제이다. 자료구조를 코드로 만들어 표현하는 부분을 더 연습해야겠다고 생각했다! 유니온 파인드(Union-Find) 알고리즘이란? 그래프 알고리즘 중 하나이다. 분리 집합, 합집합 찾기의 의미를 갖는다. parent [] 배열로 각 노드가 어떤 부모 노드 아래에 있는지 그래프로 만든다. x 1 2 3 parent[x] 1 2 3 -..

문제 보러 가기 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 이 문제는 기본 트리구조를 생성하고 트리의 순회 방법인 전위, 중위, 후위 순회를 해보는 트리 자료구조의 기본 문제라고 볼 수 있다. 재귀를 사용하여 구현하였다. 트리는 다양한 방법으로 구현할 수 있다. 나의 경우 트리 클래스를 따로 만들어서 사용하였다. Node [] 배열로 만들어서 구현하는 방법도 존재한다. 문제풀이 -tree 자료구조에 입력받은 각 노드를 위치에 맞게 insert()한다. -전위 순회(preOrder) : 루트 -> 왼..

java는 값이 없는 상태 = null로 표현한다. NullPointerException은 이 null을 만났을 때 발생하는 runtime 예외상황으로 프로그램이 비정상 종료가 될 수 있으므로 따로 처리를 해줘야 한다. 흔하게 발생하기도 하므로 코드 작성 시에 꼭 null상황에 대한 예외처리를 해줘야 한다. 예외상황 값이 null인데 이것을 이용하여 다른 코드를 수행하려고 하면 예외가 발생한다. 몇 가지 예시를 들어보면 아래와 같다. 1) null값을 비교 String str = func(); //함수를 통해 string을 return받음 if(str.equals("a"){ //이부분에서 에러 } 위와 같이 변수 str을 fnc() 메서드 return 받은 값으로 지정하게 될 때, func() 메서드에서..

문제 보러 가기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 이 문제는 백트래킹에 속해있는 문제로 완전 탐색을 통해 풀이할 수 있다. [ 적절한 탐색 조건 + 탐색을 하는 순서 ]를 찾아 접근하여야 통과할 수 있었던 거 같다. 물론 나는 헤매다가 다른 분들의 접근법을 참고하였다 ^_ㅠ 문제풀이 -가장 적게 색종이를 사용하므로 5X5의 색종이부터 탐색 -해당 색종이 영역이 다 1인지 확인 -> 다 1이면 사용할 수 있다는 의미 -해당 색종이를 사용할 수 있다면 사용하고 다른 색종이에 걸리지 않도록 0..

spring에서는 멀티 모듈 기능을 제공하여 따로따로 배포하고 구동할 수 있도록 제공한다. 나의 경우 웹서비스 로직을 담당하는 모듈과 데이터를 수집&저장하는 모듈을 나눠서 사용했는데 데이터를 수집&저장할 때 웹서비스 로직을 담당하는 common모듈에서 필요한 bean을 주입받아야 하는 상황이었다. 따로 설정을 해주지 않으면 위와 같은 멀티 모듈 에러가 나게 된다. common모듈을 -> 데이터 수집&저장 모듈에서 사용 각각 다른 모듈이라 아래와 같이 설정하는 부분이 필요했다! build tool은 gradle을 사용했다. -다른 모듈의 주입을 사용할 모듈의 build.gradle파일 dependencies { compile project(':공통 모듈이름') } ->나의 경우 데이터를 수집&저장 담당하는..

제네릭(Generic)이란? : 클래스나 메서드에서 사용할 내부 데이터 타입을 컴파일 시에 미리 지정하는 방법 ● 장점 1. 클래스나 메소드 내부에서 사용되는 객체의 타입 안정성을 높일 수 있음 List list = new ArrayList(); //이경우 타입 에러가 발생 list.add("abc"); //이경우 타입 에러가 발생하지 않음 list.add(1); Integer라는 타입을 명시해줌으로써 다른 타입의 데이터가 들어가면 에러가 발생하여 미리 잘못된 데이터 타입을 거를 수 있게 된다. 2. 반환 값에 대한 타입 변환 및 타입 검사에 들어가는 노력을 줄일 수 있음 ArrayList list = new ArrayList(); //제네릭을 사용하지 않을경우 list.add("test"); Strin..