Algorithm

Big O notation why is Big O notation neccessary? 다른 접근 방법들을 비교했을 때, 어떤 방법이 더 나은지 알기 위해서 코드가 느리거나 충돌 났을 때, 비효율적(긴 소요시간/ 많은 메모리 사용) 코드를 찾기 위해서 >N : the number of simple operations the computer has to...

Recursion Why use Recursion? > recursion : a process (a function) that calls itself recursion을 사용하는 곳 JSON.parse / JSON.stringfy document.getElementById / DOM 탐색 알고리즘 Object 탐색 복잡한 ...

Recursion Problems Reverse Problem 문자열을 받고, 그 문자열을 거꾸로 반환하는 회귀 함수 구현 Reverse Solution helper method recursion inner helper function 접근 방법 slice 메소드를 사용해서 문자열을 자른다 문자열을 거꾸로 변환해야하므로, ...

Search Algorithm Linear Search 배열을 앞에서부터 순차적으로 탐색함 linear search를 사용하는 built-in 메서드 : indexOf, includes, find, findIndex Linear Search function 배열과 값을 인자로 받는 함수 값이 존재한다면 그 값의 index를 반환함 값이 존재하지 않는...

Sort Built-In JavaScript Sort built-in sort 메서드는 선택적인 comparator 함수를 인자로 받음 comparator 함수를 사용해서 어떻게 정렬할 것인지 JavaScript에 알림 comparator 함수는 반환값을 기준으로 요소 한 쌍의 정렬 순서를 정함 음수를 반환한 경우, 첫 번째 요소가 두 번째 요소...

Search Problem Largest Number At Leat Twice of Others 주어진 배열 nums의 최대값이 적어도 다른 값들의 2배라면 최대값의 index를 반환하고, 그렇지 않을 경우 -1을 반환하는 함수 구현 Interaction of Two Arrays 주어진 2개의 배열 nums1, nums2를 인자로 받아서 두 배열의 ...

Bubble, Selection, Insertion Sort 단점 배열의 길이가 엄청 커지면 정렬 시간이 오래 걸림 (시간복잡도가 O(N^2)이므로) Merge Sort merging과 sorting의 조합임 배열의 요소가 0개 또는 1개인 배열은 항상 정렬되어 있다는 사실을 이용함 배열을 0 ~ 1개 요소를 가진 배열로 분해하고, 새로 정렬된 배열...

Quick Sort Merge Sort와 같이, 비어 있거나 요소가 1개인 배열은 항상 정렬되어 있다는 사실을 이용함 한 요소를 선택해서 pivot 변수에 할당하고, pivot 변수를 기준으로 작은 값들은 pivot 변수 왼쪽으로 이동시키고 큰 값들은 pivot 변수의 오른쪽으로 이동시켜서 pivot 변수의 정렬된 배열에서의 index값을 얻음 pivot...

Mock Test 1 코드 주인을 찾아라! 디렉토리마다 코드 주인 정보는 JavaScript 객체로 주어짐 객체는 1 이상 5 이하 깊이를 가지는 디렉토리 구조를 다룸 하위 디렉토리를 가지지 않는 디렉토리들만 코드 주인을 가짐 예) 아래 예시에서 services 폴더는 코드 주인 가지지 않음 계산할 디렉토리는 폴...

Problem(lev.1) : 신고 결과 받기 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다. 한 유저를...

Problem(level.1) : 예산 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요. d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다. d의 각 ...

Problem(lev.1) : 성격 유형 검사하기 나만의 카카오 성격 유형 검사지를 만들려고 합니다. 성격 유형 검사는 다음과 같은 4개 지표로 성격 유형을 구분합니다. 성격은 각 지표에서 두 유형 중 하나로 결정됩니다. | 지표 번호 | 성격 유형 | |:-----:|:-----:| | 1번 지표 | 라이언형(R), 튜브형(T) | | 2번 지표 | ...

