1223

N을 입력하면 1부터 N까지의 숫자를 모든 경우의 수를 따져서 나열해야 한다. 그러기 위해서는 일단 N을 입력 받았을 때 1부터 N까지의 수를 가질 수 있게 for문을 작성해야 한다. public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int num = Integer.parseInt(br.readLine()); String word = ""; for (int i = 1; i

에라토스테네스의 체 소수를 판별하는 알고리즘 단일 숫자의 소수 여부 확인 어떤 수의 소수 여부를 확인할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 에라토스테네스의 체 원리 배열을 생성하고 초기화 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (자기 자신은 지우지 않고, 이미 지워진 수는 건너뛴다. 2부터 시작하여 남아있는 수를 모두 출력 public class PrimeNumber2 { static int max = 999; static boolean[] prime; public static void main(String[] args) { prime = new boolean[max + 1]; primeNum(); for..

입력 N: 도시의 개수 M: 도로의 개수 K: 거리 X: 출발 도시 A B: A에서 B로 이동하는 단방향 도로 출력 X에서 출발해 K거리에 있는 도시를 오름차순으로 출력 최단거리가 K인 도시가 존재하지 않으면 -1 출력 핵심 다익스트라 과정 입력을 받을 변수들을 선언한다. /* 무한을 의미하는 값으로 10억을 설정 */ public static final int INF = (int) 1e9; public static int n; // 노드의 개수(N) public static int m; // 간선의 개수(M) public static int di;// 거리(K) public static int start; // 시작 노드 번호(Start) static PriorityQueue pq; //다익스트라를 위..

입력 N: 세로 M: 가로 '-', '|' 출력 소비된 나무 판자의 개수 핵심 '-' 이 모양의 나무 판자는 가로로 연속인 것은 하나로 치고, 연속이 아닌 것은 독립적으로 개수를 센다. '|' 이 모양의 나무 판자는 세로로 연속인 것은 하나로 치고, 연속이 아닌 것은 독립적으로 개수를 센다. 문제를 이해하고 나서 2차원 배열로 풀어야겠다는 생각을 했다. 과정 문제에서 주어진 입력을 받아서 설정 배열(num[])에 담는다. num[0]는 방의 세로 길이, num[1]은 방의 가로 길이를 뜻한다. public class BOJ_1388_백용민 { public static void main(String[] args) throws IOException {..

입력 N 정점(노드)의 개수 M 간선의 개수 K 시작 노드 번호 출력 DFS, BFS를 수행한 결과 핵심 Stack Queue DFS BFS Graph 과정 GraphList 클래스를 생성하고, ArrayList를 활용해서 Graph를 구현한다. class GraphList { //변수 LG를 캡슐화한다. private ArrayList LG; //GraphList의 생성자, 객체를 생성한다. 2차 ArrayList public GraphList() { setLG(new ArrayList()); } //getter public ArrayList getLG() { return LG; } //setter public void setLG(ArrayList LG) { this.LG = LG; } } 각 노드마다..

BFS(Breadth First Search) 너비 우선 탐색 가까운 노드부터 탐색 동작 방식 큐 자료구조 이용하여, 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성 먼저 들어온 것이 먼저 나가며, 가까운 노드부터 탐색하게 된다. 탐색 시작 노드를 큐에 삽입하고 방문 처리 큐에서 노드를 꺼낸다 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 위의 두 단계를 반복한다. 예시 방문 처리된 노드는 밝은 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표시한다. 시작 노드(1)를 방문 처리하면서 큐에 넣는다. 큐에서 요소 하나(1)를 꺼내고, 인접한 노드들(2, 3, 4)을 작은 것부터 큐에 넣고 방문 처리를 한다. 큐에서 요소 하나(2)를 꺼내고, 인접한 노..

DFS(Depth First Search) 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 동작 방식 스택 자료구조 이용 탐색 시작 노드를 처음으로 스택에 삽입한다. 방문처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 위의 과정을 반복한다. 예시 노드 1을 시작 노드로 하여 DFS를 이용해 탐색한다. (검정색으로 칠한 노드는 방문처리가 된 노드이고, 파란 노드는 현재 위치한 노드이다.) 시작 노드(1)를 스택에 넣는다. 인접한 노드 중(2, 3, 4)에서 스택에 없는 가장 작은 숫자의 노드(2)로 이동하고 스택에 넣는다. 인접한 노드(2)로 이동했으면, 그 노드..

리스트로 구하는 법 1. ArrayList 선언 public class GraphList { private ArrayList listGraph; } ) 위의 그림을 보면 각 정점들은 배열로되어있고, 그 정점이 리스트의 헤드가 되어있다. list하나의 각 요소마다 다른 list형태가 나타나게 만들어야 하는 것을 알 수 있다. 그래서 ArrayList의 제네릭 타입이 ArrayList인 것이다. 이렇게 만들어 주고 간단하게 ArrayList의 메서드를 사용해서 노드를 연결시켜주면 된다. 2. 정점들을 생성 public void addVertex(int x){ listGraph.add(new ArrayList(x)); } 리스트의 헤드가 될 정점들을 생성한다. 3. 정점 x와 정점 y를 연결시켜주는 메서드 단..

인접 행렬로 구하는 법 인접행렬 그래프의 연결 관계를 이차원 배열로 나타내는 방식 1. 인접 행렬 선언 public class graphArray{ private int[][] array; } 위 코드의 array 그래프 정점(vertex)들을 이어주는 간선(edge)들을 0과 1로 표시한다. 0: 연결 x 1:연결 o 2. 행렬의 크기 설정 public class GraphArray { private int[][] array; //인접 행렬 선언 public GraphArray(int size) { array = new int[size + 1][size + 1]; //인접 행렬의 크기 } } 생성자로 정사각 행렬을 크기와 함께 초기화한다. 행렬의 인덱스는 0부터 시작하므로 size에 1을 더해준다. 3..

제네릭과 배열의 차이점 1. 배열은 공변, 제네릭은 무공변 공변이란? https://disambur23.tistory.com/20 [Java] 공변 1. 공변의 성질 공변(Variance) A가 B의 하위 타입일 때, T가 T의 하위 타입 extends Read 조상관계는 공통부분이므로 적어도 조상타입은 읽을 수 있다. 자식관계끼리는 읽을 수 없다. Write 어떠한 경우에 disambur23.tistory.com 배열 Child가 Parent의 하위 타입이면, Child[]는 Parent[]의 하위 타입이다. 공변 제네릭 Child가 Parent의 하위 타입이면, ArrayList는 ArrayList의 하위 타입이다. 무공변 ? extends, ? super를 사용해서 공변의 성질을 사용할 수 있지만,..