프린세스 다이어리

너무 헷갈리고 어려워서 정리. 특히 Linked List 버전으로 작성하기 까다로웠음 1. Bubble Sort 1.1. List # 오른쪽 엘리먼트랑 비교해서 내가 더 크면 쭉쭉 오른쪽꺼랑 swap해줌 # 점점 큰 엘리먼트를 오른쪽에 먼저 보낸다는 게 버블같다는 의미에서 Bubble sort def bubble_sort(list): for i in range(len(list) - 1, 0, -1): for j in range(i): if list[j] > list[j + 1]: temp = list[j] list[j] = list[j + 1] list[j + 1] = temp return list my_list = [3, 1, 5, 2, 4] print(bubble_sort(my_list)) 1.2. ..

1. 풀이 순서 문제 입력에 따라 2차원 배열을 만들어주는 함수를 하나 만든다.(makeGraph) dfsAll() 수행하여, dfs() 종료 시마다 현재 정점을 기록한다.(order) 위상정렬 결과를 얻기 위해 그 기록을 뒤집어서 결과를 도출한다.(order.reverse()) 추가로 DAG 조건에 부합하는지 검사하여 예외처리 한다. 2. 해답 const makeGraph = (numOfTest, words) => { // 1. 2차원 배열을 26*26 크기로 초기화해줌. let graph = Array.from(Array(26), () => Array(26).fill(0)); // 2. 들어온 단어들을 돌아줌. 이 케이스에서는 나름의 알파벳 순서대로 정렬돼 있으므로 지금거([j])랑 이전거([j-1=..

문제 링크 1. 접근 방법 (1) 두 리스트의 head를 비교하고, 둘 중 큰 head를 작은 head의 next로 연결하는 아이디어다. (2) list1이나 list2가 null이면 둘 중 다른 리스트의 나머지를 다 리턴한다. if (!list1) return list2; if (!list2) return list1; (3) list1.val이 list2.val보다 작으면 list1의 next를 list2로 옮겨준다. list1.next와 list2를 인자로 넘겨준 결과를 list1이 가리키도록 하면 된다. if (list1.val

1. 접근 방법 (1) 힌트에 이전 피보나치 문제처럼 풀라고 해서 재귀로 풀었더니 시간 초과가 났다(???). 그래서 DP로 풀었다. (2) 베이스 케이스를 써 준다. stairs[1] = 1; stairs[2] = 2; (3) for문을 돌면서 점화식을 이용해 연산해준다. for (let i = 3; i

문제 링크 1. 접근 방법 (1) 이전에 계산해 둔 결과를 활용하여 지금 연산을 하는 메모이제이션 방식이다. (2) cache 객체를 만들어 놓고, 함수를 재귀적으로 실행할 때 cache에 해당 값이 이미 존재하면 그 값을 리턴한다. if (Object.keys(cache).includes(n)) { return cache.n; } (3) cache에 해당 값이 없으면, 값을 리턴한다. 피보나치 배열에서는 인덱스 0, 1은 각각 값이 0과 1이고, 그 다음 인덱스부터는 이전 인덱스에 해당하는 값과 이이전 인덱스에 해당하는 값을 더한 값이 할당된다. if (n < 2) { result = n; } else { result = recur(n - 2) + recur(n - 1); } (4) cache에 인덱스..

1. 접근 방법 (1) 구하고자 하는 rowIndex의 각 원소의 값을 구하려면 이전 rowIndex의 각 원소의 값이 필요하기 때문에 통째로 삼각형을 만들어주면 된다. (2) n번째 줄의 각 원소는 다음과 같이 구성돼 있다. 인덱스 0은 1, 인덱스 1~n-1는 n-1번째 줄의 인접한 왼쪽, 오른쪽 원소를 더한 값, 인덱스 n은 1이다. (3) (2)번의 내용을 이중 for문을 이용해 만들어준다. row.push(1); for (let i = 1; i 0; j--) { row[j] = row[j - 1] + row[j]; } // 맨 마지막은 직접 넣어준다. i = 1인 경우 j for문은 타지 않음. row.push(1); } (4) 중첩된 j for문에서 j를 거꾸로 감소시키는 이유는 j for문에..

문제 링크 1. 접근 방법 (1) 이진탐색트리에서 루트를 기준으로 왼쪽 노드의 value는 작은 수, 오른쪽 노드의 value는 큰 수다. 이 특성을 이용해서 재귀로 풀면 된다. (2) 찾는 val이 루트의 value보다 크면 오른쪽을 재귀로 탐색한다. (3) 찾는 val이 루트의 value보다 작으면 왼쪽을 재귀로 탐색한다. if (root.val < val) { return searchBST(root.right, val); } else { return searchBST(root.left, val); } (3) edge case 예외처리 해 준다. if (!root) return null 2. 전체 해답 /** * Definition for a binary tree node. * function Tre..