built-in method sort built-in method sort : JavaScript를 해석하는 엔진에서 어떻게 구현했으냐에 따라서 정렬된 알고리즘이 달라짐 Chrome의 V8 엔진에서는 정렬 알고리즘으로 Tim Sort를 사용함 Firefox의 Spidermoney에서는 정렬 알고리즘으로 Merge Sort를 사용함 Tim...

Greedy Algorithm Greedy Algorithm 여러 경우 중 하나를 결정해야할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 순간마다 하는 선택은 그 순간에 대해서 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 전역적인 해답을 만들었다고 해서 그것이 최적이라...

Programmers Problem(lev.1) : 체육복 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요. 학생들의 번호는 체격 순으...

완전 탐색 알고리즘 모든 경우의 수를 다 체크해서 정답을 찾는 방법 문제의 정확한 결과값을 얻을 수 있는 가장 확실하고 기초적인 방법 완전 탐색으로 문제를 푸는 방법 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산함 가능한 모든 방법을 계산함 Brute Force Permutation(순열) Recursion(재귀) ...

Programmers Problem(lev.2) : 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 r...

Tree Traversal Breadth-First Search (BFS) Depth-First Search (DFS) Breadth-First Searh (BFS) Breadth-First Search : 인접한 노드를 모두 탐색한 후, 다음 깊이의 노드를 탐색함 BFS 수행 방법 (Iteratively) 방문했던 노드의 값을 저장하기 위해...

HackerRank Problem : Cats and a Mouse Two cats and a mouse are at various positions on a line. You will be given their starting positions. Your task is to determine which cat will reach the mouse fir...

Graph Traversal Visting / Updating / Checking each vertex in a graph Usuage of Graph Traversal 소셜 네트워크 (SNS) 웹페이지 탐색 (an webpage => other webpage) 가장 근접한 값 또는 추천을 찾기 가장 짧은 경로 탐색 GPS Navigation ...

Programmers Problem - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매...

Dynamic Programming 복잡한 문제를 단순한 작은 문제들로 분해함 작은 문제를 한번만 풀고, 그 해를 저장해둠(memoization) 큰 문제를 풀 때 똑같은 작은 문제가 나타나면, 저장해둔 해를 사용해서 해결함 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems...

LeetCode Problem : Merge Two Binary Trees You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while th...

LeetCode Problem : Last Stone Weight You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose the heav...

Union-find 대표적인 그래프 알고리즘 합집합 알고리즘 또는 서로소(Disjoin-Set) 알고리즘이라고도 부름 주로 트리(Tree) 구조를 이용하여 구현됨 크루스칼(Kruskal) 알고리즘과 함께 사용됨 크루스칼 알고리즘 : 그래프 내의 모든 노드들을 가장 적은 비용으로 연결하기 위해 사용되는 알고리즘 methods of Union-fin...

LeetCode Problem : Find if Path Exists in Graph There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a ...

LeetCode Problem : Vaild Perfect Square Given a positive integer num, write a function which returns true if num is a perfect square else false. Follow up: Do not use any built-in library function su...

LeetCode Problem : N-th Tribonacci Number The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given n, return the value of Tn Con...

Problem (lev.2) : 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개...

Problem: 주차 요금 계산 주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다. 요금표 |기본 시간(분)|기본 요금(원)|단위 시간(분)|단위 요금(원)| |:-----:|:-----:|:-----:|:-----:| | 180 | 5000 | 10 |...

Problem : 귤 고르기 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2,...

Problem : Roman to Integer Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. | Symbol | Value | |:----:|:----:| | I | 1 | | V | 5 | | X | 10 | | L | 50 | | C | 100 |...

Dijkstra's Algorithm What is Dijkstra's Algorithm? 다익스트라 알고리즘 : 그래프에서 두 노트 사이의 가장 짧은 경로를 찾는 알고리즘 다익스트라 알고리즘 사용 예 GPS : 가장 빠른 경로 찾기 Network Routing : 데이터에 대해 열려 있는 가장 짧은 경로 찾기 Biology : ...

Programmers Problem : 등산코스 정하기 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등...

Backtracking 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 조건문을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색함 최적화 문제와 결정 문제를 푸는 방법이...

