본문 바로가기

백준

(10)

그래프 이론과 알고리즘 개념정리 1. 그래프의 개념 그래프(graph)는 원소 간의 관계를 표현하는 비선형 자료구조이다. 그래프는 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. G=(V,E) 에서 G - 그래프 V - 정점의 집합 E - 정점을 연결하는 간선의 집합 2. 그래프의 종류 2.1 무방향 그래프 무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 2.2 방향 그래프 방향 그래프(Directed Graph)는 간선에 방향..0이 있는 그래프이다. 정점 V(i) 에서 정점V(j)를 연결하는 경우 V(i)를 꼬리(tail) 이라 하고 V(j)를 머리(head) 라고 한다. 2.3 완전 그래프 완전 그래프(Complete Graph)는 각 ..

[백준][JAVA]구간 합 구하기4(11659번) - 누적합 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 jwww.acmicpc.net* 문제는 해당 게시물 참고바랍니다. 해당 문제는 누적합을 구하는 문제입니다. 근데 그냥 풀면 시간 초과가 나옵니다.수 많은 시행 착오를 겪었습니다. 해당 문제를 해결한 코드에 대해 설명하겠습니다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.u..

[백준][JAVA]색종이 만들기(2630번) - 분할 정복 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.www.acmicpc.net* 문제는 해당 게시물 참고바랍니다. 분할 정복(Divide and Conquer)이란 재귀를 응용하는 알고리즘으로 여러 알고리즘의 기본이 되는 해결방법입니다.기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념입니다. 분할 정복은 크게 3단계로 나눌 수 있습니다. 1. 원래 문제를..

[백준][JAVA]회의실배정(1931번) - 그리디 알고리즘 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.www.acmicpc.net* 문제는 해당 게시물 참고바랍니다. 그리디 알고리즘이란그리디 알고리즘은 흔히 탐욕 알고리즘이라고도 불리며 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 각 단계에서 한 선택이 최선의 선택을 한 것이길 바라고 전체적으로도 최선이길 바라는 알고리즘입니다. 해당 문제를 해결한 코드입니다.import java.util.*;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner..

[백준][JAVA]평범한 배낭(12865번) - 다이나믹 프로그래밍, 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net* 문제는 해당 게시물 참고바랍니다. 해당 문제는 동적 계획법 1에 분류되어 있으며알고리즘 분류로는 다이나믹 프로그래밍과 배낭 문제에 해당합니다. 다이나믹 프로그래밍이란 흔히 DP라고도 불립니다. 이는 최적화 이론의 한 기술으로, 특정 범위까지의 값을 구하기 위해서 하나의 큰 문제를 여러개의 작은 문제로 나누어 해당 문제들 값을 이용..

[백준][JAVA]스타트와 링크(14889번) - 백트래킹 algorithm 그리고 재귀의 이해 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net * 문제는 해당 게시물 참고바랍니다. 해당문제는 재귀와 백트래킹을 이용하여 동작을 구현하는 문제입니다. 백트래킹이란 해를 찾는 도중 아니다 싶으면 더 이상 깊이 들어가지 않고, 이전 단계로 돌아가 해를 찾아나가는 기법입니다. 모든 경우의 수를 탐색하는 브루트 포스 algorithm과는 다르게 문제를 최적화하여 비교적 빠르게 풀어나갈 수 있습니다. 요약하자면 브루트 포스 - 모든 가지에 다 가봄 백트래킹 - 가지치기를 ..

[백준][JAVA]하노이 탑 이동 순서(11729번) - 재귀 algorithm https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로www.acmicpc.net* 문제는 해당 게시물 참고바랍니다. 해당 문제는 재귀를 사용하여 동작을 구현하는 문제입니다. method 내부에서 method 자신을 다시 호출하는 것을 '재귀호출(recursive call)'이라 합니다.호출된 method는 '값에 의한 호출(call by value)'를 통해 원래의 값이 아닌 복사된 값으로 작업하기 때문에호출한 method와는 관계없이 독립적인 작업수행을 합니다. *..

[백준][JAVA]카드2(2164번) - 스택, 큐, 덱 algorithm https://www.acmicpc.net/problem/2164 2164번: 카드2N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가www.acmicpc.net* 문제는 해당 게시물 참고바랍니다. 해당 문제는 큐(Queue)를 사용하여 동작을 구현하는 문제입니다. Queue는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있습니다. Queue의 경우 LinkedList 컬렉션 클래스로 구현하는 것이 가장 적합합니다.만약 배열기반의 ArrayList와 같은 컬렉션 클래스로 구현하게 되면 데이터를 꺼낼 때마..

[백준][JAVA]블랙잭(2798번) - 브루트 포스 algorithm https://www.acmicpc.net/problem/2798 2798번: 블랙잭첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장www.acmicpc.net* 문제는 해당 게시물 참고바랍니다. 브루트 포스 algorithm이란 모든 경우의 수를 탐색한다는 뜻으로,완전탐색이라고 하며, 해당 알고리즘의 가장 기본적인 접근방식은 해가 존재할 것으로 예상되는 모든 영역을 전부 탐색하는 것입니다. 해당 문제를 해결한 방법입니다.import java.util.*;public class Main { public static voi..

백준 JAVA로 문제 제출방법 (1000번) 안녕하세염슬슬 복학도 해야되고 학교 문제푸는 방식을 연습좀 해보고자 코딩 문제푸는 사이트를 찾아보던중 백준과 프로그래머스를 고민했었습니다.근데 프로그래머스는 상업적으로 이용이 안된다고 해서 백준을 이용하게 되었습니다. 백준 문제 제출방법 우선 제가 제출한 문제입니다.import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int a = scanner.nextInt(); int b = scanner.nextInt(); System.out.println(a+b); }}백준에서는 ..

이전 1 다음

티스토리툴바