본문 바로가기

BOJ749

[자바] 백준 8462 - 배열의 힘 (boj java) 문제 : boj8462 가장 간단한 방법으로, 각 쿼리마다 직접 해당 범위를 순회하면서 가장 많은 등장 수를 찾는 것은 당연히 간단하다. 하지만 그러면 O(TN)이 될 것이므로 시간초과가 나게 된다. 그러니 이번엔 이전 쿼리의 결과를 이용할 방법을 생각해보자. 첫 번째 쿼리가 i=3, j=10이고 두 번째 쿼리가 i=5, j=11 이라고 해보자. 그림으로 나타내면 아래와 같다. 이 경우 만약 위에서 말한 방법대로 매번 직접 순회하며 볼 경우 첫 번째 쿼리는 8번, 두 번재 쿼리는 7번을 봐야하므로 총 15번을 봐야한다. 하지만 첫 번째 쿼리에서 i가 +2가 됬으므로 주황색으로 빗금친 부분을 빼면 2번을 빼면 되고, 마찬가지 방식으로 파란 빗금부븐을 1번 더해줄 수 있다. 그럼 총 15번 필요했던게 3번으.. 2022. 6. 10.
[자바] 백준 13548 - 수열과 쿼리 6 (boj java) 문제 : boj13548 우선 가장 간단한 방법으로, 각 쿼리마다 직접 해당 범위를 순회하면서 가장 많은 등장 수를 찾는 것은 당연히 간단하다. 하지만 그러면 O(MN)이 될 것이므로 시간초과가 나게 된다. 그러니 이번엔 이전 쿼리의 결과를 이용할 방법을 생각해보자. 첫 번째 쿼리가 i=3, j=10이고 두 번째 쿼리가 i=5, j=11 이라고 해보자. 그림으로 나타내면 아래와 같다. 이 경우 만약 위에서 말한 방법대로 매번 직접 순회하며 볼 경우 첫 번째 쿼리는 8번, 두 번재 쿼리는 7번을 봐야하므로 총 15번을 봐야한다. 하지만 첫 번째 쿼리에서 i가 +2가 됬으므로 주황색으로 빗금친 부분을 빼면 2번을 빼면 되고, 마찬가지 방식으로 파란 빗금부븐을 1번 더해줄 수 있다. 그럼 총 15번 필요했던게.. 2022. 6. 9.
[자바] 백준 24513 - 좀비 바이러스 (boj java) 문제 : boj24513 문제를 풀 개념만 확실히 잡는다면, 그 이후로는 구현력에 달려 있는 문제이다. 구현이 상당히 복잡할 수 있다. 구현자체는 코드를 참고해서 짜보고, 일단 개념만 풀이로 작성해보겠다. 이하의 예시를 생각해보자. 3 3 1 0 0 0 0 0 0 0 2 우선 1번 바이러스가 전체 맵을 진행할 때, 각 마을에 도착하는 시간을 재보면 다음과 같을 것이다. 그 다음 2번 바이러스가 차례차례 1번 바이러스의 지점들을 덮으면서 진행해보자. 위에서 동일한 거리끼리 만나게 되었다. 즉, 해당 지점에 각 바이러스는 동일한 시각에 도착한다는 의미이다. 따라서 이 지점에서 3번 바이러스가 만들어지게 되는 것이다. 최종적으로 각 마을마다 감염되는 바이러스의 번호는 다음과 같다. -------------- .. 2022. 6. 8.
[자바] 백준 24508 - 나도리팡 (boj java) 문제 : boj24508 그리디로 생각해보자. 결국 최소 횟수로 이동하면서 K개씩을 만들려면 더 빠르게 없어질 수치가 큰 값에다, 더 느리게 없어질 수치가 작은 값을 밀어넣어야 한다. 따라서 입력으로 들어온 N개의 입력값 Ai 들을 정렬해보자. 그리고 작은 값을 큰 값에 직접 밀어넣으면서 K개를 만들면 없애는 식으로 시뮬레이션을 진행하면 풀 수 있다. 약간의 그리디가 들어간 시뮬레이션 문제로 구현력(?)이 좋다면 어렵지 않게 풀 수 있다. 이하의 코드를 참고해보자. 다만 주의해야 할 예시 2가지를 들어보겠다. [1] 3 2 10000 0 0 0 [2] 5 2 10000 1 0 0 [1] 처럼 모두 0인 경우엔 이미 조건을 만족하므로 별다른 처리없이 YES를 출력해줘야 한다. [2] 처럼 하나만 0이 아닌.. 2022. 6. 8.
[자바] 백준 14725 - 개미굴 (boj java) 문제 : boj14725 알고리즘 분류를 봤다면 트라이를 봤을텐데, 필요없다. 그냥 그래프를 활용할 줄 안다면 풀 수 있다. 결국 다음의 예제 입력 1을 3 2 B A 4 A B C D 2 A C 이하의 그래프 처럼만 표현할 줄 알면 된다. 각 정점은 먹이 이름과 간선으로 이루어진다. 그리고 동일한 depth에 동일한 이름이 존재할 경우엔 먹이 이름을 정점을 추가하지 않는다. 이것만 해주면 된다. 차후 출력 시 간선을 순서대로 순회해주며 출력하는 부분은 이하 코드처럼 매번 정렬을 해줘도 된다. 어차피 N이 최대 1000이므로, 딱히 해싱을 하지 않고 매번 모든 간선에 열결된 정점이름을 확인해도 문제 없다. 딱히 알고리즘 기법이 들어간게 없고, 그냥 그래프 자료구조 응용 문제로 상당히 좋은 문제인 것 같다.. 2022. 6. 8.
[자바] 백준 18818 - Iguana Instructions (boj java) 문제 : boj18818 bfs로 진행하되, 거리가 증가되는 기준이 한 방향으로 일직선으로 장애물을 만나기 전까지 모두가 동일한 거리를 가진다.그리고, 한 방향으로 일직선으로 진행하면서 만난 모든 지점을 큐에 추가하면서 풀어주면 된다. 예를들어 예제 입력 2를 봐보자. 5 ..... .###. ..... .#### ..... 우선 시작점에서 bfs를 진행한 결과에 따른 각 지점의 거리는 다음과 같다. 그리고 현재 거리가 '1'인 지점은 모두 큐에 추가된 상태이다. 맨 윗줄만 봤을 때, 2,3,4번째 칸들은 더이상 진행할 곳이 없으므로 그대로 무시된다. 맨 윗줄 5번째칸에서 진행한 결과는 다음과 같을 것이다. 다음으로 좌측줄 정중앙에서 진행한 결과는 다음과 같다. 마지막으로 맨 아래줄 좌측에서 진행한 결과.. 2022. 6. 8.
[자바] 백준 10986 - 나머지 합 (boj java) --- 이해하기 어렵게 작성한 것 같아서 새로 작성했습니다. 이 글(링크)을 보시는게 더 나을 것 같습니다. --- 문제 : boj10986 i번 까지 누적합을 계산한 값이 arr[i]라고 하자(1 2022. 6. 7.
[자바] 백준 22938 - 백발백준하는 명사수 (boj java) 문제 : boj22938 두 점의 거리가 두 반지름의 합보다 작으면 YES, 같거나 크다면 NO를 출력해주면 된다. 두 점 사이의 거리는 이하 그림을 통해알 수 있듯이 피타고라스의 정리를 통해 얻을 수 있고, 그 값이 r1+r2 보다 더 큰지 작은지에 따라 겹치는지 확인 가능하다. 이 때 한 점에서 만나는 경우는 두 점의 거리와 r1+r2가 동일한 경우이다. 수식으로 보면 다음과 같다. 그리고 양변을 제곱해서 2번째 수식으로 풀어야 실수 오차 없이 풀 수 있다. 주의점은 X, Y, R이 모두 최대 10^9의 큰 수이므로, 제곱한 값이 int 범위를 넘어가게 되므로 long으로 연산을 해줘야 한다. 최대 (r1+r2)^2이 (2*10^9)^2 으로 대략 4*10^18인데, long은 대략 9*10^18 까.. 2022. 6. 6.
[자바] 백준 23808 - 골뱅이 찍기 - ㅂ (boj java) 문제 : boj23808 규칙을 찾아 그걸 그대로 구현해주는 문제이다. 일단 가로로만 보자. 그럼 두 가지 형태가 보이는 것을 알 수 있다. '@ @' 형태와 '@@@@@' 형태이다. 이 때, n=1일 대와 n=3일때를 비교해보면 각 행은 총 길이가 n*5임을 알 수 있고, '@ @'형태의 경우엔 n개의 @ + n*3개의 공백 + n개의 @으로 이루어져 있음을 알 수 있다. 그럼 이걸 우선 함수로 빼두자. 이하 코드에서 printSplitShells가 그 구현이다. 그리고 '@@@@@'형태는 더 간단하게 n*5개의 @으로 이루어져 있다. 이하 코드에서 printFullShells가 이 형태를 나타낸다. 다음으로는 세로로 보자. n*2개의 '@ @'형태 + n개의 '@@@@@'형태 + n개의 '@ @'형태.. 2022. 6. 5.
[자바] 백준 24445 - 알고리즘 수업 - 너비 우선 탐색 2 (boj java) 문제 : boj24445 bfs가 뭔지 모른다면 이 글을 참고해보자. 일반적인 bfs 구현인데, 문제는 다음 정점을 내림차순으로 선택해야 한다. 그리고 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 된다. 그러니 인접 리스트로 간선을 표현하자. 이 때 내림차순으로 다음 정점을 선택해야 하므로, 미리 내림차순으로 각 정점의 간선들을 정렬시켜두면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { int[] answer; ArrayList[] edges; int idx = 0; int[] v; private .. 2022. 6. 4.

티스토리툴바