본문 바로가기

전체 글1068

백준 15738 자바 - 뒤집기 (boj 15738 java) 문제 : boj15738 풀이 첫 줄에 강력한 스포가 있다. 혹시 아직 못 풀어서 이걸 어떻게 풀지? 생각되어 풀이를 봤다면, 이하 풀이를 보면 많이 짜증날 수 있으니 다시 한번 문제를 잘 읽어보고 직접 도전해보는걸 추천한다. ------- 풀이 : 애초에 배열 A가 아무런 의미가 없다 ㅋㅋㅋ 그냥 입력받은 n과 k만 가지고 각 m개의 연산에 따라 사칙연산으로 k의 위치만 바꿔주면 된다. A. i가 양수일 때 i 그리고 i-k+1로 k를 변경해주면 된다. B. i가 음수일 때 n+i+1 까지 영향을 끼치므로, 그보다 k가 작다면 무시하면 된다. -> 그리고 2*n-k+i+1로 k를 변경해주면 된다! 따라서 시간복잡도는 O(M)이다. N은 아무런 영향을 끼치지 않는다. 이.. 2022. 4. 20.
백준 1940 자바 - 주몽 (boj 1940 java) 문제 : boj1940 고유한 번호를 a라고 할 때, 결국 알아야 하는 것은 n개의 a에 대해 현재 보고 있는 a값을 기준으로 m-a가 n개 중에 존재하는지만 알 수 있으면 된다. 따라서 HashSet을 사용하면 쉽게 풀 수 있다. 이 때, 만약 '고유한 번호'가 아니라 중복되는 것이었다면 HashMap으로 개수도 체크해야 했을 것이다. 로직은 그럼 다음과 같다. A. N개를 입력받으면서 HashSet에 넣는다. B. N개를 순회하면서 m-a가 HashSet에 존재하는지 확인한다. 존재한다면 카운트를 +1 시킨다. C. 이 때 m이 짝수이고 m/2인 값이 존재한다면 m-a == a 이므로 이 경우는 빼야하니 카운트 -1 시킨다. D. 최종적으로 중복된 경우를 빼기 위해 카운트/2를 해서 출력해주면 된다... 2022. 4. 19.
코드업 4040 자바 - 펜션 (CodeUp 4040 java) 문제 : CodeUp4040 어차피 중간에 하루라도 지낼 수 없다면 조건이 만족되지 않는다. 따라서 s부터 시작해서 매번 가장 길게 지낼 수 있는 방에서 지내면 된다. 그러다가 지낼 수 없는 날이 되면 -1, t 이상이 됬다면 변경 횟수를 출력하면 된다. 증명은 간단한데, 매번 가장 길게 지낼 수 있는 방이 아닌 다른 곳에 묵었을 때 더 이득이 되는 경우가 있다면 위의 추론이 틀린 것이다. 하지만 더 짧은 기간 지낼 수 있는 방을 고르더라도 동일한 변경횟수까진 나와서 더 낮은 변경 횟수가 될 수 없음은 직관적으로 알 수 있다. 따라서 그리디하게 선택하면 된다. 그럼 해당하는 날에 어느 방이 가장 길게 묶을 수 있는 방인지 어떻게 알 수 있을까? 이건 날을 거꾸로 진행하면서 몇 일을 지낼 수 있는지 pre.. 2022. 4. 18.
[자바] 프로그래머스 - 타겟 넘버 (코딩테스트 연습 Lv2) 문제 : Programmers-타겟넘버 결국 주어진 numbers를 순서대로 + 한번, - 한번씩 모든 경우를 구해보면 된다. 이 경우 O(2^n)이 된다(+,-의 2가지 경우를 n번 봐야 하므로). 예를들어 numbers가 [1, 2, 3]일 경우 다음과 같이 진행된다. 이 중 target과 동일한 경우를 세서 return해주면 된다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges */ class Solution { int cnt = 0; private void rec(int[] numbers, int target, int idx, int sum) { if (idx == numbers.length.. 2022. 4. 18.
백준 17550 자바 - Inquiry I (boj 17550 java) 문제 : boj17550 prefix sum (누적합)을 안다면 쉽게 풀 수 있다. 누적합 배열을 하나는 n개를 원래 값 대로, 하나는 n개를 제곱해서 합한 누적합 배열을 만든다. 전자를 a, 후자를 b라고 하겠다. 그럼 이후 특정 범위의 합을 O(1)로 알 수 있으므로, b[i] * (a[n]-a[i])에 대해 i를 1부터 n까지 진행하면서 가장 큰 값을 찾으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2022. 4. 18.
백준 17359 자바 - 전구 길만 걷자 (boj 17359 java) 문제 : boj17359 우선 브루트포스로 모든 경우를 본다면 10! 번을 봐야 한다. 사실 이건 360만번 정도로 충분히 가능한 횟수이다. 문제는 모든 경우를 이어본 후, 한땀한땀 바뀌는 부분을 구하려면 문자열의 길이가 최대 100 이므로 O(10!*100)이 필요하게 된다. 따라서 시간초과(사실 3억번정도에 중간에 추가 연산(세세한 덧셈 뺄셈 같은 것들)이 거의 없어 C나 C++이면 통과될것같긴하다 ㅋㅋ)가 날 것이다. 그럼 시간을 뺄 수 있는 아이디어를 생각해보자. 1. 각 묶음 내에서 바뀌는건 고정이다. 즉, 어떻게 배치하게 되던지, 각 묶음 내에서 바뀌는건 어쨌든 고정적으로 바껴야 한다. 따라서 입력을 받으면서 내부에서 바뀌는걸 미리 세두자. 내 경우엔 confirmedCnt가 해당 역할을 한다.. 2022. 4. 17.
AtCoder Beginner Contest 248 참여후기 (ABC248) 대회 : abc248 코드 : github 오랜만에 AtCoder를 참가해봤다. 이것보단 CodeForces를 더 좋아하는데(앳코더는 번역기를 못쓴다 ㅠ), 요즘들어 시간대가 항상 애매해서 참가를 못하고 있다. 앳코더는 일본에서 개최하는 만큼 시간대가 참여하기 괜찮은 것 같다. 총 8문제 중 패널티 없이(첫 제출에 한방에 통과) 4솔했고, 그게 참가자 약 7000명 중 1700등 정도였다. Beginner라고 적혀있긴한데 항상 보면 백준 기준 A,B는 브~실, C,D는 골~플, 그 이상은 플~다 수준으로 내는 것 같다. 심지어 8문제에 시간은 100분이다. 빠르게 푸는건 잘 못하는 내겐 특히 어렵게 느껴진다(백준에서 플래나 다야도 몇 개 풀긴했지만, 대부분 한 문제에 1시간 넘게 들어간다 ㅠ 그러니 대회.. 2022. 4. 17.
백준 15492 자바 - 뒤집기 (boj 15492 java) 문제 : boj15492 바로 직전에 풀었던 19585번 '전설'의 경우 시도횟수가 18번이었는데, 이번엔 29번이었다 ㅂㄷㅂㄷ... 이번에 포기안하고 계속 시도해본 이유는, 테스트케이스 랜덤 생성기로 400만개를 돌려보니 괜찮은 시간이 나왔기 때문이었다. 결론적으로는 '1 2 3 1 2 3 1 2 3 ...'와 같은 케이스를 제대로 못잡아 내서 시도횟수가 많아졌다(랜덤 생성기라 그런 케이스가 안나오니까) 풀고 보니 다른 분들은 해싱과 KMP 등으로 풀었다는데, KMP까진 적용이 이해가 됬는데 해싱으로 푼다니 생소하다. 해싱은 'Lexicographically Minimal Cyclic Shift' 라는걸 쓰면 된다고 한다. 처음들어본다. 내 경우엔 실력이 부족하니 몸으로 때워서 해결했다. 시뮬레이션으로.. 2022. 4. 16.
백준 19585 자바 - 전설 (boj 19585 java) 문제 : boj19585 다른 의미로 전설이었다. 보통은 포기하고 넘어갔을텐데 이론상(?) 가능할 것 같아서 계속 하다보니 오기가 생겨서 끝까지 해보기로 했었다 ㅋㅋㅋ 풀고보니 자바한정으로 통과하기 어려운 문제였다. 시간초과난 로직으로 다른 언어론 통과가 되더라 ㅠ 시도한 내용들은 이하와 같다. 1. 이왜플(이게 왜 플래)을 외치며 모든쌍을 HashSet에 넣었다가 당연히 시간초과(이하 TLE). -> 색상과 닉네임이 둘 다 최대 4000개씩 이므로 모든 쌍을 만들면 O(4000^2) 이라고 대충 생각해서 해봤었다. 하지만 String이란 점을 간과했다. String + String이 결국 두 문자열 길이의 합 만큼 시간복잡도가 들어가므로, 실제론 O(4000^2 * (1000+1000)) 이다. Str.. 2022. 4. 15.
백준 11444 자바 - 피보나치 수 6 (boj 11444 java) 문제 : boj11444 분할 정복을 이용한 거듭제곱 최적화(이 글)을 보면 풀 수 있다! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static final long MOD = 1_000_000_007l; private long[][] matrixMult(long[][] a, long[][] b) { long[][] arr = new long[2][2]; arr[0][0] = (a[0][0]*b[0][0]%MOD + a[0][1]*b[1][0]%MOD)%MOD; arr[1][0] = (a[0][0]*b[0][1]%MOD + a[0][1]*b[1][1]%MOD)%.. 2022. 4. 13.

티스토리툴바