전체 글

[BOJ/JAVA] 20551번: 마스터 배지훈의 후계자

20551번: Sort 마스터 배지훈의 후계자https://www.acmicpc.net/problem/20551키워드먼저 제자들에게 N개의 원소를 가진 배열A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다.그 다음 M개의 질문을 한다.제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력단, D가 B에 존재하지 않는 경우에는 -1를 출력구현정렬 후 탐색이 이루어지므로, 입력값을 정렬할 필요가 있다.중요한 것은 가장 먼저 등장한 위치를 출력이므로 이분탐색으로 찾더라도 가장 앞에 있는 원소를 찾아야 한다. 템플릿low, high 모두 범위 안에 들어오도록 한다.반복문의 속행 조건은 low≤high (항상 high가 low 이상이여야 한다.)해당 숫자를 찾은 경우가장 앞에 있는 원..

[BOJ/JAVA] 15810번: 풍선 공장

15810번: 풍선 공장https://www.acmicpc.net/problem/15810키워드풍선을 담당하는 N명의 스태프대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰각 스태프가 풍선 하나를 만드는 시간(분) A_i를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?구현매개변수 탐색을 이용하여 구현한다.범위가 int 범위를 초과하므로 long 자료형을 이용한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 가장 빨리 만들 수 있는 직원이 걸리는 시간 * M 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;mid 시간내로 만들 수 있는지 체크한다. mid 시간 내로 만들 수 있다면high = ..

[BOJ/JAVA] 16401번: 과자 나눠주기

16401번: 과자 나눠주기https://www.acmicpc.net/problem/16401키워드반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.구현나누는것 여러개로 나눌 수 있지만, 하나로 합칠 수 없음에 주의하자. 매개변수 탐색을 이용하여 구현한다. 템플릿low, high 값은 항상 범위 내로 설정한다.low = 0high = 길이가 가장 긴 과자 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2..

크롤링과 XPath

크롤링💡웹 페이지를 그대로 가져와서 데이터를 추출해 내는 행위인터넷에 존재하는 많은 정보를 사람이 하나씩 찾기는 매우 어렵다.따라서 이를 필요한 것만 탐색하기 위하 크롤러를 사용한다.크롤링과 스크래핑크롤링탐색에만 초점을 맞춘다.해당 페이지에 방문 후 그 페이지의 내용과 링크의 복사본을 저장한다.스크래핑정보 추출에 초점을 맞춘다.예특정 게시판의 게시글들의 조회수를 추출한다.특정 게시글의 작성자 이름을 추출한다.특정 페이지 입력창의 input element을 추출한다.정적 크롤링과 동적 크롤링페이지 형태가 동적인 형태로 많이 바뀌게 되면서 크롤링도 동적 크롤링을 많이 사용하는 추세이다.정적 크롤링동적 크롤링한 페이지 내 원하는 정보가 전부 드러나는 정적인 데이터를 크롤링하여 가져오는 것여러 페이지를 이동하며..

[BOJ/JAVA] 1351번: 무한 수열

1351번: 무한 수열https://www.acmicpc.net/problem/1351키워드무한 수열 A는 다음과 같다.A_0 = 1A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.0 ≤ N ≤ 10^122 ≤ P, Q ≤ 10^9구현중요한 것은 N, P, Q의 범위가 매우 크다는 것이다.배열로 만들기에는 너무 크기 때문에, Map을 이용하여 필요한 데이터만 저장하도록 하자.int 대신 long 자료형을 이용하자statch HashMap cacheA_i에서 i일 때 A_i의 값을 저장한다.statc long dp(long index)index가 0인 경우1을 반환한다.캐시값이 존재하는 경우캐시값을 반환한다.A[index] = A_[i..

[BOJ/JAVA] 2302번: 극장 좌석

2302번: 극장 좌석문제 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.https://www.acmicpc.net/problem/2302키워드공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.“VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.주어진 조건을 만족하면서 사람들..

[BOJ/JAVA] 11052번: 카드 구매하기

11052번: 카드 구매하기요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.https://www.acmicpc.net/problem/11052키워드카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재민규는 돈을 최대한 많이 지불해서 카드 N..

[BOJ/JAVA] 5557번: 1학년

5557번: 1학년상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.https://www.acmicpc.net/problem/5557키워드마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다.상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다.상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램구현초기값은 항상 맨 앞에 있는 숫자이다.결과..

플로이드 최단 경로 알고리즘

플로이드 최단 경로 알고리즘💡모든 정점 쌍에 대해 최단 거리를 구할 때 쓰는 알고리즘개요board[u][v]정점 u에서 정점 v까지의 최단거리를 저장최단 거리를 찾는 방법정점 u에서 정점 v까지 바로 가는 거리를 w(u, v)라고 하자이 때, u→a→v를 가는 거리가 u→v 거리보다 짧다면 갱신하는 방식이다.코드public class 플로이드 { static int board[][]; static void floyd() { // 자기 자신의 거리는 0 for (int i = 0; i < board.length; i++) { board[i][i] = 0; } // 거리 계산하기 for (int k = 0; k < board.length; k++) { for (int i = 0; i < board.lengt..

벨판-포드의 최단 경로 알고리즘

벨판-포드💡다익스트라의 음수 간선 문제를 해결한 최단 경로 알고리즘다익스트라와의 차이벨판-포드는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄이는 방식동작 과정upper[]시작지점으로부터 각 정점까지 최단 거리의 상한시작점→시작점의 거리는 0나머지는 매우 큰 수로 저장시작점이 아닌 임의의 두 지점 u, vdist[u]시작지점 → u 까지의 최단 거리dist[v]시작지점 → v 까지의 최단 거리이때, 다음이 성립한다.dist[v] ≤ dist[u] + w(u, v)dist[u] ≤ upper[u]upper[u] + w(u, v) ≤ upper[v]종료 조건과 정당성의 증명어떻게 upper[] 의 값을 dist[] 값으로 만들 수 있..