본문 바로가기

분류 전체보기1056

백준 9242 자바 - 폭탄 해체 (BOJ 9242 JAVA) 문제 : boj9242 입력받은 문자열을 숫자로 변경만 할 수 있다면 6의 배수인지는 n%6==0 과 같이 쉽게 알 수 있다. 또한 코드는 8자리 이하라고 했으므로 최대 10^8-1의 값이므로 정수로 표현하는데에도 문제가 없다. 따라서 주어진 문자가 잘못된 문자인지 여부를 알 수 있고, 주어진 문자가 숫자로 무엇과 대응되는지만 알면 풀 수 있다. 그럼 주어진 문자를 주어진 기준문자(아래와 같은)와 비교만 잘 하면 된다. 이 때 주의점은 각 문자의 특징을 잡아서, 예를들어 마지막 열에 5개의 별표가 있다면 1 혹은 7일테니 첫번째 열에 *이 있다면 7, 아니면 1 이런방식은 틀린 입력값을 제대로 잡아낼 수 없다. 따라서 문자의 모든 위치(5x3)을 모두 비교하는게 맞다. 내 경우엔 우선 기준 데이터를 파싱.. 2022. 3. 21.
백준 2191 자바 - 들쥐의 탈출 (BOJ 2191 JAVA) 문제 : boj2191 이 문제에서 뭐' 속도가 빠른 쥐가 더 멀리 가야만한다'와 같은 가중치적인 부분은 들어있지 않다. N개의 정점을 M개의 정점에 최대한 많이 매칭 시키기만 하면 되는 문제이다. 1. 그래프 형태로 전처리 문제에서 제시된 값들만 가지고는 뭔가 풀어보기가 힘들다. 따라서 우선 그래프 형태로 변경해보자. 각 쥐의 현재 x, y 좌표와 각 땅굴의 x, y 좌표를 알고 있다. a번째 쥐의 좌표를 Xa, Ya라 하고, b번째 땅굴의 좌표를 Xb, Yb라 하겠다. 그럼 쥐가 땅굴로 달리기 전 a번째 쥐와 b번째 땅굴의 거리는 다음과 같다. 그리고 쥐는 초당 V만큼 움직이고, S초까지 들어가야 하므로 다음 식이 만족된다면 a번째 쥐에서 b번째 땅굴로 안전하게 들어갈 수 있다. ('단, 들쥐가 도착.. 2022. 3. 20.
백준 9997 자바 - 폰트 (BOJ 9997 JAVA) 문제 : boj9997 1,2,3에 걸쳐서 점점 효율성이 좋은 풀이를 설명할 겁니다. 그러니 최종적으로는 '3'만 보셔도 되긴합니다. 왜 그렇게 설명하냐면 제가 그렇게 풀었기 때문입니다 ㅋㅋㅋ 시간 제한 딱 맞춰서 푸는건(1초제한인데 백준에서 자바로 제출할 시 '원래시간*2+1'초 이므로 자바로는 3초제한 이었어요.) 뭔가 기분나빠서 줄이다보니 줄여지네요. 1. 우선 빠듯하게 가능한 풀이 우선 모든 경우를 살펴보는게 가능할지 생각해보면, O(2^25*100*26)가 필요하다(2는 해당 문자를 사용하거나, 안하거나이고 25는 N의 최대수치, 100은 단어 길이의 최대수치, 26은 a~z 모든 문자가 포함되었는지 확인). 상당히 빠듯하긴 하지만, 어찌보면 할만해 보이므로 일단 해봤다. 이 때 단어 길이는 1.. 2022. 3. 20.
백준 3164 자바 - 패턴 (BOJ 3164 JAVA) 문제 : boj3164 우선 뭐 배열에 직접 그린 후에 직접 세는 방식은 O(X*Y) = O(10^12) 이므로 불가하다. 애초에 메모리도 엄청 많이 들 것이다. X와 Y가 최대 10^6 이므로 시간내에 풀기 위해서는 O(N)이나 O(NlogN) 급의 풀이가 필요하다. 혹시 어떻게 푸는지 감이 안왔다면 아래의 그림을 보면 바로 아! 라고 외칠 것이다. 그래프를 2개로 나눠서 보면 쉽게 풀이법을 생각해낼 수 있다. 문제에서 제시된 그래프 그대로 풀이를 찾기엔 좀 난해할 수 있지만, 아래와 같이 가로 성분과 세로 성분을 나눠서 생각해보면(세로 성분의 맨 위는 가로성분에 이미 포함된다.) 그냥 범위내에 포함되는 매번 +2씩 증가하는 기둥의 길이를 구하는 문제가 된다. 가로 기둥 최대 50만개, 세로 기둥 최대.. 2022. 3. 19.
백준 17162 자바 - 가희의 수열놀이 (Small) (BOJ 17162 JAVA) 문제 : boj17162 mod가 최대 10^2라서 뭐 복잡한 알고리즘 필요없이 풀 수 있다. 결국 나누었을 때 0, ..., mod-1인 수가 어느 idx 위치에 있냐가 중요하다. 이걸 빨리 알 수 있으면 되는건데, mod가 10^2이니깐 대충 O(Q * mod) 정도의 시간복잡도만 가져도 풀 수 있다. 그럼 해볼만한게 많이 있다. 내 경우엔 어차피 맨 뒤에서만 수가 추가되고 빠지니 스택을 사용했다. 그리고 mod개 만큼의 스택을 마련했다. 스택배열을 arr이라고 하고, 현재 넣을 위치를 idx라고 하겠다. 그럼 각 쿼리에 대해 다음과 같이 대응할 수 있다. --- [ 쿼리 : 1 num ] arr[num % mod]에 num을 추가하고 idx++ -> O(1) [ 쿼리 : 2 ] 최대 10^2개인 a.. 2022. 3. 18.
백준 2602 자바 - 돌다리 건너기 (BOJ 2602 JAVA) 문제 : boj2602 이게 돌다리 2개를 번갈아 건너는 부분을 어떻게 처리할지 감이 잘 안올 수 있어서 그렇지, 그 부분 때고 생각하면 생각보다 어렵지 않다. 1. 그러니 우선 돌다리가 한 줄만 있다고 치고 생각해보자. 이 경우에도 모든 경우를 보기에는 당연히 무리가 있다. 대강 100! (팩토리얼) 정도 나올테니 다 볼순 없다. 브루트포스로 하진 못하겠고, 그럼 돌다리 한 줄만 우선 본다고 했으니 "RRGGSR"에서 "RGS"를 건너면서 지나가는 경우를 생각해보자. 이런건 DP를 사용해 구하면 효율 좋게 구할 수 있다. dp[a][b]를 "RGS"에서 a 인덱스 까지를 표현하는 가지수, b는 "RRGGSR"의 인덱스 라고 정의해보자. 이 경우 다음과 같이 그려볼 수 있다. 최종적으로 가장 우측 아래에.. 2022. 3. 18.
백준 11637 자바 - 인기 투표 (BOJ 11637 JAVA) 문제 : boj11637 우선 직관적으로 생각하기엔 아주 간단하다. 각 테스트 케이스에 대해 n명의 득표 수 합계(이하 sum)를 구하고, 그 n명 중 가장 큰 값(이하 max)을 기준으로 다음과 같이 나뉜다. 1. max값을 가졌던 인원이 2명 이상인 경우 : no winner 2. sum/2+1 0) { int n = nextInt(); int max = 0; int maxIdx = -1; int sum = 0; int idx = 0; boolean chk = true; while (idx++ 2022. 3. 17.
백준 5568 자바 - 카드 놓기 (BOJ 5568 JAVA) 문제 : boj5568 우선 항상 문제를 풀 때, 그냥 무지성으로 모든 경우를 봐도 주어진 시간, 메모리 내에 가능한지부터 확인하는 습관을 들이는게 좋다. 이 문제의 경우엔 최대 10개 중 최대 4장을 선택하면 되므로, 최대 10C4번만 보면 된다. 따라서 그냥 모든 경우를 보면 된다! -> 모든 경우를 확인하려면 k번의 반복문이 필요하다. 이렇게 반복문의 개수가 고정되지 않을 때는 재귀로 짜면 매우 편하다. 재귀를 쓰기 싫다면 스택을 쓰면 재귀로 짠 것과 동일하게 짤 수 있다. 그럼 '만들 수 있는 정수'의 종류는 어떻게 알 수 있을까? 마찬가지로 제한 조건을 확인해보면서 생각해보면 된다. 우선 1부터 99까지의 정수이므로 0이 없어서, 숫자 앞에 0이 오는 경우는 무시해도 됨을 알 수 있다. 그리고 .. 2022. 3. 16.
백준 18258 자바 - 큐 2 (BOJ 18258 JAVA) 문제 : boj18258 문제에 제시된 대로 구현만 잘 하면 되는 문제이다. 큐를 직접 구현해봐도 되고, 자바 혹은 다른 언어에서 제공하는 기본 큐를 사용해서 짜도 된다. '만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.' 와 같은 세세한 조건들만 잘 처리해주면 쉽게 통과할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.PriorityQueue; .. 2022. 3. 15.
읽은 책 소감 - React.js, 스프링 부트, AWS로 배우는 웹 개발 101 읽은 목적은 React를 배우기 위해서였다. 기존 스프링 부트와 함께 jsp를 사용해 js 위주로 짜는 프론트는 사실 좀.. 안멋있다. 개인 취향이다ㅋㅋ. 별로 상세하게 파고들어서 알고싶은 마음이 들지 않았다. 그래서 유명한 리액트는 내 입맛에 좀 맞을까 싶어서 한번 배워보고 싶었다. 한글로 된 리액트 책 중에 괜찮아 보이는게 별로 없었다. 그렇다고 원서를 읽자니 초반에야 열심히 읽겠지만, 이후 열정과 집중력이 좀 떨어졌을 때 끝까지 읽을 자신이 없었다. 그래서 어쨌든 한글로 된걸 선택하기로 했다. 추가로 내 입장에서 백엔드는 node.js로 하는 것 보다는 스프링 위주가 내겐 여러모로 더 유리하다고(사실 취향임ㅋ) 판단했다. 따라서 리액트도 배워보면서, 스프링 + 리액트로 Decoupled Archit.. 2022. 3. 14.

티스토리툴바