Outgoing Introvert

투 포인터 알고리즘이란? - 1차원 배열에서 두 개의 포인터(시작점, 끝점)의 위치를 기록하면서 목표값을 구하는 알고리즘. - 완전탐색 O(n^2) -> O(n) 선형 시간 복잡도로 문제 해결 가능 - 연속된 구간의 원소들을 처리하거나, 정렬된 배열에서 무언가를 구할 때 사용 포인터 두 개가 한 곳에서 시작하는 경우 end 포인터가 0 에서 n 까지 움직일 때 까지 (배열의 길이만큼 순회하며) 반복하므로 O(n)의 시간복잡도를 가진다. (Linear time 선형 시간 복잡도) 1. 시작점과 끝 점이 첫번째 원소의 인덱스를 가리키도록 한다. 2. 부분합이 S보다 작으면 end ++ 3. 부분합이 S보다 크거나 같으면 start ++ 4. 문제에서 제시한 부분합의 조건을 만족시킬 경우 처리 모든 경우를 확..

그리디 Greedy 알고리즘이란? 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않고, 오직 현재 시점에서 가장 좋은 선택을 하는 알고리즘 ex) 대표적인 문제 : 백준 11047 동전 0 미래를 고려하지 않고 현재 내릴 수 있는 최선의 선택에만 집중하기 때문에 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지는 않는다. 항상 최적의 해를 찾을거라는 보장은 없기 때문에 근사 알고리즘이라고도 한다. 코테에서 그리디 알고리즘 사용 가능한 조건? 코딩테스트에서는 최적 해가 보장되는 조건에서만 그리디 알고리즘을 사용해야 한다. (보통 코테에서 그리디 문제는 이렇게 얻은 해가 최적의 해가 되는 상황으로 풀리도록 출제가 된다고 함) - 현재의 선택이 미래의 선택에 영향을 주지 않을 때 - 부분의 최적 ..

누적 합 Prefix Sum 배열에서 구간 합을 구해야 하는 문제에서 중첩 for 문을 사용해 값을 계속 더해주면 O(n^2) 시간 만큼 걸리지만 누적 합을 사용하면 계속 더해줄 필요 없이 마이너스 연산 만으로 해결 가능하다. O(1) 동적 계획법 문제들에서 DP로 연산 결과를 저장할 때에도 누적 합 방식이 많이 사용되는 듯 하다. * prefixsum 만들 때 index 0 말고 1부터 담아야 만들기 쉬움 psum 1, ~2, ~3, ~4 … suffix sum 은 뒤에서 부터 더하는 것. 알고리즘 대회 같은데서 가끔 나오긴 하는데 코테에서는 잘 안나옴. 구간쿼리 구할 때 배열의 요소가 정적일 경우 psum 동적일 경우 펜윅트리(?) 1차원 배열일 때 누적 합 구하는 건 간단하지만 2차원 배열은 좀,,..

이분탐색 N개의 수가 크기 순서대로 배열되어 있을 때 특정 수 K가 몇 번째 위치에 있는지 빠르게 찾는 방법 한 가운데에 있는 수를 보자 짝수면 가운데서 앞번째 절반만 남기고 그 안에서 찾기 줄어든 범위 내에서 재귀적으로 해결 한 번에 배열이 절반씩 줄어들기 때문에 시간복잡도는 O(log n) 재귀방식 or while 반복문 사용 가능 이분탐색 응용 parametric search 최적화 문제를 결정 문제로 바꾸어 푸는 것 최적화 문제 : f(i) = 1 이 되는 i 의 최솟값을 구하여라. 결정 문제 : 어떤 i 에서, f(i) = 1 인가? 이분탐색 문제들 https://www.acmicpc.net/workbook/view/9764 백준 1920 수 찾기 백준 10816 숫자 카드 2 백준 1654 랜..

input n에 대하여 가장 높은 차수 O(1) 상수 시간 constant time O(n) 선형 시간 linear time ex) 반복문, 반복문이 여러개(O(n)에 수렴) O(n^2) quadratic time ex) 반복문이 중첩 O(log n) 로그 시간 log time : 입력 크기에 따른 실행 횟수의 변화가 다양한 경우. ex) 이진 탐색, for (int i = 1; i \(log_2n\) O(n log n) 선형 로그 시간 : 입력 크기의 변수가 여러 개인 경우 : O(n log m) ex) O(n) 반복문 + log m 반복문 중첩 => n log m 재귀 함수의 시간 복잡도 분석 쉬운 경우 : 팩토리얼, 합병 정렬(merge sort) - 팩토리얼: T(n) = T(n - 1) + 1 ..

