본문 바로가기

전체 글1104

[자바] 백준 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.
[자바] 백준 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.

티스토리툴바