Coding 한놈만 팬다

문제링크 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 문제 풀이 과정 동전문제는 그리디 문제로 많이 알려져 있지만, 이 문제는 그리디로 접근 하면 해결이..

문제링크 문제 풀이 과정 결혼식에 초대 가능한 친구는 친구와 그 친구의 친구까지 초대가 가능하다. 이것은 탐색 할 때 깊이가 2까지만 탐색한다는 것을 의미 할 수 있다. 예제 1번 기준으로 그래프로 나타내면 아래와 같다. 1의 기준으로 친구는 2, 3 이 해당 된다. 친구의 친구는 4가 해당 된다. public static void Find(int depth, int start){ if(depth == 2){ return; } for (int i = 0; i < list[start].size(); i++) { int next = list[start].get(i); visited[next] = true; Find(depth + 1, next); } } 재귀호출 탈출 조건을 깊이가 2일때로 해주었다. 근처 ..

문제링크 문제 풀이 과정 벌의 위치와 꿀통의 위치를 3가지 케이스로 나눠서 풀이를 해야한다. [1] 벌이 왼쪽에 고정 되어 있으며, 꿀통은 오른쪽에 고정 되어 있을때 [2] 벌이 오른쪽에 고정 되어 있으며, 꿀통은 왼쪽에 고정 되어 있을때 [3] 벌이 양쪽에 고정 되어 있으며, 꿀통이 움직일때 각각의 케이스를 진행 할때마다 벌1과 벌2의 꿀의 합을 반복문을 이용하여 새롭게 구했는데 이렇게 하면 서브테스크 4번에서 시간 초과가 생긴다. 아래 코드가 바로 시간 초과가 난 코드이다. 이것을 해결하기 위해서 합을 매번 새롭게 구하지 않고 벌또는 꿀통이 움직일때마다 이전 값에서 더하거나 빼는 방식으로 구했더니 모든 태스크가 통과가 되었다. 전체 코드

문제링크 문제 설명 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 ..

문제링크 문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, "ULURRDLLU"로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 ..

문제링크 문제 풀이 과정 투포인터를 이용하면 간단하게 해결되는 문제이다. 부분 수열의 합이 중복 되면 안되므로 부분수열의 합을 HashSet 에 저장하여 나중에 HashSet 의 size 를 출력하면 부분 수열의 합의 수가 출력이 된다. HashSet sumSet = new HashSet(); for(int item : elements){ sumSet.add(item); } 부분 수열의 길이가 1인 경우는 배열 원소가 해당 되므로 우선 배열 원소 각각을 set 에 넣어 주었다. 부분 수열의 길이가 2일때 초기 start 와 end 를 start 는 0, end 는 start + i(간격) 으로 지정해준다. start 부터 end 까지의 합을 sum 에다 저장해둔다. 그다음 부분수열로 움직일때 sum 에서..

문제링크 문제 풀이 과정 이 문제를 잘 보면 f(n) = f(n - 1) + f(n - 2) 피보나치 수열이라는 것을 알수 있다. 5 까지의 경우의 수이다. 칸이 3일때를 보면 칸 2일때와 1일때의 값을 더한 값이 된다. 칸이 4일때도 칸이 3일때와 2일때의 값을 더한 값이 칸이 4일때의 값이 된다. 따라서 이 문제가 피보나치 수열이라는 것을 알 수 있다. 피보나치수열은 재귀호출을 이용하여 풀이하는 것과 dp 배열을 사용하여 풀이 하는 방법이 있는데 이 문제는 재귀 호출을 이용하면 통과가 안된다. 또한 dp 을 선언 할때 배열의 칸을 n + 1 만큼 잡았었는데 이러면 케이스 1이 통과가 안된다. dp 배열의 길이를 매우 넉넉하게 잡거나 n + 2 만큼 잡으면 테스트 1이 통과가 된다. 전체 코드

문제 링크 문제 풀이 과정 체스 규칙을 잘 모르면 이 문제를 처음 접했을 때 난감할 수 있다. 사실 체스 규칙을 전혀 몰라서 퀸의 움직임에 대해서 먼저 검색했었다. 퀸은 오른쪽, 왼쪽, 위, 아래, 대각선으로 움직일 수 있다. 첫번째 퀸의 위치가 (0, 1) 일때 엑스 친 부분은 퀸이 공격 가능한 위치이다. 이 문제는 서로 다른 퀸이 공격 못하게 배치해야 되므로 다음 퀸의 자리는 (1, 3) 이 된다. 3번째 줄에는 퀸을 둘 수 있는 곳이 한곳밖에 없다. 4번째 퀸까지 배치가 가능하므로 서로다른 퀸이 공격 못하게 하는 위치가 된다. 대부분 구글에서는 1차원 배열로 풀이 하였지만, 1차원 배열보다는 직관적인 2차원배열이 이해가 잘되서 2차원 배열로 풀이 하였다. 퀸이 공격이 가능한 자리를 표시하는 visi..

문제링크 문제 풀이 과정 이 문제의 핵심은 LRU 알고리즘을 이용하는 것인데, LRU 알고리즘을 사전에 알고 있으면 쉽게 해결 되는 문제이다. 첫번째 예제를 이용하자면 캐시의 사이즈가 3이므로 3개의 도시까지 캐시에 들어 올 수 있다. 도시배열을 보면 3번째까지 도시가 겹치는 것이 없으므로 3개의 도시가 캐시 미스 되어 캐시에 들어 오게 된다. 그 다음 도시인 NewYork 은 기존 캐시에 없었으므로 캐시 미스가 발생 하게 된다. 이때 캐시 사이즈는 3이므로 LRU 알고리즘에 의해서 제일 처음에 사용했던 캐시 부분이 삭제된다. 만약 캐시에 넣을 데이터가 캐시에 존재 하고 있다면 캐시 히트가 발생 하여 기존 캐시에 있던 데이터를 삭제 할 필요가 없어진다. 전체코드

문제링크 문제 풀이 과정 보석을 가방에 넣는 로직에서 보석이 중복으로 들어가지 않는 것에 대해 오래 고민을 한 문제이다. 우선 보석의 무게와 비용을 한번에 담기 위해서 Item 클래스를 만들었다. static class Item implements Comparable{ int idx; int weight; int cost; public Item(int idx, int weight, int cost) { this.idx = idx; this.weight = weight; this.cost = cost; } @Override public int compareTo(Item o) { if(this.weight == o.weight){ return o.cost - this.cost; } return this.we..