빠에야는 개발중

생각했던 것 어떤 방식으로 하든 어쨌든 정렬인 문제다. 정렬 중 가장 빠른 정렬은 역시 퀵 정렬이기 때문에 퀵 정렬을 구현해서 스왑할때마다 카운트를 해주자! 웃기고 있네 너무나 당연하게도 퀵 정렬은 최악의 경우에 O(n^2)의 시간복잡도를 보여준다. 따라서 퀵정렬은 항상 가장 적은 swap 수를 보장해주지 못한다. 차라리 합병정렬을 하면 몰라… 그래서 어떻게 할것인가? 직관적으로 가보자 첫번째 원소부터 순차적으로 검사해서 해당 인덱스 i에서의 값이 i+1이 아니라면 원래 그 값이 있어야 할 위치와 바꿔준다. 즉 수식으로 나타내면 arr[i] != i+1 이면 swap(arr[i], arr[arr[i] - 1]) 인 것이다. 결과 맞았다… 이렇게 직관적으로 풀 문제였는데 괜히 돌아가려다가 망했다. 돌아갈거..

생각했던 것 문제에 주어진 배열을 그 상태로 분석하여 각 숫자의 위치에 따라 count 값을 조절하려고 시도했었다. 그러다 보니 두가지 생각이 나왔다. 원래 위치보다 앞에 있는 수 기준 : 앞으로 나온 숫자만큼 더해주고 그 수만큼 뒷자리의 수의 위치변화를 무시한다. 원래 위치보다 뒤에 있는 수 기준 : 원래 위치보다 앞에 있는 수들의 위치변화를 무시하고 뒤로 나온 숫자만큼 더해준다. 둘 다 시도했으나 실패했다. 그 이유는 “뒤로 간 숫자들끼리도 위치를 바꿀 수 있는 경우”를 생각하지 못했기 때문이다. 예를 들어 1 2 5 4 3이라는 배열이 주어졌다면 5가 앞으로 2번 나온 것도 더해줘야 하지만 뒤에서 서로 자리를 바꾼 3, 4도 생각해줘야한다. 앞선 두 방법은 이 경우를 고려하지 못한다. 풀이 결국 힌..

오랜만에 문제를 풀면서 간단하지만 쉽게 풀지 못했던 문제가 있었다. 결국 시간적으로 너무 오래 걸리는 것 같아 답을 찾아보았고 여러가지 것들을 배울 수 있었던 문제였다. DP 가장 먼저는 DP를 생각해내지 못했다. 경우의 수가 있고 그것들을 비교해서 최적값을 가져간다는 생각은 있었지만 선형적으로만 생각했지 메모이제이션에 대해서는 떠올리지 못했다. 배열의 크기 조절 평소에 배열을 다루면서 i+1, i+2 따위로 인덱스를 찾았는데 이렇게 하면 항상 마주치는 것이 ArrayIndexOutOfBound exception이었다. 볼 때마다 어떡하지 했었는데, 다음과 같은 두가지 방법으로 해결하면 된다는 걸 알았다. 1. 문제에 주어진 배열의 최대값보다 더 큰 배열을 만들면 된다. 2. dp를 사용하면 현재 인덱스..

단순 연결리스트에 대한 개념이 부족해서 전에는 풀지 못했던 문제였고, 공부를 해보았다. 한쪽 방향으로만 연결되어있다는 특징을 최대한 활용해야하는 문제이다. 일반적인 배열이나 ArrayList라면 인덱스로 간단하게 바꿀 수 있다. 이중 연결리스트도 오버헤드가 좀 들지만 비교적 간단하게 가능하다. 하지만 단순 연결리스트는 생각을 좀 해야하는데, 처음에 생각했던 방법은 모든 요소를 스택에 집어넣어서 하나씩 빼며 리스트를 새로 생성하는 것이었다. 하지만 이 방법은 리스트의 크기만큼의 메모리가 필요하기 때문에 규모가 커지면 효율적이지 못하다. 시간적으로도 선형 탐색을 두번해야한다는 점에서 그 단점을 알 수 있다. 그래서 추가메모리를 최대한 줄이고 탐색 시간도 줄이기 위해서는 다음과 같이 하면 된다. 핵심은 새로운..

물건 값보다 많은 돈을 낼 경우 거스름돈을 돌려주게 됩니다. 거스름돈은 한 금액의 돈으로 줄 수도 있지만, 여러 금액의 동전을 섞어 거슬러 줄 수 있습니다.거스름돈이 N원일 때, 1원, 2원, 5원 동전이 있다면 몇 가지 방법으로 돈을 거슬러 줄 수 있을까요? change 함수를 통해 경우의 수를 반환해주는 함수를 만들어 보세요. K에는 사용할 수 있는 동전의 종류가 들어 있습니다.예를 들어, N = 5이고 K = [1, 2, 5]이면 1원, 2원, 5원 동전을 가지고 5원을 맞추는 경우의 수를 찾으면 됩니다.1원 5개1원 3개, 2원 1개1원 1개, 2원 2개5원 1개이렇게 총 4가지 경우가 있으면, 4를 리턴해 주면 됩니다. 각각의 순서가 의미가 없기 때문에 bfs로는 풀 수 없을 것 같았고 dp를 ..

