본문 바로가기

전체 글1104

[자바] 백준 25083 - 새싹 (boj java) 문제 : boj25083 예제 출력대로 자바에서 출력만 잘 해주면 된다. 여기서 주의할 점은 \을 출력하려면 \\를 작성해야 한다는 점과 "를 작성하려면 \"로 작성해야 한다는 점 이다. 다만 자바의 거의 모든 경우에 복붙하면 알아서 문자열을 잘 생성해주므로, 그냥 복붙만 해도 된다. 코드 : github public class Main { private void solution() throws Exception { System.out.println(" ,r'\"7\n" + "r`-_ ,' ,/\n" + " \\. \". L_r'\n" + " `~\\/\n" + " |\n" + " |"); } public static void main(String[] args) throws Exception { new .. 2022. 5. 13.
[자바] 백준 5591 - 最大の和 (boj java) 문제 : boj5591 n개의 데이터에서 연속된 k개의 합이 최대인 지점을 찾으면 된다. 두 가지 정도로 해볼 수 있다. 이하 예시는 다음 입력을 이용해 설명하겠다. 5 3 2 5 -4 10 3 1. 슬라이딩 윈도우 처음 k개의 합을 구한다(A). k개의 윈도우를 옆으로 옮겨다니듯이 생각하면 된다. 그럼 윈도우를 우측으로 한 칸 이동한다면, 직전 윈도우 위치의 첫번째 위치의 값을 빼고 이번에 새로 추가된 값을 더해주면 된다. 이런식으로 이동하면서 최대값을 구하면 된다. O(N) 2. prefix sum 입력을 받을 때 미리 누적합을 계산해둔다. 그렇다면 i번 인덱스에서 이전 k개 원소들의 합은 arr[i]-arr[i-k]가 된다. 이걸 i를 k부터(그래야 i-k가 0 미만으로 안내려갈테니) n까지 증가시.. 2022. 5. 12.
[자바] 백준 11880 - 개미 (boj java) 문제 : boj11880 문제에서 제시된 직육면체에서 A에서 B로 가는 최단 거리를 어떻게 구할 수 있을까? 직육면체를 전개해서 살펴보면 어렵지 않게 피타고라스의 정리만 가지고 최단거리의 길이를 구해낼 수 있다. 다만 이 문제에서는 '서로 반대편에 위치한 A, B점까지의 최단 거리' 라고 했으므로 A, B점은 임의로 변경해도 된다고 볼 수 있다(정확힌 틀려보고 알았다 ㅠㅠ). 그렇다면 그냥 3개의 변의 길이가 주어졌을 때, 위의 x^2+(y+z)^2이 최단이 되는 값을 찾으면 된다(x,y,z에 각각 a,b,c를 넣었을 때). 즉, 이하의 3가지 중 최단 거리를 찾으면 된다. a,b,c 3가지 중 2가지를 택하므로 3C2 = 3가지 경우를 모두 살펴봐서 최단거리를 구하면 된다. 다만 이 경우 직관적으로 x.. 2022. 5. 11.
[자바] 백준 1110 - 더하기 사이클 (boj java) 문제 : boj1110 문제에서 요구하는 대로 구현을 하면 된다. 과정을 정리하면 다음과 같다. 제시된 대로 시뮬레이션 하면서 몇 회 진행됬는지 세기만 하면 되므로 별다른 알고리즘적인 지식은 필요없다. 일반적으로 숫자 그 자체로 연산해서 구하는 방법과, 문자열로 보고 구하는 방법이 있을 것이다. 이하 코드1과 코드2에 두 가지 방법을 모두 구현했으니 코드를 참고해서 구현해보자. 코드1 (정수로 구하기) : github import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { private voi.. 2022. 5. 11.
[자바] 백준 2936 - 채식주의자 (boj java) 문제 : boj2936 우선 이 문제를 풀기위한 가장 기본이 되는 개념부터 알아야 한다. 초등학교나 언젠가 배웠을테지만 까먹었을 수도 있으므로! 삼각형의 넓이는 한 변만 x나 y축에 평행하다면, 평행한 면의 길이 w와, 그와 수직인 높이 h에 대해 w*h/2 로 구할 수 있다. 즉, 아래와 같은 삼각형 3개(검정, 주황, 초록)는 w가 셋 다 동일하고 h도 동일하므로 다른 것 처럼 생겼지만 사실 넓이는 전부 동일하다. 위의 개념만 잘 알고 있다면 문제에서 제시된 삼각형의 어느 지점의 한 점이 주어지더라도 두 구역의 넓이를 동일하게 하는 넓이를 구할 수 있다. 예를들어 아래처럼 주황선으로 나뉜 구역의 넓이는 다음과 같이 w와 h를 잡으면 된다. 이 문제의 경우 입력에 따라 다양한 경우가 존재한다. 따라서 .. 2022. 5. 10.
[ABC250] D - 250-like Number (AtCoder Beginner Contest 250 with Java) 문제 : abc250_d 최대 10^18 까지 표현이 가능해야 한다. 이 때 p n || calc < 0) break; cnt++; } } System.out.println(cnt); } ... 2022. 5. 9.
[ABC250] C - Adjacent Swaps (AtCoder Beginner Contest 250 with Java) 문제 : abc250_c 일단 단순히 swap만 하는 거였다면 별 문제가 없었을 것이다. 문제는 매번 swap해서 바뀌는 각 숫자의 위치를 유효한 시간 내에 찾아내야 한다는 점이다. 만약 매번 전체 배열을 순회하며 찾으려 한다면 O(N+QN)만큼(처음 N은 배열 입력받는 부분, QN은 각 쿼리마다 최대 N번 확인해야 하므로) 필요할 것이므로 시간내에 통과할 수 없다. 따라서 배열을 2개 써서 다음과 같이 한번 생각해보자. N이 5인 경우이다. 원래는 위의 저 '값 배열'만 가지고 해야했는데, '위치 기록용 배열'을 추가로 만들었다. B[z]는 값 z의 현재 idx를 나타낸다. 즉, A[B[z]] == z 이다. 이렇게 메모리를 더 써서 배열 하나를 더 두면 swap 시에 다음과 같이 해볼 수 있다. 현재.. 2022. 5. 9.
[ABC250] B - Enlarged Checker Board (AtCoder Beginner Contest 250 with Java) 문제 : abc250_b 패턴을 잘 살펴보면 결국 NxA행, NxB열의 문자열을 출력하면 된다. 그리고, 시작하는 문자가 '.'으로 시작하는게 A줄, 그 다음 '#'으로 시작하는게 A줄... 을 N줄동안 수행하면 된다. 단순 구현문제긴 한데 반복문에 익숙치 않다면 좀 어려울 수 있다. 4중 for문에서 처음 2중은 N과 A, 그 다음 2중은 N과 B라고 생각하면, 코드로는 4중 for문이지만 개념적으로는 2중 for문이 된다. 그럼 좀 더 쉽게 구해볼 수 있다. boolean값을 잘 설정해서 한번 구현해보자. 참고로 이하 코드에서 'i&1==0'은 i가 짝수라면 true, 홀수라면 false 이다(왜 그런지는 짝수와 홀수를 아무 숫자나 2진수로 바꿔보면 알 수 있다.). 'isWhite^swt'에서 '^.. 2022. 5. 9.
[ABC250] A - Adjacent Squares (AtCoder Beginner Contest 250 with Java) 문제 : abc250_a (1, 1)부터 (H, W) 까지의 모든 square 쌍 (h, w) 대해 이하가 만족하는 경우를 카운팅하면 된다. 코드 : github ... private void solution() throws Exception { int h = nextInt(); int w = nextInt(); int r = nextInt(); int c = nextInt(); int cnt = 0; for (int i = 1; i 2022. 5. 9.
[자바] 백준 8892 - 팰린드롬 (boj java) 문제 : boj8892 각 테스트케이스마다 k가 최대 100개이므로, 모든 쌍을 보더라도 O(T x 100^2)번에 가능하다. 또한 모든 단어의 길이의 합은 10,000이하라고 했으므로, 단어 길이의 합을 L이라 할 때 팰린드롬인지 확인하는 로직이 O(L)짜리 로직이라 하더라도 O(TL x 100^2)으로 가능하다. 또한 팰린드롬인 값이 하나라도 있다면 거기서 종료하면 되므로, 대강 모든 경우를 봐도 시간내에 통과 가능할 것임을 예상할 수 있다. 우선 문자열 S가 팰린드롬인지 확인하는 가장 간단한 방법은, |S/2|까지 인덱스를 증가하면서 앞과 뒤의 문자를 확인하는 것이다. isPalindrome() 함수를 확인해보면 알 수 있다. 그리고 모든 경우를 보는 것은 모든 문자쌍을 만들어보면 된다. 코드의 2.. 2022. 5. 9.

티스토리툴바