본문 바로가기

전체 글1068

백준 1187 자바, C++ - 숫자 놀이 (boj 1187 java c++) 문제 : boj1187 감을 제대로 못잡고 있었는데, '수학귀신' 책을 추천해줬던 수학 잘하는 선배같은 동생의 도움으로 풀 수 있었다. 1. 귀납법(귀납 추론)으로 풀 수 있는 문제이다. 1.1 k=1 k를 1부터 증가시켜 나가면서 생각해보자. 우선 k=1일 때, N은 2가 된다. 이 때 2*2-1 = 3개 중 합이 2로 나누어 떨어지는 2개를 뽑는 문제가 된다. 그럼 2*2-1개의 수가 어떻게 나와야 2로 나눌 수 있는 2개를 뽑을 수 있을까? 이 때 모든 경우를 나타내보면 다음과 같다. A. 3개의 수가 모두 짝수일 경우 -> 아무거나 2개 뽑으면 된다. B. 3개의 수가 모두 홀수일 경우 -> 아무거나 2개 뽑으면 된다. C. 3개의 수가 짝수2개, 홀수1개인 경우 -> 짝수 2개를 뽑으면 된다. .. 2022. 4. 1.
백준 5419 자바 - 북서풍 (boj 5419 java) 문제 : boj5419 1. 일단 모든 쌍을 직접 확인해보자! (brute force) n개의 정점 모두에 대해 모든 쌍을 확인하면서 조건을 만족하는지 확인해보면 된다. 이 경우 코드는 아래와 같이 될 것이다. 물론 이대론 O(N^2)이 되므로 시간 내에 통과할 수 없다! 어쨌든 어떠한 점이 자신보다 x가 작거나 같고, y가 크거나 같은지 확인하면 될 것임을 알 수 있다. ArrayList arr = new ArrayList(); void add(Island island) { arr.add(island); } long getAnswer() { long cnt = 0; for (int i = 0; i < arr.size(); i++) { for (int j = i+1; j < arr.size(); j++).. 2022. 3. 31.
백준 1918 자바 - 후위 표기식 (boj 1918 java) 문제 : boj1918 전공자라면 과제로 한 번씩 해봤을 그 녀석이다. 후위 표기식으로 변환하는건 스택을 활용하면 된다. 실제 계산을 할 필요가 없고, 단순히 중위 표기식을 후위 표기식으로 바꾸기면 하면 되므로 실제 연산 결과를 유지하지 않아도 되서 더 쉽게 짤 수 있다(원래대로라면 'A'~'Z'도 스택에 넣어서 연산자에 따라 실제 연산이 진행되야 하지만, 이 문제의 경우 단순히 화면상에 출력만 하면 되므로). 이 문제와는 관계없지만 후위 표기식을 활용해 실제 계산해서 공학 계산기처럼 동작하는 자바 코드는 여기(깃헙)에 있다(오래전에 짠거라 좀 코드가 안이쁘긴하다). 다음과 같이 동작한다. INPUT : 23.3 * (sin3+ 2.5)/ 43.2 OUTPUT : 1.3766071245476987 INP.. 2022. 3. 31.
백준 2170 자바 - 선 긋기 (boj 2170 java) 문제 : boj2170 당연히 전체 위치를 보게되면 -10억부터 +10억까지 봐야하므로 시간초과가 뜬다. 최대 100만개인 N을 기준으로 동작할 방법을 찾아야 한다. 문제에서 제시된 '예제 입력 1'은 이미 그렇게 정렬된 데이터긴 하지만, N개를 전부 x를 기준으로 오름차순으로 정렬했다고 생각하고 어떻게 풀지 한번 생각해보자. 4 1 3 2 5 3 5 6 7 그렇다면 위와 같이 x값 기준 오름차순으로 차례대로 확인할 경우(x값이 동일할 경우 y값 순서는 상관 없음. 그나마 내림차순으로 하면 아주 약간의 대입연산 정도는 줄여볼 수 있는데 의미 없음), 이전 y 값보다 현재의 x값이 작거나 같다면 이어진 항목으로 생각해볼 수 있다. 1-3을 본 후, 2-5를 보자. 현재 보고 있는 x인 2는 이전의 y값인 .. 2022. 3. 30.
백준 16496 자바 - 큰 수 만들기 (boj 16496 java) 문제 : boj16496 당연한거지만 앞에 올수록 더 전체값이 커질만한 순서대로 정렬한 후, 출력해주면 되는 문제이다. 그 정렬 규칙만 잘 정하면 된다. 케이스1 - 예를들어 9와 89999999가 있다. 직관적으로 자리수와 정렬 규칙은 관계가 없음을 알 수 있다. 둘 중 작은 길이의 숫자까지 비교해서 그 중 다른 숫자가 있다면 쉽게 규칙을 정할 수 있다. 이 경우 9를 먼저 놓는것이 당연히 이득이다. 케이스2 - 그럼 98와 98999이 있다면 어떨까? 직관적으로 98999를 먼저 두는 것이 이득임을 알 수 있다. 이 경우는 '케이스1'로는 판단할 수 없는 경우이다. 그렇다면 자리수가 다르면서, 둘 중 작은 자리수까지 비교해도 비교가 안되는 경우를 어떻게 판단할지가 관건임을 알 수 있다. 내 경우 규칙.. 2022. 3. 30.
백준 24927 자바 - Is It Even? (boj 24927 java) 문제 : boj24927 ※ 2K로 나누어 떨어지는지 구하면 안되고, 2^K(2의 K승)로 나누어 떨어지는지 구해야 한다. 문제에 오류가 있다. 이걸 직접 계산해서 실제로 나누어 보려고 한다면 무려 90만1자리의 엄청난 수가 나온다 ㅋㅋ. 그러니 생각을 좀 바꿔보자. 어차피 2^K으로 나누어 떨어지는지만 확인하면 되므로, 단순히 2^K 성분만 확인하면 된다. 다른 소수는 생각할 것도 없다! 무슨말이냐면, 소인수 분해를 생각해보자. 위와 같이 어떠한 수를 소인수분해 했을 때 2가 몇개 있는지만 알면 된다. 240의 경우 2가 4개 존재한다. 3이랑 5는 상관이 없다. 2가 4개인 수를 나눌 수 있는 2^K는 K개 4이하일 때 가능하다. 즉, 주어진 x_i을 2로 나누어지지 않을 때 까지 계속 나누면서 2로.. 2022. 3. 30.
백준 2713 자바 - 규현이의 사랑을 담은 문자메시지 (boj 2713 java) 문제 : boj2713 실버치고 구현이 상당히 빡쌘 문제이다. 아마 곧 골드까지 올라갈 것 같다. 이정도면 아무리 별다른 알고리즘 필요없는 구현문제라도 골드5정도가 맞다. 내 경우엔 최대한 원툴(?)로 구현을 하고 싶었다. 따라서 약간의 아이디어를 써서 좀 쉽게 진행했다. 다음의 입력을 확인해보자. 1 4 4 ACM 4x4일 경우, 그보다 2칸씩 크게 미리 배열을 만든다. 즉 6x6으로 만들고, 외곽을 1칸씩 띄운 상태로 중앙의 4x4에 '-1'과 같이 나올 수 없는 수를 쓴다. 해당 위치에 들어가야하는데 아직 값이 안들어갔다는 의미로 사용했다. 그리고 (1,0) 지점에서 시작하고, 처음 진행하는 방향은 항상 우측방향이다. 그리고 방향은 우측:0, 아래:1, 좌측:2, 위:3 으로 정한다. 소용돌이가 진.. 2022. 3. 29.
백준 14405 자바, 파이썬 - 피카츄 (boj 14405 java, python) 문제 : boj14405 1. 직접 찾아보자! 우선 정규식을 사용하지 않고 직접 찾는걸 확인해보자. 간단히 생각해서, 문자열에서 "pi", "ka", "chu"를 모두 나올 수 없는 문자로 변경해보자! 예를들어 "piakapichu"를 확인해보자. 이제 변경되지 못하고 남는 'a'가 보인다. 따라서 'NO'를 출력하면 된다. '&'만 있었다면 'YES'를 출력하면 된다. 그냥 삭제하지 않고 저렇게 자리를 남겨두는 이유는 'cpihu' 와 같은 경우 때문이다. 이 때 위 처럼 문자를 남긴다면 'c&hu'가 되어 chu를 변경할 수 없지만, 그냥 삭제하면 'chu'가 되므로 변경될 수 있다. 즉 올바른 답을 찾을 수 없다. 위와 같은 방식으로 짠 코드는 '코드1'에서 볼 수 있다. 2. 정규식을 사용해 찾아.. 2022. 3. 29.
백준 5698 자바 - Tautogram (boj 5698 java) 문제 : boj5698 원랜 브론즈는 해설을 작성하지 않으려 했으나, 블로그 유입인원 늘릴려면 아무래도 골플 문제보단 브론즈 문제가 더 이득인 것 같다. 문자열을 잘라내는 방법만 안다면 풀 수 있다. 자바의 경우 String에 대한 split함수 또는 StringTokenizer를 사용해서 자를 수 있는데, 결론적으로 후자가 더 빠르다. 이제 자를수만 있다면, 모든 잘라진 토큰에 대해 첫 character만 확인하면 된다. String에 대해 charAt(0)을 하면 첫 번째 character가 나온다. 이 때 소문자 혹은 대문자로 맞춰서 확인하는 것이 좋을 것이다. 그럼 해당 String에 대해 toLowerCase 후에 charAt(0) 으로 보면 바로 소문자가 나온다. 하지만 당연히 더 느리다. 따.. 2022. 3. 28.
백준 9342 자바 - 염색체 (boj 9342 java) 문제 : boj9342 파싱해서 하려다가, 너무 대놓고 정규 표현식으로 풀어! 라고 하는 문제라서 정규 표현식으로 풀어봤다. ^ : 정규표현식 시작 $ : 정규표현식 끝 [A-F] : A,B,C,D,E,F ? : 0번 또는 1번 + : 그 전 문자가 1개 이상 이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static final String REGEX = "^[A-F]?A+F+C+[A-F]?$"; private void solution() throws Exception { BufferedReader br = new BufferedReader(new Input.. 2022. 3. 28.

티스토리툴바