자바

[JAVA] 백준 1766 : 문제집

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 해결방법 위상 정렬의 대표적인 문제 중에 하나이다. 근래 위상정렬 문제를 꾸준히 풀어보고 있는데, 풀 때마다 헷갈려서 정리를 한 번 해두려고 한다. 일단 위상정렬은 Topological Sort 라고 부르며, 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 것들을 순서대로 나열하는 건데, 수학 2를 하기 전에 수학 1을 먼저 배워야 하고 그전에 기초수학을 배워야 하는..

JAVA 란?

CS역량이 많이 부족함을 느껴 CS를 조금씩 공부하면서 공부한 것들을 정리해보려고 한다. 그 첫 번째로 가장 자주 쓰고 주로 다루는 언어인 자바로 시작하기로 했다. 1. 개요 - 썬 마이크로시스템즈에서 1995년 개발한 객체 지향 프로그래밍 언어 - 창시자는 제임스 고슬링 2. 철학 - 객체 지향 방법론을 사용해야 한다. - 같은 프로그램이 여러 운영 체제에서 실행될 수 있어야 한다. - 컴퓨터 네트워크 접근 기능이 기본으로 탑재되어 있어야 한다. - 원격 코드를 안전하게 실행할 수 있어야 한다. - 다른 객체 지향 언어들의 좋은 부분만 가지고 와서 사용하기 편해야 한다. 3. 특징 - 플랫폼에 독립적인 언어, 즉 가상 머신인 JVM에 종속적이다. 더보기 자바 컴파일러는 바이트코드인 클래스 파일을 생성하..

[JAVA] 백준 1162 : 도로포장

문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 해결방법 1번에서 N번까지 가는 최소 시간을 출력하는 문제인데, 추가적으로 도로포장이라는 조건이 주어져있다. 포장이 가능한 횟수는 K로 주어지고, 포장을 하게 되면 해당 도시를 잇는 도로를 통과하는 시간이 0이 된다. 그래서 기본 다익스트라에 추가적으로 포장횟수를 기록해야 한다. 원래 배열은 dijk[해당 도시까지 최솟값] 을 나타낸다고 하면 이번 문제에서는 dijk[해당 도시까지 최솟값][포장 횟수] 를 사용한 2차원 ..

[JAVA] 백준 1963 : 소수 경로

문제 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 해결방법 문제를 읽어보면 가능한 비밀번호는 1000 ~ 9999 사이의 숫자이다. 그렇기 때문에 에라토스테네스의 채를 이용해서 9999까지의 소수를 찾아내고 현재 비밀번호에서 각 자리수를 하나씩 변경하며 그 수가 소수라면 다음으로 또 한자리는 변경하는 방식으로 목표 비밀번호까지 최소한의 횟수를 찾는 문제이다. 순서를 정리하면 1. 9999까지 소수를 찾는다. 2. 각 자리수를 변경하며 목표 비밀번호를 찾는데, 거쳐가는 비밀번호도 모두 소수인지 확인해야한다. 추가적으..

[JAVA] 백준 12781 : PIZZA ALVOLOC

문제 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 해결 방법 CCW (Counter-ColockWise) 라는 알고리즘을 쓰는 문제인데, 처음 보는 알고리즘이라 기록해둘 겸 글을 작성하게 되었다. CCW는 '평면에 놓여진 세 점의 방향 관계를 구하는 알고리즘' 인데 CCW 식을 사용해서 양수가 나오면 이 그림과 같이 시계 반대 방향으로 향하는 방향 관계를 가지고 있다고 하고, 음수가 나온다면 이와 같이 시계 방향으로의 관계를 가지고 있다고 알 수 있다. 그러면 0이 나오는 경우는 뭘까? 그때는 세 점의 관계가 평행 즉, ..