1x1 정사각형 2개가 붙어 있는 타일이 있습니다. 이 타일을 이용하여 총 3xN 의 보드판을 채우려고 합니다. 타일은 가로, 세로 두 가지 방향으로 배치할 수 있습니다.보드판의 길이 N이 주어질 때, 3xN을 타일로 채울 수 있는 경우의 수를 반환하는 tiling 함수를 완성하세요.단, 리턴하는 숫자가 매우 커질 수도 있으므로 숫자가 5자리를 넘어간다면 맨 끝자리 5자리만 리턴하세요.예를 들어 N = 2일 경우 3을 반환해 주면 됩니다. 하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 리턴하세요. 리턴타입은 정수형이어야 합니다.참고: 이 문제는 2 x n 타일링 문제와 유사합니다. 문제이해가 어려우면 2 x n 타일링 문제를..

과자를 좋아하는 동우는 책상 위에 일렬로 놓아진 과자를 발견하였습니다. 과자에는 맛을 숫자로 평가한 종이가 붙어 있습니다. 동우는 맨 왼쪽부터 순서대로 과자를 먹기로 하였습니다. 동우는 먹을 과자를 고를 때 이전에 먹은 과자보다 맛이 더 좋은 과자만 먹습니다.제일 처음에 맛이 3인 과자를 먹었다면, 다음에는 4보다 작은 맛의 과자는 먹지 않습니다.책상위에 놓인 과자의 맛이 입력되면, 동우가 최대 과자를 몇 개를 먹을 수 있는지 반환해주는 eatCookie 함수를 완성하세요.예를 들어 [1, 4, 2, 6, 3, 4, 1, 5] 가 입력된다면 동우는 1, 3, 5, 6, 8번째 과자(각각의 맛은 1, 2, 3, 4, 5)를 골라 총 5개를 먹을 수 있고, 5개보다 더 많이 먹을 수 있는 방법은 없으므로 5..

N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다.이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에... 서 있는 상태를 나타냅니다.이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다.예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다.1번째 방법은 [1,2,3]2번째 방법은 [1,3,2]3번째 방법은 [2,1,3]4번째 방법은 [2,3,1]5번째 방법은 [3,1,2]6번째 방법은 [3,2,1]이 때 K가 5이면 [3,1,2]가 그 방법입니다.사람의 수 N과 순서 K를 입력받아 K번째 ..

N개의 원판은 총 2N -1 번의 과정을 거쳐 이동할 수 있습니다. 하지만 어떠한 과정으로 원판을 옮겨야 2N -1 번만에 옮길 수 있는지는 아직 모릅니다. 원판이 N개 있을 때, Hanoi 함수에서 어떠한 과정으로 2N -1 번만에 옮길 수 있는지 과정을 리턴하세요.리턴값의 표기 방법은 다음과 같습니다.3개의 기둥은 순서대로 각각 1, 2, 3번으로 표기합니다.원판을 기둥1에서 기둥3으로 이동했다면 [1, 3]으로 표기합니다.원판을 기둥3에서 기둥1로 이동했다면 [3, 1]로 표기합니다.이러한 이동 순서를 담는 배열을 리턴하면 됩니다. 예를들어 N이 2라면 아래 그림과 같이 옮길 수 있으므로 리턴값은 [ [1,2], [1,3], [2,3] ]입니다. 기본적인 하노이탑 문제인데, 재귀를 사용한다는건 알았..

1x1 정사각형 2개가 붙어 있는 타일이 있습니다. 이 타일을 이용하여 총 2xN 의 보드판을 채우려고 합니다. 타일은 가로, 세로 두 가지 방향으로 배치할 수 있습니다.보드판의 길이 N이 주어질 때, 2xN을 타일로 채울 수 있는 경우의 수를 반환하는 tiling 함수를 완성하세요.예를들어 N이 7일 경우 아래 그림이 타일을 배치할 수 있는 한 경우입니다. 단, 리턴하는 숫자가 매우 커질 수도 있으므로 숫자가 5자리를 넘어간다면 맨 끝자리 5자리만 리턴하세요.예를 들어 N = 2일 경우 가로로 배치하는 경우와 세로로 배치하는 경우가 있을 수 있으므로 2를 반환해 주면 됩니다. 하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 ..