프로그래민👨‍💻

2018 카카오 블라인드 채용 문제이다. 이문제는 문자열 찾기문제로 KMP를 사용하여 풀었다. 하지만 전처리를 해줘야할것이 많았다. 나는 일단 #을 처리하리 위해 translate라는 함수를 만들어 #이 붙은 문자들을 새로운 문자로 아예바꾸어서 문제를 해결하였다. 꼼꼼한 전처리와 KMP를 다룰 줄 알면 쉬운 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 ..

이문제는 문자열 패턴찾기 문제이다. 단순히 일반적으로 찾으면 시간초과가 생겨서 풀수 없는 문제이다. 그렇기에 대표적인 문자열 알고리즘의 대표적인 KMP를 사용하였다. KMP의 알고리즘의 간단한 원리는 일단 패턴문자열에 대해 해당 문자열의 위치마다에서 접두사와 접미사가 최대로 같아지는 것을 카운팅해주는 배열을 만든다음, 그 배열을 이용하여 접두사와 접미사를 확인해가며 일정간격을 건너뛰어 시간복잡도가 거의 O(n)에 가깝도록 해결하는 방식이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53..

2020 카카오 문제였다. 이 문제는 옳은 괄호를 찾는 문제인데, 재귀를 이용해서 푸는 문제였다. 다만 이 문제에서는 재귀의 모든 과정을 문제에서 제공해주었고, 단순 구현만 하면 되는 문제였다. 따라서 문제의 제공되어있는데로 그대로 재귀를 구현하여 쉽게 풀 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 8..

다이나믹 프로그래밍 문제이다. 1차원 DP문제로써 점화식을 세우는데 오래걸리진 않았다. 각 k 에선 k-동전가치 만큼에서 경우들을 더해주면 구할 수 있으므로 다음과 같은 점화식을 구했다. for 1부터 k까지 for 모든 동전가치 dp[k] = dp[k] + dp[k-동전가치] 하지만 이문제에선 하나의 조건이 더 있는데 바로 동전의 구성이 같다면 카운팅을 안해주는 것이었다. 바로 중복의 경우르를 제거해주는 것인데, 이것을 어떻게 구현할지 한참을 고민하였다. 답은 바로 1부터 k까지가 아니라 모든 동전에 대해서 먼저 처리를 해주는 것이었다. for 모든 동전가치 for 1부터 k까지 dp[k] = dp[k] + dp[k-동전가치] 다음과 같은 점화식으로 풀 수 있는 문제였다. 1 2 3 4 5 6 7 8 ..

2020 카카오 인턴 4번 문제였다. 맨처음 봤을땐 단순하게 백트래킹+가지치기로 접근하였다. 하지만 역시 N이 최대 25였기에 시간초과가 발생하였다. 그래서 다르게 접근을 해보았다. visit배열을 int로 정의하여서 각 지점마다 최소가 되는 값을 저장해주었고, 갱신이 가능할때만 그 지점으로 갈 수 있도록 DFS를 구현하여 풀었다. 일종의 DP 개념으로 접근하여 DFS를 해결하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..

2020 카카오 인턴 3번 문제였다. 이 문제를 맨처음 봤을 때 배열 크기 N의 범위때문에 어떻게 접근할까 고민을 하였다. 최대 100000이기 때문에 2중 포문만 되어도 시간초과가 발생하기에 이분탐색을 떠올렸다. 이분 탐색을 이용하여 문제를 풀었을 때 기본 테스트 케이스는 통과하였지만 효율성검증에 있어 탈락을 하였다. 그래서 이분 탐색 후 checking하는 과정에서 배열에서의 고정길이 탐색을 효율적으로 할 수 있는 슬라이딩 윈도우 알고리즘을 사용하였다. 이 문제는 배열에서의 조건을 만족하는 최소길이를 찾는 문제이므로 크게 두가지 방법을 사용할 수 있다. 첫째로, 길이를 이분탐색으로 구하고, 그 고정길이를 이용하여 슬라이딩 윈도우를 사용하는 방법이 있다. 두번째로, 고정길이의 탐색이 아닌 가변길이 탐색..

2020 카카오 인턴 2번 문제였다. 수식의 연산자에 대해 우선순위를 부여하고 그순간에서의 최대값을 구하는 문제였다. 주어진 연산자가 3개였으므로 순열을 이용하여 모든 경우의 수를 보았다. 그리고 수식의 전부를 token화 시켜서 List의 형태로 저장하였고, 계산을 할땐 list에서 remove해주는 방식으로 해주었다. 여기서 주의할점은 for문안에서 List의 사이즈를 건들수 있는 remove연산을 해주었기 때문에 index값을 조정해주는 것이 꼭필요했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 ..

위상정렬을 이용하여 풀은 문제였다. 문제를 맨처음 파악했을때, 일의 우선순위가 있고, 일끼리 싸이클을 만들지 않는 DAG임을 보장받을 수 있는 조건이라 위상정렬을 사용하여 문제를 풀었다. 이 문제에선 우선순위가 높은것 -> 우선순위가 낮은것 으로 간선을 연결해 주었고, indegree배열과 queue를 이용하여 위상정렬을 구현하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 ..

그래프의 사이클을 찾는 문제이다. DFS를 이용하여 그래프의 사이클을 찾아서 pq에 저장하였다. DFS를 이용하여 그래프의 cycle을 찾을때는 visit 배열 뿐만 아니라 finished 배열을 하나 더 사용해준다. finished를 이용하여 이미 완전히 탐색이 끝났는지를 확인해주었다. DFS를 도는중 만일 visit가 true이지만 finished가 false 인곳을 찾는다면 cycle을 찾은 조건을 만족한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58..

DP문제이다. 코딩테스트에 나왔던 문제이다. 그 당시 효율성을 해결하지 못하여 풀지 못했어서 다시 풀어보았다. 맨처음 문제를 보고 자연스럽게 바텀업이 생각났고 DP로 접근하게 되었다. 다음과 같은 점화식으로 DP를 풀었다. DP[i] = min(DP[i], DP[i-현재 코인의 값] + 1) 과 같은 점화식을 얻을 수 있었고 이것을 이용하여 모든 코인에 대하여 처리해주는 방식으로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 package study4; import java.io.BufferedRe..