CodeReview (21) 썸네일형 리스트형 21년 10월 2주차 PS 일지 CP는 안한지 꽤 됐지만, PS는 꾸준히 하고 있는데 이렇게 포스팅이 늦은 이유는.... 게을러서입니다ㅋㅋㅋ 백준 10160 암호 dp(i) : 1~i까지 처리 했을때, 가능한 안전한 암호의 갯수 위와 같이 디피 배열을 정의합니다 그렇다면 다음과 같은 점화식을 도출 할 수 있습니다 $dp_{i} = K*dp_{i-1} - 2*dp_{i-5} + dp_{i-7}$ i까지 가능한 암호의 갯수는 i-1개까지의 가능한 갯수에 K를 곱해준 경우에서 뒤의 5글자가 안전하지 않은 패턴인 경우를 빼주면 구할 수 있습니다 다만 여기서 디피에서 관리하는 값은 안전한 암호의 갯수라는 점에서 AB/ABCBC 이런 경우는 없기 때문에 다시 dp(i-7)을 더해주어야 합니다(AB/ABCBC 이런 패턴은 안전한 암호만을 저장하기 .. 알고리즘 문제풀이 복습 1 12015 가장 긴 증가하는 부분 수열2 부분 수열1 문제는 DP로 풀 수 있습니다 하지만 같은 풀이를 여기에 적용하면 수열의 크기가 100만이라 TLE를 받습니다 따라서 dp배열을 보다 빠른 방법으로 채워주어야 합니다 이는 이분 탐색을 통해 해결 할 수 있습니다 수열을 s라고 할때, $dp_{i}$를 $s_{i}$를 끝으로 하는 증가하는 부분수열의 길이라고 정의합니다 그리고 $X_{j}$는 $dp_{i}=j, 1\leq i\leq N$를 만족하는 $s_{i}$ 중 min값으로 정의합니다 이후 dp값을 1부터 N까지 보면서 X의 값 중 이때의 수열 s의 값보다 작은 값을 이분탐색으로 찾아줍니다 이렇게 찾은 X의 인덱스로 dp값을 갱신해주고, 갱신한 dp값으로 X의 다음 인덱스 값을 다시 갱신해주면 문제를.. BOJ 문제풀이 W32 과외 마지막 주차 문제 풀이입니다 18886 new year and permutation len : r - l이라고 할때, $\sum\limits_{len}\left ( n-len+1 \right ) \times len! \times \left ( n-len+1 \right )!$, len = 1 to N 이를 구현해주면 문제를 해결 할 수 있습니다 다만 O(N) 안에 이를 구해야 함으로 팩토리얼 연산을 미리 전처리 해야합니다 또 이렇게 3가지를 곱할 때 m이 최대 10^9임으로 10^9를 3번 곱해주면 overflow가 발생합니다 3개를 동시에 곱해주지 말고 이 역시 나눠서 구해주면 해결 할 수 있습니다 11758 CCW CCW 기본 문제입니다 신발끈 공식을 이용해 그대로 구현하면 됩니다 10840 구.. BOJ 문제풀이 (W29~30) 요즘 ps에 할애하는 시간이 눈에 띄게 적습니다. 핑계아닌 핑계를 대보자면 인턴 시험, 면접이 어마어마하게 많고(공채보다 더 많습니다) 프로젝트도 마무리 지었어야 해서 바쁘게 지나갔네요(덤으로 발바닥에 구멍이나서 병원을...) 아무튼 시작하겠습니다(27주차도 안까먹고 올리겠습니다 문제는 하나빼고 다 풀었습니다) 14739 faster sorting //minrun이 주어졌을때 정렬은 $Nlog(N)$안에 가능합니다. 이를 증명하는 일이 문제풀이의 핵심인데 다음에 추가하겠습니다. 19587 객실배치 D[n, i] : N층의 i에 배칠 할 수 있는 경우의 수 위와 같이 배열을 정의 해주면 아래와 같은 점화식을 만들 수 있습니다. $$\begin{pmatrix} D_{N+1, 0}\\ D_{N+1, 1}\\ .. 2020 카카오 인턴 기출 풀이 오늘 다 풀어볼줄 알았는데 5문제중에 3문제만 풀었네요 내일 마저 풀겠습니다. 1. 키패드 누르기 키패드를 좌표 평면으로 생각해보면 쉽게 해결 할 수 있습니다. 다만 왼손, 오른손, 눌러야할 버튼 이 3가지를 좌표 평면에 옮겨야해서 별것도 없는 문제인데 길이가 90줄 가까이 됩니다. 구현의 팁은 거리를 구할때 굳이 루트 연산을 하지 않는 부분입니다. 2. 수식 최대화 제가 취약한 문제 유형(구현, 문자열) 중 하나입니다. 문자열 문제라 바로 파이썬으로 바꿔 풀었습니다. 문제에서 친절하게도 경우의 수가 3!뿐이라고 알려줍니다. 6가지 각각의 경우에 대해서 계산을 해주면 됩니다. 다만 내용에 비해 역시 구현해야할 코드가 많습니다. 나름 줄인건데 70줄이네요 계산하는 부분을 따로 함수로 작성하고 6가지 경우에.. BOJ 문제풀이 (W27) 무려 2주만의 PS입니다!! 그간 코딩테스트와 중간고사가 겹쳐서 못하고 있었는데 시간 비면 짬짬이 해야겠습니다. 4학년 올라오니까 거의 매주 시험입니다 😭😭😭 16325 king's color 트리 dp 문제입니다. 간선이 주어지는데 문제 풀이와는 전혀 관계없습니다. 어떤 정점이든간에 2가지 경우만 생각해주면 됩니다. 어떤 정점 u를 색칠했을때, 그 색이 다른 정점을 칠할때도 사용되는 경우와 그렇지 않은 경우가 있습니다. 이때 F(i, j) 를 i개의 정점을 j개 이하의 색으로 칠하는 경우의 수라고 정의하면 후자의 경우 $K*F(N-1, K-1)$ 입니다. 정점 u를 칠하는 경우 k개, 나머지 정점들을 k-1개의 색으로 칠해주는 경우 전자의 경우 $(K-1)*F(N-1, K)$입니다. 정점 u를 부모와 .. BOJ 문제풀이(W26) 15565 귀여운 라이온 인형의 갯수를 누적합으로 구해주고, 투포인터를 이용하여 인형이 K개 이상인 가장 짧은 구간을 찾아주면 됩니다. 이때 투포인터는 end를 하나씩 늘려 가면서 각각의 end를 끝으로 하는 인형이 K개 이상인 가장 짧은 구간을 찾을 수 있습니다. for (int e = 1; e =k) s++; else break; } if (sum[e] - sum[s-1]>=k) len = min(len, e-s+1); } 찾아준 구간이 정말 K개 이상인 구간인지 보장못함으로 마지막에 값을 갱신할때는 이를 체크해주어야 합니다. 다른 풀이로는 구간의 인덱스를 활용하는 풀이가 있습니다.(선생님이 알려주신 풀이입니다) 예전에 풀었던 17844 복붙하기 문제에서 비슷하게 사용했던 테크닉같은데 구현이 아주 짧.. BOJ 문제풀이(W24) 2098 외판원 순회 2617 구슬찾기 구슬의 대소관계를 이용하여 그래프를 만들고, 이를 탐색하여 문제를 해결했습니다. 1번 구슬이 2번 구슬보다 무겁다면 1에서 2로 가는 간선을 그어주고 각각의 구슬에 대해 dfs를 돌려 그 구슬보다 무거운 구슬의 숫자를 셌습니다. 9009 피보나치 어떤 정수에서 그 정수보다 작은 피보나치 수열 중 가장 큰 피보나치수를 하나씩 빼주면서 문제를 해결했습니다. 5582 공통 부분 문자열 dp[i][j] := s[i]=t[j]이면서 이를 끝으로 하는 최대 공통 부분 문자열의 길이 이렇게 배열을 정의하면 쉽게 해결 할 수 있습니다. 주어진 두 문자열의 길이가 4,000이라 시간안에 풀 수 있습니다. 9251 LCS 최장 공통 부분 수열을 찾아주는 문제입니다. 수열을 찾아주는 .. BOJ 문제풀이(W23) 7578 공장 구간합을 구하는 문제로 치환되는 순간 매우 편해집니다. 포인트는 문제를 구간합을 구하는 문제로 치환하기와 쿼리에서 요구하는 인덱스를 구하는 부분입니다. 기계가 교차하는 조건을 생각해보면 첫번째 포인트를 잡을 수 있습니다. $i b_{a_{j}}$이면 교차합니다. 그러니까 j를 1부터 n까지 돌면서 j~N까지 구간의 합을 구해주면 문제를 해결 할 수 있습니다. 이때 배열을 전부 0으로 초기화시켜주고 j를 하나씩 돌면서 기계를 연결시키면서 배열의 해당 인덱스를 1로 만들어줍니다. 이 부분에서 배열 A의 값이 배열 B의 몇번째 인덱스와 일치하는지를 찾아주는것은 이분탐색을 통해 구현했습니다. 2096 내려가기 메모리 제한이 4MB입니다. N이 10만이라 입력이 30만개인데 int형이 8byte이니.. BOJ 문제풀이 (W22) 10806 부분합 투포인터를 사용하여 답을 갱신해주면 됩니다. 다만 이 문제에서 중요한 점은 후에 따로 글로도 쓸 주제이지만 loop invariant입니다. 각각의 원소에 대해서 그 원소를 끝으로 할 때, 합이 s이상이 되게하는 가장 인덱스가 큰 시작지점을 찾아 주는 반복문을 하나 넣어 loop invariant를 설정하면 됩니다. while (start+1=s) { sum-=arr[start]; start++; } 1992 쿼드 트리 대표적인 분할정복 문제입니다. 주어진 배열을 4등분하여 분할정복을 돌아주면 됩니다. 인덱스 슬라이싱 할 때 거리를 따로 구해서 슬라이싱해야하는 점이 구현의 팁입니다. 17626 four squares 1개일때, 2개일때, 3개일때 까지는 그냥 반복문으로 처리해주면 됩니다.. 이전 1 2 3 다음