프로그래민👨‍💻

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..

Spring Data JPA는 다양한 프레임워크와 연동기능을 제공한다. JPA만으로 해결할 수 없는 동적쿼리등을 지원하기 위함이다. 대표적으로 QueryDSL 등을 사용하고, JDBC Template, Mybatis 등도 사용할 수 있다. 가장 많이 사용해본 Mybatis와의 연동을 실습해보았다. 사용자 정의 Repository - MyBatis MemberRepositroy에 기존 Spring Data JPA가 제공하는 메소드 말고, 다른 프레임워크(Mybatis)를 이용한 메소드를 추가하기 위해 다음과 같은 사용자 정의 Repository와 구현체 class를 만들어보았다. 1 2 3 public interface MemberRepositoryMybatis { List findDynamic(Membe..

페이징과 정렬 Spirng Data JPA는 아주 간편한 페이징과 정렬기능을 제공해준다. 메소드의 리턴 타입으로 Page를 사용해주고, pageable이란 파라미터에 시작페이지, 갯수, 정렬조건, 그리고 메소드이름으로 검색조건을 적절히 사용해준다면 count쿼리까지 자동으로 조회해주는 쉬운 페이징을 할 수 있다. 다음과 같은 예시가 있다. 1 2 3 4 5 public interface MemberRepository extends JpaRepository{ //페이징 Page findByAge(int age, Pageable pageable); } Colored by Color Scripter 위 처럼 Page를 리턴타입으로 받아주고, Pageable 변수를 파라미터로 가지는 메소드 네이밍 쿼리를 작성하..