본문 바로가기

PS831

[자바] 백준 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.
[자바] 백준 24444 - 알고리즘 수업 - 너비 우선 탐색 1 (boj java) 문제 : boj24444 일단 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; priva.. 2022. 6. 3.
[자바] 백준 4108 - 지뢰찾기 (boj java) 문제 : boj4108 무지성 구현문제이다. RxC 배열의 모든 칸을 보면서 '*'을 만날 시 그 주변 8개의 칸에 대해 카운트를 시켜주면 된다. 주의점은 '*'이었던 위치는 특별한 값으로 표시를 해주면 좋다(이하 코드에선 -1로 했음). 시간복잡도는 O(8RC) 이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; import java.util.stream.Stream; public class Main { private void solution() throws Exception { BufferedReader .. 2022. 6. 2.
[자바, 파이썬] 백준 13706 - 제곱근 (boj java) 문제 : boj13706 단순히 제곱근(루트)을 구하는 간단한 문제긴한데, 문제는 정수의 자리수가 최대 800자리나 된다는 점이다. 따라서 큰 수 연산이 필요하다. 파이썬의 경우엔 애초에 무한정 크기의 숫자 표현이 가능하다. 다만 단순히 int(input())**0.5 와 같은 코드로는 불가능한데, 너무 큰 수에대해서는 **0.5가 사용 불가하다고 한다. 찾아보니 math에 isqrt 라는 함수가 있어서 그걸 사용했다. 자바의 경우엔 우선 큰 수의 경우엔 BigInteger로 표현 가능하다. 그리고 BigInteger에 sqrt라는 함수가 있으므로 해당 함수를 사용하면 되는데, 문제는 이게 자바 9에서 추가되었다. 따라서 자바9 이상에서는 간단하다. 자바 8 이하에서 짤려면 비트 연산을 활용해서 직접 제.. 2022. 6. 1.
[자바] 백준 21941 - 문자열 제거 (boj java) 문제 : boj21941 기존에 그리디로 생각해서 풀었었는데, 재채점이 되어 틀려있었다. 기존 틀린 풀이는 여기에 있다. 다시 풀어서 작성한다. 문자열 s를 각 인덱스(이하 idx)를 정점으로 하는 가중치를 가지는 방향 그래프로 바꿔서 생각해보자. 이 때, '문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.' 라는 부분은 idx -> idx+1 로 가는 가중치 1의 간선으로 바꿀 것이다. 그리고 문자열 Ai와 그에 따른 가중치는 예를들어 s가 "abcd"이고, A1이 bc이고 가중치가 3이라고 한다면 idx=1 -> idx=3으로 향하는 가중치 3의 간선이라고 할 수 있다. 예제 입력 1을 봐보자. abcxyzxabc 2 abc 10 xyz 5 위에서 말한 그래프로 그려보면 다음과 같다. .. 2022. 5. 31.
[자바] 백준 6318 - Box of Bricks (boj java) 문제 : boj6318 입력으로 들어온 n개의 hi의 합이 n으로 나누어 떨어진다고 했으므로, 잘 생각해보면 결국 모두 동일한 높이인 sum(hi)/n 으로 맞춰줘야 한다. 즉, sum(hi)/n 보다 큰 hi들에서 하나씩 빼서 sum(hi)/n 미만의 hi들에 더해줘야 한다. 이 말은 다시 말해, n개의 hi들에 대해 이하의 값을 구하면 된다. 여기서 hi_k는 k번째 hi 값을 의미하고, sum(hi)/n은 n개의 hi값의 합을 n으로 나눈 값이다(나누어 떨어진다는 조건이 있으므로 정수). 말로 설명하면, sum(hi)/n보다 큰 hi값을 초과한 값 부분만 다 더해주면 답이 된다. 코드 : github import java.io.BufferedReader; import java.io.IOExcepti.. 2022. 5. 31.

티스토리툴바