문제 보러 가기 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 이 문제는 이진트리 자료구조를 이용하여 너비를 구하는 응용문제이다. 너비를 구하는 부분에서 좀 다른 점이 있다면, 각 level마다 최대 너비를 구해야 한다는 점. 가장 왼쪽 자식이 1번 , 가장 오른쪽 자식이 n번으로 너비를 구한다는 점이다. 아래 트리와 같이 구성된다. 문제풀이 - 자신의 번호와(num) 부모 번호(parent) 왼쪽 자식(left) 오른쪽 자식(right)을 갖는 Node 클래스를 만든다. - Node []..
최소 스패닝 트리 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..
제네릭(Generic)이란? : 클래스나 메서드에서 사용할 내부 데이터 타입을 컴파일 시에 미리 지정하는 방법 ● 장점 1. 클래스나 메소드 내부에서 사용되는 객체의 타입 안정성을 높일 수 있음 List list = new ArrayList(); //이경우 타입 에러가 발생 list.add("abc"); //이경우 타입 에러가 발생하지 않음 list.add(1); Integer라는 타입을 명시해줌으로써 다른 타입의 데이터가 들어가면 에러가 발생하여 미리 잘못된 데이터 타입을 거를 수 있게 된다. 2. 반환 값에 대한 타입 변환 및 타입 검사에 들어가는 노력을 줄일 수 있음 ArrayList list = new ArrayList(); //제네릭을 사용하지 않을경우 list.add("test"); Strin..
- Total
- Today
- Yesterday
- programers
- 삼성 sw역량 테스트
- Baekjoon
- 백준
- websocket
- 최소 스패닝 트리
- OS
- 운영체제
- sockjs
- java
- 프로그래머스
- Spring
- 알고리즘
- 삼성 sw역량테스트
- git
- 분리 집합
- 완전탐색
- BFS
- Heap
- SWEA
- 채팅
- DP
- 코딩테스트
- dfs
- 자바
- JavaScript
- MST
- Oracle
- Stomp
- 정렬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |