공부의 발자취를 남기는 블로그

문제 분석: 해당 문제를 요약하자면, 1. 무작위로 나열된 카드가 존재함. 2. idx 0번부터 탐색 3. idx 0번의 카드를 꺼내, 그 카드의 숫자에 적힌 idx 상자를 뽑는다. 4. 3번의 행동을 반복하여 하나의 싸이클(순환)이 될때까지 수행한다. 우린 이걸 하나의 그룹으로 명한다. 5. 그렇게 만들어진 그룹중에서 제일 사이즈가큰 2개의 곱을 반환 문제를 제대로 이해가 완료했다면, 이제 푸는방법은 꽤나 간단하다. 이 로직을 구현하기위해선 3가지 1. 방문을 체크할 boolean[] 2. 모든 상자를 탐색할 for문 3. 싸이클(순환) 을 탐색할 while문을 준비한다. 싸이클 순환동안 매번 카드의 값이 바뀌기때문에 체크를해줄 current를 하나 생성해서 판별한다. 문제 풀이: 1 2 3 4 5 6..

문제분석 문제를 읽고 이해하는데도 꽤 난감한 문제다. 영재는 1,2,3,4,5... 와 같이 정규 컨테이너로 상자를 받는다. 하지만, 정규컨테이너로 받은 상자가, 주문순서와 다르다면, 보조 컨테이너에 넣어둔다. 보조컨테이너는 Stack의 형태를 띄운다. 보조 컨테이너와 ,정규컨테이너에서 받은 상자가, 주문순서와 다르다면 배송이 종료된다. 즉, 정리하자면 1. 정규컨테이너로 상자를받는다. 2. 만약 정규컨테이너가 주문순서와 다르다면, 보조컨테이너로 2-2. 만약 정규컨테이너가 주문순서라면, 출하한다. 여기서 While()로 한번 감싸준다. (왜냐하면 보조컨테이너에 여러개 연속으로 출하할수 있기때문) 3. 보조컨테이너가 주문순서와 같다면, 출하한다. 3-2.보조컨테이너가 주문순서와 다르다면, 종료시키고 .1..

문제분석 [7,4,1,1,9] 와같은 배열이 있다면, 중복이 없으며, 연속되는 수의 합의 가짓수를 구하는 문제다. 단, 이 문제는 원형의 수열이기때문에, 연속되는 수의 합의 가짓수가 훨씬 많아진다. EX) 첫번째 7과 마지막숫자 9를 선택해도 원형의 배열이니, 연속된숫자의 포함이된다. 따라서, 이 원형의 수열임을 가정하고 연속된 숫자를 어떻게 판별하는지가 이 문제의 Key Point다. 제일 간단한 방법은, 기존 배열을 2개 이어서 붙이는것이다. [7,4,1,1,9,7,4,1,1,9] 처럼 말이다. 이러면 원형의 수열까지 판별이 가능하다. 단, 이 방법은 매우 간단하지만 배열의 길이가 2배로 늘어나고, 탐색 범위가 매우증가하여, 비효율적이긴하다. import java.util.*; import java...

문제분석: 간단하게 요약하자면, 정현이가 원하는 10개의 상품이 10일 연속으로 할인을 하는 구간의 갯수를 구하는 문제다. 문제의 할인 상품의 배열의 길이는 10만개다. 요즘엔, 문제 풀기전부터 최적화, 효율성 좋은 코드를 뽑으려고 고민하다 오히려 푸는 시간이 더 오래걸리는것같다. 정작 이런 생각은 코딩테스트 가면 진짜 독이 될수 있다.. 첫번째 접근으로, Queue 를 사용해보고자했다. 그이유는, 매번 10개의 할인구간이 하루가 지날때마다 바뀌는데, 그 할인구간을 매번 바꾸는것보다, 가장 오래된 원소를 빼고, 가장 최근의 원소를 추가하는 (선입 선출 알고리즘을 사용하면) 최적화 방식을 생각했다. -> 오히려 더 복잡하고.. 복잡하다보니 코드 오류가 좀 많이떳다. 결국, 처음으로 돌아와 쉽게 짜기로 생각..

문제분석: 문제요약 : Que 2개에 주어진 배열을 합이 모두 같게 해주세요. 단, 최소 횟수로 반환해주세요. 이 문제를 정직하게 접근하면 , 원소를 뽑을때마다 1번큐 또는 2번큐에서 뽑을지 선택의 기로가 주어진다. 그래서 그 과정을 큐의길이만큼 (최대 30만) 반복하여 경우의수를 다 따지면 시간초과가 뜬다. 그렇다면 조금 다르게 접근을해보자. 두 큐에 있는 원소의 합이 같다 == 한쪽큐를 원소의합/2 만 만들면된다. 즉, 큐 1의 모든 원소를 전체합/2 를 만드는걸 목표로 두고, 큐2를 원소를 교체할수있는 교체박스라고 생각하고 짜보자. 예시를 들어보자, 만약 두 큐의 모든 원소의합이 30이면, 큐1의 원소합을 15만 맞추는걸 목표로만 하면된다. 만약 큐1의 원소합이 15보다 작으면 큐 2에서 원소를 뽑..

문제분석: 블록을 다음과 같은 규칙으로 칠한다. N*2 , N*3, ...일경우 블록을 칠한다. 이미 블록이 칠해져있다면 덮어서 칠한다. 여기서 칠해야하는 블록의 갯수가 무려 10억개, 각기다른 블록의색깔은 천만개다. 잘못 구현하면 바로 효율성에러가 뜨기좋은 거대한 숫자다. 문제의 요구사항은 begin~ end 사이에있는 블록의 리스트다. 그러면 필시 begin~end 부터 돌릴 반복문 1개가 존재해야한다. 그렇다면 begin~ end의 블록의 색깔은 어떻게 구할까? 이 블록의 색깔은 제일 작은 소수로 나눈 몫이 블록의 색깔이된다. 제일 작은 소수를 구하는법은 에라토네스의 체를 사용한다. 여기서 주의해야할점은 리턴하는 몫의 값이 천만을 넘어가선 안된다. 블록이 천만개만 존재하기때문에 그 이상의 블록의색깔..

문제분석: 길이가 N인 보드판에 N개의 퀸말을 서로 공격할수없는 상태로 만드는 형태의 갯수를 구하는문제다. 이 문제를 처음 접근할때 대부분의 사람들은 2차원 배열을 만들고 완전탐색을 진행할것이다. (본인도 2차원배열 만들어놓고 접근하니 뭔가 이상하게.. 산으로가는 느낌이 들엇다.) 이 방식으로 접근을 해서 푸는것도 하나의 방법이겟지만, 더 좋은 방법이 있다. 2차원배열을 1차원배열로 압축시켜버리는것이다. 어떻게 1차원 배열로 압축을 시킬까? 배열의 index를 행, 배열의 값을 열로 보는것이다. 예시로 들자면, 이 배열을 1차원으로 압축시키면 [1,3,0,2] 라는 값이 나온다. 이 압축시킨 배열로 백트래킹 기법을 사용하는것이다. 하지만, 퀸을 놓을수있는조건은 가로, 세로, 대각선이 겹치면 안된다. 여기..

문제분석 하노이의 탑 문제다. 하노이의 규칙은 한번쯤은 다 알것이다. 간단하게 하노이의 규칙의 갯수만 물어보면 매우 쉬운 문제가 되엇겠지만, 이동경로까지 전부 구해야한다. 즉, 하노이의 탑 알고리즘을 구해야한다. 하노이의 탑 알고리즘: 하노이의 탑은 N개의 원반을 끝지점에 옮기려면, 1.N-1개의 원반을 중간에 놓는다. 2. 가장큰 원반을 끝지점에 옮긴다. 3. 중간에 있는 N-1개의 원반을 끝지점에 옮긴다. 자 무엇이 보이는가 그렇다 DP(점화식)가 보인다. 즉 원반을 1-> 2-> 3 경로로 옮기려면, h(1,2,3,N) = h(1, 3, 2, n-1) {1번과정} + 1 {2번과정} + h(2,1,3) { 3번과정} 이 필요하다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

문제분석 문제는 아주 심플하다. 가로 2 세로 1인 블록을 3XN타일에 몇개까지 완벽하게 가득 넣을수 있는지 묻는다. 문제 읽자마자 떠오르는게 '규칙찾기' 이다. 혹여나, 규칙을 찾으신분은 별탈 없이 이문제는 프리패스지만.. 못찾는게 대부분이다. 규칙을 찾기위해선 먼저 증거들을 수집해 보자. n=0 , 1 n=2 , 3 n=4 , 11 -> 홀수를 빼먹엇는데 홀수의 경우수는 완벽하게 가득 넣을수없으니 0개다. 저 3가지의 경우를 보고 규칙이 보이는가? 대부분 못찾는다.. n=6일땐 경우의수가 41이나온다. n=6인 예시도 있었다면 규칙을 쉽게찾앗겟지만 주지않는다. 만약 실제 코딩테스트문제라면 빠른 구글링을하자.,, 괜히 규칙찾는다고 시간낭비다. 필자도 고민해보다 구글링을 했는데, 규칙은 f(n)= f(n..

문제분석 문제 목표: 1과 0으로 구성된 문자열을 조건에맞게 X번 적용할때 0이 지워진 갯수를 Y라할때 X 와 Y를 구하자. 조건: 1. 1과 0으로 된 문자열에서 0을 모두제거 2.제거된 문자열의 길이를 N 이라할때, N을 2진법으로 다시 표현 3. 윗 과정을 숫자 1이될때까지 반복 매우 쉬운문제다. 사고력없이 문제가 시키는대로만 하면 풀리는 문제다. 우선, 조건 1대로 문자열에서 0을 제거하는건 자바에선 replace("0" , "")를 사용한다. 그후, 제거된 문자열의 길이를 잰뒤, 2진법으로 바꾸는 로직을 시행한다. ->여기서 동시에 제거된 0의갯수를 세준다. ->또한, 조건을 적용할 카운트도 세준다. 이 과정을 1이될때까지 (While)반복시킨다. 그리고 마지막에 세준 X, Y값을 반환하면끝이다..