본문 바로가기

전체 글1104

백준 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.
[세미나 진행 영상] 밑바닥부터 스프링 기반 프로젝트 시작해보기 대학교때 이후로 이렇게 많은 분들 앞에서 진행한 적이 거의 없어서 떨리기도 하고 재밌었습니다. 게더타운 기반으로 세미나 진행한것도 재밌었구요. https://www.youtube.com/watch?v=xqQJIHu378Y 위 영상은 원래 반디캠으로 촬영하려 했는데, 찍고보니 10분만 촬영되서(무료는 10분제한이었는데 몰랐음) 못쓰고 따로 재촬영했습니다. 그러다보니 많이 어색하네요. 사람들 앞에서 말한게 아니다보니. 그래도 내용은 거의 비슷하게 말한 것 같습니다. 세미나인데 마지막에 질문하라는 말이 없는 것도 재촬영해서 그렇습니다. 말하려고 했던 얘기는 결국, 스프링 기반 프로젝트 시작하는거 별거 아니니 갠프도 하고 팀프도 하고 마구 해보라는 내용이었습니다. 그러다보니 우선 왜 스프링을 쓰는지 부터 말해야.. 2022. 4. 13.
백준 24510 자바 - 시간복잡도를 배운 도도 (boj 24510 java) 문제 : boj24510 자바의 replaceAll을 사용해 입력으로 들어온 문자열에 포함된 for와 while을 전부 특정 문자로 변경(이하 코드에서는 ','로 변경)한다. 이후 해당 문자의 개수를 세면 문자열에 포함된 for와 while의 개수를 셀 수 있다. 특정 문자로 변경한 이유는 "foforr"과 같은 경우 1번으로 체크되야 하지만, 그냥 for를 제거만 할 경우엔 foforr -> for 이 되어 2번 세질 수 있기 때문이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Excepti.. 2022. 4. 13.
백준 11004 자바 - K번째 수 (boj 11004 java) 문제 : boj11004 정렬만 할 줄 안다면 바로 풀 수 있는 날먹문제. 정렬 후 K-1 인덱스에 있는 값을 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(.. 2022. 4. 11.
[자바] 프로그래머스 - 가사 검색 [코딩테스트 연습 Lv4] 문제 : Programmers-가사검색 트라이(Trie) 개념으로 구현하면 된다. 내 경우 words에 들어있는 String으로 트라이 트리를 구성했는데, 각 길이마다 별도로 앞에서 부터 진행한 트리와 뒤에서 부터 진행한 트리를 둘 다 구성했다. 만약 '*' 같은것도 있으면 길이마다 구성한게 의미가 없었을테지만, 이 문제의 경우 queries의 길이가 고정되어 있으므로 길이마다 별도로 구성하는 것이 더 빠르게 연산할 수 있다. 또한 '?'가 접미사 혹은 접두사에 있으므로 둘 다 찾기 위해서는 앞에서 부터 구성한 트라이와 뒤에서 부터 구성한 트라이 둘 다 유지해야 한다. 접미사에 '?'가 있다면 뒤에서 부터 구성한 트라이 트리를 봐야 하고, 접두사에 있다면 앞에서 부터 구성한 트라이 트리를 봐야 한다. 추.. 2022. 4. 10.

티스토리툴바