백준 단계별 문제풀이 4단계 (1차원 배열) https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net # 문제 N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오. # 예제 입력 - 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같..

백준 단계별 문제풀이 4단계 (1차원 배열) https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net # 문제 총 N개의 정수가 주어졌을 때, 정수 v가 몇 개인지 구하는 프로그램을 작성하시오. 정수의 개수가 첫째줄, 배열이 둘째줄, 정수 v가 셋째줄에 입력된다. # 예제 입력 11 1 4 1 2 4 2 4 2 3 4 4 2 출력 3 # 필요개념 배열 전체를 for문으로 돌면서 카운트 하는 방법도 있지만, 이번에는 자바를 공부하면서 알게 된..

백준 단계별 문제풀이 3단계 (반복문) https://www.acmicpc.net/problem/2439 2439번: 별 찍기 - 2 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. www.acmicpc.net # 문제 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. # 예제 입력 (1 = 1 ; j--) System.out.print(" "); for (int k = n - i; k >= 0 ; k--) System.out.print("*"); System.out.println(); } } } # 결과

백준 단계별 문제풀이 3단계 (반복문) https://www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. www.acmicpc.net # 문제 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. Java를 사용하고 있다면, `Scanner`와 `System.out.println` 대신 `BufferedReader`와 `BufferedWriter`를 사용할 수 있다. `BufferedWriter.flush`는 맨..

이번챕터에서는 branch-and-bound 알고리즘에 대해 정리할 예정이다. 목차는 다음과 같다. Branch-and-Bound algorithm 0/1 Knapsack Problem using DFS using BFS (Breath-First Search) using BFS (Best-First Search) BFS, DFS 개념은 아래 게시물에 정리되어있다. https://wanna-developer02.tistory.com/54 [알고리즘] CHAP 5. Backtracking Algorithm (백트래킹 알고리즘) - Monte Carlo Algo- 이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS..

이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS Monte Carlo Algorithm (몬테카를로 알고리즘) Solve problem 1. N Queens Problem 2. Sum-of-Subsets Problem 3. Graph Coloring Problem 4. Hamiltonian Circuits Problem 1. Backtracking Algorithm (백트래킹 알고리즘) 백트래킹 알고리즘은 어떤 조건을 가진 문제의 해결책을 찾기위해 탐색하는 알고리즘 중 하나이다. 모든 경우의 수를 탐색하긴 하지만, 완전탐색 알고리즘과 달리 어떤 조건을 가지고 있으므로 배제되는 경우들이 많아 효율이 더 높다..

이번 게시글은 탐욕 알고리즘의 마지막 알고리즘으로 다익스트라 알고리즘을 정리할 예정이다. 목차는 다음과 같다. Dijkstra's algorithm (다익스트라 알고리즘) 탐욕알고리즘은 아래 게시글에 설명되어있다. https://wanna-developer02.tistory.com/51 [알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘) 이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다 wanna-developer02.tistory.com 1. Dijkstra 알고리즘 다익스트라 알고리즘은 가중치그래프에서 ..

지난 게시글에 이어 이번에는 Greedy Approach 중에서 Kruskal 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다 Kruskal 알고리즘 접근방식 코드 시간복잡도 Greedy Approach와 프림 알고리즘은 아래 링크를 참고하도록 하자! https://wanna-developer02.tistory.com/51 [알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘) 이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다 wanna-developer02.tistory.com 1. Kruskal alg..

이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다음과 같다. Greedy Approach (GA, 탐욕 알고리즘) Minimum Spanning Tree (MST, 최소 신장 트리) GA - 1. Prim's algorithm (프림 알고리즘) 1. Greedy Approach (탐욕 알고리즘) 동적 프로그래밍이 작게 쪼개고 재귀를 통해 작은 것들부터 해결해나가는 기법이었다면, 탐욕 알고리즘은 작게 나누지 않고 그때그때 탐욕스러운 (가장 이익이 되는) 선택을 해나가는 알고리즘이다. 접근 방식은 다음과 같다. 선택 과정 가장 가까운 노드들 중에서 현재 고려사항을 최고로 만족..

이번 챕터에서는 그래프에 대해 알아보고, 그래프를 이용해 최단거리를 구하는 Floyd algorithm (플로이드 알고리즘)도 살펴보려고 한다. 목차는 아래와 같다. 그래프 이론 플로이드 알고리즘 최단경로 구하기 - Floyd vs Brute-force 1. 그래프이론 (Graph Theory) 정말정말 x100!! 중요한 부분이다. 그래프 부분을 해놔야 이후에 나오는 다른 문제들을 해결할 수 있다! 그래프는 여러 개의 점(정점)들이 간선으로 연결된 구조를 나타낸다. 즉 그래프는 정점(V)와 간선(E)로 구성된다. G = (V, E) 그래프 종류 그래프는 가중치 존재의 여부, 방향 존재의 여부에 따라 종류가 다양하다. 가중치그래프 (weighted graph) : 간선에 값(가중치)이 존재한다면 그 그래..