개발블로그by페페

gg

private private가 붙은 변수, 메소드, 클래스는 해당 클래스에서만 접근 가능 default 접근 제어자가 없는 변수, 메소드, 클래스는 default 접근 제어자가 되어 해당 package 내에서만 접근 가능 protected protected가 붙은 변수, 메소드, 클래스는 - 동일 패키지의 class - 해당 class 를 상속 받은 다른 패키지의 class에서만 접근 가능 public public이 붙은 변수, 메소드, 클래스는 어떤 클래스에서도 접근이 가능하다 // 접근제어자를 모두 public으로 단순하게 open할수 있지만, 접근 제어자를 잘 이용하면 코딩 실수 및 중복 등의 위험요소를 제거 가능하다

출발 노드와 모든 노드 간의 "최단 거리" 탐색 - weight가 있을 때 - 에지는 모두 양수일 때 0 Adjacency matrix로 구현해도 좋지만, 시간 복잡도 및 N의 크기에 대비해 Adjacency graph로 구현한다 1 최단 거리 배열 D[N]을 만들고 - 출발 노드 0 - 나머지 노드는 Integer.MAX_VALUE로 할당 2 cycle unit - D[N]에서 가장 값이 작은 노드를 고른다(출발 노드에서 시작) - 해당 노드와 연결된 노드에 에지의 가중치를 업데이트 - Min(D[selected] + edge weight, D[connected]) 3 kaiten space - 모든 노드가 선택될 때까지 반복 - boolean[] visited를 만들어 중복 처리 - 출력

- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 - 우선 순위와 관련 - ArrayList[N]을 사용 1 : 진입 차수(in-degree) - indegree D[N]을 만든다 - 인접 리스트에서 노드와 edge 값이 할당되면, 에지인 D[i] 값을 올려준다(D[i]++;) 2 : cycle unit 진입 차수가 0인 노드를 Queue에 저장한다 해당 노드와 연결된 edge의 D[i]를 1씩 감소시킨다(D[i]--;) 3 : 다음 노드인 2를 선택 모든 노드가 정렬될 때까지 반복 4 : 정렬 결과를 출력

union : 특정한 2개의 노드를 연결해 1개의 집합으로 묶음 find : 두 노드가 같은 집합에 속해 있는지 체크 1차원 배열을 이용 index = 값 value = 대표 노드(집합) find :4 index와 value 가 동일한지 확인한다 // union public static void union(int a, int b) { a = find(a); b = find(b); if (a != b) { label[b] = a; } } // find public static void find(int a) { if (a = label[a]) return a; else return label[a] = find(label[a]); } // checkSame public static boolean checkSa..

Edge list A[2][N] 노드를 배열에 저장하여 에지를 표현 배열에 출발 노드, 도착 노드, (가중치) 를 저장 > - 특정 노드와 관련 있는 에지를 탐색하기는 쉽지 않음 - 노드 중심 알고리즘 x - 벨만 포드 / 크루스칼 사용 Adjacency matrix A[N][N] 노드 중심의 그래프 표현 - 노드와 관련된 에지 탐색시 N번 접근해야 하므로, 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐 - 노드 갯수가 많은 경우 2차원 배열 선언이 불가한 결함(노드가 3만개가 넘으면 heap space 에러 발생) Adjacency List ArrayList[N] - 노드 개수만큼 ArrayList를 선언 - 에지 탐색 시간은 빠름 - 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 ..

Queue queue = new LinkedList(); while (!queue.isEmpty()) { int now = queue.poll(); System.out.print(now + " "); for (int next : A.get(now)) { indegree[next]--; if (indegree[next] == 0) { queue.offer(next); } } }

(Briefing) (문제) (단 하나의 맥락) (입출력과 되어야 하는 그림) N개의 문자열로 이루어진 집합 S 입력으로 주어지는 M개의 문자열 중, S에 포함된 것이 총 몇개인지 구하는 프로그램을 작성하시오 Trie I // 문자열 갯수 N, M (1) S에 포함된 문자열 ... (N) S에 포함된 문자열 (1) 검사해야 하는 문자열 ... (M) 검사해야 하는 문자열 O // M개의 문자열 중 총 몇개가 집합 S에 있는지 출력 *알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않음 *같은 문자열이 여러 번 주어지는 경우는 없다 import java.util.Scanner; public class Main { public static void main(String[] args) { // Inp..

(Briefing) (문제) (단 하나의 맥락) (입출력과 되어야 하는 그림) N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 기부가능한 최대의 랜선 길이 I // 컴퓨터 갯수 N N x N 행렬에 w가 주어진 O // 기부가능 랜선 길이 최댓값 *i번째 줄의 j값이 0일 경우 > 연결랜선 x *a > z : 1~26 // A > Z : 27 ~ 52 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { // point reco..

(Briefing) (문제) (단 하나의 맥락) (입출력과 되어야 하는 그림) 다리는 2 이상, 직선, 섬의 개수는 2~6 모든 섬을 연결하는 다리의 최소 길이를 구하라 BFS + 최소 신장 트리 I // 지도 세로크기 N - 가로 크기 M (1)섬과 바다 정보 1,0 > M개 ... (N)섬과 바다 정보 O // 모든 다리 합의 최소 길이 출력 연결 불가시 -1 출력 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { // point recognition static int[] dr = {-1, 0, 1, 0}; sta..