본문 바로가기

분류 전체보기

 (73)
[백준][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..
자바 복습하기(예외처리편) * 해당 게시물은 자바의 정석(책)을 참고하여 작성하였습니다. 에러 에러는 발생 시점에 3가지 종류로 나뉜다.1. 컴파일 에러 - 컴파일 시에 발생하는 에러2. 런타임 에러 - 실행시에 발생하는 에러3. 논리적 에러 - 실행은 되지만, 의도와 다르게 동작하는 것 여기서 런타임 에러는 2가지로 나뉜다.에러(error) - 프로그램 코드에 의해서 수습될 수 없는 심각한 오류예외(exception) - 프로그램 코드에 의해서 수습될 수 있는 다소 미약한 오류  예외 클래스자바는 오류를 클래스로 정의되어 있다.Exception의 자손 클래스로는 IOExeption, ClassNotFoundException, RuntimeException들이 있는데자바의 예외 클래스는 RuntimeException과 그 외의 E..
자바 복습하기(extends, super, abstract, interface편) * 해당 게시물은 자바의 정석(책)을 참고하여 작성하였습니다. 상속상속이란 기존의 class를 재사용하여 새로운 class를 작성하는 것으로 extends를 붙여서 사용한다.ex)class Child extends Parent {// Child, parent를 확장한}parent - 조상 class로 super classchild - 하위 class 사용시 주의사항1. 생성자와 초기화 블럭은 상속되지 않고 멤버만 상속된다.2. 자손 class의 member 개수는 조상 class보다 항상 같거나 많다.  Object classobject class는 모든 class의 상속계층도의 최상위에 있는 조상class이다.class Member extends Object {//pass}이렇게 하면 Object cl..
자바 복습하기 (객체지향, 클래스, 인스턴스, 오버로딩, 생성자편) * 해당 게시물은 자바의 정석(책)을 참고하여 작성하였습니다. 객체지향언어 자바는 대표적인 객체지향언어이다. 객체지향언어에는 3가지의 주요 특징이 있다. 1. 코드의 재사용성이 높다. - 새로운 코드를 작성할 때 기존의 코드를 이용하여 쉽게 작성할 수 있다. 2. 코드의 관리가 용이하다. - 코드간의 관계를 이용해서 적은 노력으로 쉽게 코드를 변경할 수 있다. 3. 신뢰성이 높은 프로그래밍을 가능하게 한다. - 제어자와 메서드를 이용해서 데이터를 보호하고 올바른 값을 유지하도록 하며 ,코드의 중복을 제거하여 코드의 불일치로 인한 오작동을 방지할 수 있다. class와 object(객체) class - class란 object를 정의해 놓은 것으로 object를 생성하는데 사용된다. object - obj..

티스토리툴바