grace's dev_note

정렬 정렬은 요소들을 일정한 순서대로 열거하는 알고리즘입니다. 정렬 기준은 사용자가 정할 수 있으며, 크게 비교식과 분산식 정렬로 나눌 수 있습니다. 대부분의 언어가 빌트인으로 제공해주며, 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재합니다. 상황에 따라서 적합한 정렬 방식이 있기 때문에 절대적으로 빠르다라고 말할 수 있는 정렬 방식은 없습니다. 비교식 정렬 버블 정렬: 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘입니다. O(n^2)를 가집니다. 선택 정렬: 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘입니다. O(n^2)를 가집니다. 삽입 정렬: 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘입니다. O(n^2)를 가집니다. ..

이진 탐색 여러분이 보통 탐색에 많이 사용하시는 방법은 선형 탐색입니다. 즉, 순서대로 하나씩 찾는 탐색 알고리즘을 말합니다. O(n)의 시간복잡도가 걸립니다. 하지만 효율성을 높이기 위해서 우리는 정렬 되어있는 요소들을 반씩 제외하며 찾을 수 있습니다. 이것을 이진 탐색이라고 합니다. 이진 탐색은 **O(log n)**만큼의 시간복잡도가 걸립니다. 이진 탐색은 반드시 정렬이 되어 있어야 사용할 수 있으며, 만약 정렬이 되어있지않다면 선형탐색보다 더 많은 시간이 걸릴 수도 있습니다. 배열 혹은 이진 트리를 이용하여 구현할 수 있습니다. 배열 배열에서 요소를 찾으려면 시작 지점을 left, 끝 지점을 right라고 두며 mid = (left+right)/2 로 중간 지점을 표현합니다. 중간지점과 탐색할 요..

시간 복잡도 실행 환경과 메모리 사용량에 따라 프로그램의 성능은 다르기 때문에 성능을 정확하게 측정하는 것은 불가능합니다. 그렇기 때문에 대략적인 성능 비교를 위한 상대적 표기법인 빅오 표기법을 사용하기로 했습니다. // O(log n) 로그시간 for(leti=0; i

원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절합니다. 그래프 그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 입니다. 정점(Node) 집합과 간선(Edge) 집합으로 표현할 수 있습니다. 그래프는 우리가 흔히 쓰는 지하철 경로 탐색 등에도 사용되는 소프트웨어 개발에서 중요한 자료구조 중 하나입니다. 정점은 여러 개의 간선을 가질 수 있으며, 크게 방향이 존재하는 방향 그래프와 방향이 존재하지 않는 무방향 그래프로 나눌 수 있습니다. 간선은 가중치를 가질 수 있으며, 탐색 시 그래프의 정점과 간선의 집합에서 계속 순환 가능한 사이클이 있습니다. 때문에 탐색 시 무한루프에 빠지지 않도록 사이클을 잘 찾아줄 필요가 있습니다. 그래프의 종류 무방향 그래프..

단순 구조 정수, 실수, 문자열, 논리 자료형 같은 것들입니다. 선형 구조 한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가집니다. 배열(순차 리스트) 일반적으로 변수를 선언하면 메모리 상에 데이터가 기록되게 됩니다. 우리는 변수를 통해 기록된 데이터를 꺼내 쓸 수 있습니다. 연관된 데이터를 쓰기 위해서는 여러개의 변수를 선언하는 방법이 있지만 보통 이렇게 작성을 하지는 않습니다. 이런 상황에서는 배열을 사용하게 됩니다. 배열은 연관된 데이터를 연속적인 형태로 구성된 구조를 가집니다. 배열에 포함된 원소는 순서대로 index를 가지며, index를 사용해 조회하거나 데이터를 수정할 수 있습니다. 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있습..

💡 알고리즘을 공부하고 문제를 풀 때 마음가짐 1. 항상 여러가지 풀이 방법이 있을 수 있다. 2. 항상 예외가 있을 수 있다 3. 내가 이미 푼 답을 최적화하는 방법을 항상 고민해야 한다. 4. 풀지 못했던 코드 또한 남겨두는 것이 좋다. 5. 다른 사람의 코드를 많이 봐야, 나의 생각에서 벗어나 새로운 사고를 할 수 있다. 6. 문제를 쉽게 포기하지 말고, 도저히 모르겠다면 답을 보고 시간이 지난 후 다시 풀어보는 것이 좋다. 7. 알고리즘 마스터가 될 필요는 없지만, 익숙해져야 한다. - 회사는 업무를 수행 할 수 있는 기초 능력을 확인하고 싶은 것이기 때문에 문제 해결 능력을 기르는 것이 좋다. - 예외적으로 알고리즘이 중요한 회사(게임, 인공지능 등의 분야)인 경우에는 중요하기 때문에 알고리즘/..

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python. Example 1: Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2. Example 2: Input: x = 8 Output:..

한 개의 문자열을 입력받고, 특정 문자를 입력받아 해당 특정문자가 입력받은 문자열에 몇 개 존재하는지 알아내는 프로그램을 작성하세요. 문자열의 길이는 100을 넘지 않습니다. 입력설명 첫 줄에 문자열이 주어지고, 두 번쨰 줄에 문자가 주어진다. 출력설명 첫 줄에 해당 문자의 개수를 출력한다. 입력예제 1 COMPUTERPROGRAMMING R 출력예제 1 3 function solution(str, letter){ return str.split('').filter(el => el === letter).length; } function solution(str, letter){ let answer = 0; for(el of str){ if(el === letter) answer++ } return answe..

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits. Example 1: Input: digits = [1,2,3] Output: [1,2,4] Expl..

대문자로 이루어진 영어단어가 입력되면 단어에 포함된 'A'를 모두 '#'으로 바꾸어 출력하는 프로그램을 작성하세요. 입력설명 첫 번째 줄에 문자열이 입력된다. 출력설명 첫 번째 줄에 바뀐 단어를 출력한다. 입력 예제 BANANA -> B#N#N# let str="BANANA"; // replaceAll function solution(s){ return s.replaceAll('A', '#') } console.log(solution(str)); // B#N#N# // recursive function + replace function solution(s){ function replace(s){ if(!s.includes('A')) return s s = s.replace('A', "#") return ..