Programmers Problem : N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인 경우, 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다. 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, ...

Problem : 개인정보 수집 유효기간 고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해...

Problem : 괄호 회전하기 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. (), [], {} 는 모두 올바른 괄호 문자열입니다. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다....

Problem : 바탕화면 정리 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 wallpaper가 주어집니다. 파일들은 바탕화면의 격자칸에 위치하고 바탕화면의 격자점들은 바탕화면의 가장 왼쪽 위를 (0, 0)으로 시작해 (세로 좌표, 가로 좌표)로 표현합니다. 빈칸은 ".", 파일이 있는 칸은 "#"...

Problem (lev. 1) : 대충 만든 자판 휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다. 예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한...

Problem (lev. 1) : 둘만의 암호 두 문자열 s와 skip, 그리고 자연수 index가 주어질 때, 다음 규칙에 따라 문자열을 만들려 합니다. 암호의 규칙은 다음과 같습니다. 문자열 s의 각 알파벳을 index만큼 뒤의 알파벳으로 바꿔줍니다. index만큼의 뒤의 알파벳이 z를 넘어갈 경우 다시 a로 돌아갑니다. skip에 있는 알...

Problem (lev. 1) : 달리기 경주 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수...

Problem (lev. 2) : 멀리뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 ...

Problem (lev. 2) : 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야...

Programmers Problem (lev. 2) : 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목...

Programmers Problem : 기사단원의 무기 숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다...

Problem (lev.2) : 연속된 부분 수열의 합 비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다. 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다. 부분 수열의 합은 k입니다. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다....

LeetCode Problem (easy) : Count Negative Numbers in a Sorted Matrix Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numb...

Programmers Problem : 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자...

Problem 1436. Destination City You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the...

Problem 496. Next Greater Element 1 The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-inde...

Problem 392. Is Subsequence Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string b...

Problem 2784. Check if Array is Good You are given an integer array nums. We consider an array good if it is a permutation of an array base[n]. base[n] = [1, 2, ..., n - 1, n, n] (in other words, it...

Problem 290. Word Pattern Given a pattern and a string s, find if s follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-emp...

Problem 49. Group Anagrams Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a ...

Problem 605. Can Place Flowers You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. Given an integer array flower...

Problem 459. Repeated Substring Pattern Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. Examples Example 1: I...

Problem 2405. Optimal Partition of String Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a sin...

Problem 232. Implement Queue using Stacks Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop,...

Problem 844. Backspace String Compare Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character. Note that after backspaci...

Problem 1305. All Elements in Two Binary Search Trees Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order. Examples Ex...

Problem 278. First Bad Version You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each v...

Problem 1678. Goal Parser Interpretation You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G", "()" and/or "(al)" in some order. The Goal Parser will ...

Problem 345. Reverse Vowels of a String Given a string s, reverse only all the vowels in the string and return it. The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and u...

Problem 2130. Maximum Twin Sum of a Linked List In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / ...

Problem 1043. Partition Array for Maximum Sum Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values chang...

Problem 1614. Maximum Nesting Depth of the Parentheses A string is a valid parentheses string (denoted VPS) if it meets one of the following: It is an empty string "", or a single character not eq...

Programmers Problem lev.3 정수 삼각형 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배...

LeetCode Problem 739. Daily Temperatures Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait a...

LeetCode Problem 2149. Rearrange Array Elements by Sign You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers. You should rearra...

Programmers Problem lev.2 JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는...

Problem 942. DI String Match A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where: s[i] == 'I' if perm[i] perm[i + 1]. Gi...

Problem 222. Count Complete Tree Nodes Given the root of a complete binary tree, return the number of the nodes in the tree. According to Wikipedia, every level, except possibly the last, is complet...

Problem 876. Middle of the Linked List Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node. Examples Exa...

Problem 111. Minimum Depth of Binary Tree Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf no...

Problem 2928. Distribute Candies Among Children I You are given two positive integers n and limit. Return the total number of ways to distribute n candies among 3 children such that no child gets mo...