스택 Stack 곡차곡 쌓아 올린 형태의 자료구조. 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출 LIFO (Last In First Out) 구조 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 삽입/삭제할 수 있다. 스택에서 top을 통해 삽입하는 연산을 push, top을 통해 삭제하는 연산을 pop 이라고 한다. 스택 활용 예시) - 웹 브라우저 방문 기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. - 실행 취소 : 가장 나중에 실행된 것부터 실행을 취소한다. 큐 Queue 줄을 서서 기다리는 것. 먼저 들어온 것이 먼저 나가는 선입선출 FIFO (First In First Out) 방식의 자료구조 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제..

DP가 왜 필요? DP의 장점? DP 문제 어떻게 알아보고 접근할지 1. 다이나믹 프로그래밍의 목적 DP 는 완전 탐색, DFS, BFS 와 같이 수많은 경우의 수를 전부 따져봐야 하는데, 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고 수행시간을 단축하고자 만들어진 알고리즘. DP가 없던 시절에는 최단 경로를 찾거나, 최고 점수를 만들거나 하는 문제를 풀기 위해 모든 조합을 다 만들어 보는 수밖에 없었음. DP 알고리즘이 만들어진 후에는 수행시간을 현저하게 줄일 수 있었다. 예시) 프로그래머스 - 정수 삼각형 (Swift는 지원 안됌..ㅠ) => 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여 수행 속도를 개선한다. 메모리를 사용한다 : 배열 혹은 자료구조를 만든다. 중복 연산을 줄인..

복잡도란? 알고리즘의 성능을 나타내는 척도 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 복잡도를 측정함으로써 시간복잡도에서는 알고리즘에 의해 필요한 연산의 횟수를, 공간복잡도에서는 사용되는 메모리의 양을 계산할 수 있다. 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도 시간 복잡도 표현할 때는 빅오 Big-O 표기법을 사용 빅오 표기법이란? : O(N) 연산횟수 N번 반복문 돌리는 경우 O(1) 연산횟수 1 O(N²) 데이터 개수가 N개일 때, 2중 반복문 돌리는 경우 시간제한이 1초인 문제에 대한 시간복잡도 설계 예시 N의 범위 500 인 경우 : O(N³) 알고..

브루트 포스 (완전탐색) 알고리즘 ex) 비밀번호가 될 수 있는 모든 조합을 다 시도해보는 기법 구현방법 1. for / while 반복문 2. 재귀함수 ex) 프로그래머스 - 소수 찾기 여러 숫자 카드들이 주어졌을 때, 카드들로 가능한 모든 조합의 숫자를 만들어보고, 그 중 소수의 개수를 구해야. 소수 판별 이전에 주어진 카드들로 모든 조합의 수를 만들 줄 알아야. 재귀함수를 계속 호출하면서 각 숫자 카드를 쓸지 안쓸지 결정하며 조합 만들기 브루트 포스만으로 풀 수 있는 코테 문제는 드물지만, 문제의 일부를 브루트 포스 알고리즘을 이용해 풀어야 하는 경우가 많다. => 어떤 종류의 완전 탐색도 기계적으로 잘 구현할 수 있도록 잘 익혀두기! 예) 프로그래머스 - 모의고사, 소수 찾기

Hash Key : Value 의 형태를 갖는 하나의 자료구조 ex) 해시 = 전화번호부. 이름 : key, 번호 : value 해시의 특징 : 모든 데이터 타입으로 접근이 가능하다. 해시 문제들 백준 10816 숫자 카드 2 프로그래머스 - 완주하지 못한 선수 신고 결과 받기 위장 예) 프로그래머스 - 완주하지 못한 선수 n명이 마라톤 참가. n-1명만 완주. 완주하지 못한 1명을 찾는 문제 Hash를 사용하면 아주 간단하게 해결 가능 HashMap 생성. HashMap.put("A", true); HashMap["A"] = true; 와 똑같은 동작 bool fin = hashmap.get("A"); bool fin = hashmap["A"]; 와 같은 동작 getOrDefault 함수 getOrDe..