기록하는 습관 "기습"

투 포인터투 포인터(Two Pointers) 기법은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 알고리즘 설계 방법이다. 이 기법은 일반적으로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 부분 배열이나 쌍을 찾는 문제를 풀 때 자주 활용된다.투 포인터는 주로 다음과 같은 상황에서 유용하다:- 두 요소의 합이나 곱과 관련된 조건을 만족하는 쌍을 찾는 경우- 특정 조건을 만족하는 부분 배열의 길이, 개수 등을 구하는 경우- 슬라이딩 윈도우와 함께 사용하여 효율적으로 부분합을 계산하는 경우투 포인터의 동작 원리초기화: 두 개의 포인터를 각각 배열의 시작과 끝에 두거나, 특정 조건에 맞게 시작점을 설정한다.조건 검토 및 이동: 조건에 따라 포인터를 이동시킨다..

분할정복분할 정복은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 해결한 뒤 결과를 결합하여 원래 문제의 해를 구하는 알고리즘 설계 기법이다.이 방법은 재귀적 접근을 기반으로 하며, 특정 문제를 풀기 위해 문제를 반복적으로 쪼개어 더 단순한 형태로 만들고 이를 조합하여 해를 도출한다. 이 과정은 아래 세 단계로 구성된다:분할(Divide):원래 문제를 더 작은 부분 문제로 분할한다.일반적으로 이 단계는 입력 데이터를 나누거나, 문제의 범위를 축소하는 과정을 포함한다.정복(Conquer):나뉜 부분 문제를 재귀적으로 해결한다.하위 문제의 크기가 충분히 작아지면(예: 크기가 1인 경우), 직접 해결(기저 사례)한다.결합(Combine):각 부분 문제의 결과를 결합하여 원래 문제의 해를 구한다.결합 과..

누적합누적합(Cumulative Sum)은 배열이나 리스트의 특정 구간 합을 빠르게 계산하기 위해 사용하는 알고리즘 기법이다. 일반적으로 대량의 데이터에서 특정 구간의 합을 반복적으로 구해야 하는 경우, 단순히 반복문을 이용해 매번 합을 계산하는 것은 비효율적일 수 있다. 이때, 누적합 배열을 활용하면 원하는 구간의 합을 상수 시간 내에 구할 수 있다. 누적합의 원리누적합의 기본 원리는 배열의 각 위치까지의 값을 순차적으로 더해 새로운 배열을 생성하는 것이다. 이를 통해 배열의 특정 구간 합을 빠르게 계산할 수 있다. 예를 들어, 배열의 i번째 위치까지의 누적합은 원본 배열의 0번째 인덱스부터 i번째 인덱스까지의 합을 저장하는 형태다.누적합 배열을 S라고 할 때, 원본 배열 A에서 구간 [i, j]의 합..

동적 프로그래밍동적 프로그래밍에 대해서 다시금 공부하고 있다. 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제들로 나누어 해결한 후, 그 결과를 저장하여 재사용함으로써 문제 해결의 효율성을 높이는 기법이다. 이는 주로 하위 문제가 반복해서 나타나는 경우에 사용되며, 각 하위 문제의 결과를 기록(memoization)하거나 테이블 형식으로 정리하여 중복 계산을 방지한다. DP는 최적화 문제에서 자주 사용되며, 두 가지 주요 접근 방식이 있다: 상향식(Bottom-Up)과 하향식(Top-Down). 단순히 말하자면, 동적 프로그래밍은 "이전에 계산한 값을 저장해 두었다가 필요할 때 재사용하는 방법"이다. 이는 중복 계산을 줄이고 문제를 더 빠르게 해결할 수 있..

백트래킹이란?백트래킹은 해를 찾는 과정에서 여러 가능성을 탐색하다가, 특정 경로가 잘못되었음을 알게 되면 되돌아가서 다른 경로를 시도하는 문제 해결 기법이다. 모든 가능한 경우의 수를 탐색하지만, 가지치기(pruning)를 통해 비효율적인 경로를 배제하여 효율성을 높인다. 다시 말해, 완전 탐색(브루트 포스)의 개선된 형태라 할 수 있다. 단순히 요약하자면, 백트래킹은 "이 길이 아닌 것 같을 때 원래 왔던 길로 되돌아가서 다른 길을 가보는 것"이다. 이는 특성으로 알 수 있듯이 대부분 DFS로 구현할 수 있다.  백트래킹의 예시이번 예시는 9663번 N-Queen 문제를 기준으로 하겠다. 먼저 구현 문제를 보자.  문제 자체는 백트래킹을 잘 활용해야 풀 수 있다. 나는 문제를 다 읽고 2차원 배열로 풀..

개요코테 준비를 시작했는데 너무 부족함을 느끼고 있다. 나오는 문제는 막힘없이 풀 수 있는 정도가 되고 싶다. 왜 이렇게 해야 하는가에 대한 이유는 다음 글을 읽어보길 바란다. 도움이 되는 내용도 많다! https://yozm.wishket.com/magazine/detail/2755/ 개발자를 위한 실전 ‘코딩테스트’ 준비 팁 | 요즘IT개발자라면 누구나 ‘코딩테스트’를 준비해 본 경험이 있을 겁니다. 코딩테스트는 여러분의 두뇌가 얼마나 비상한지, 복잡하게 꼬인 문제를 얼마나 천재적인 발상으로 해결할 수 있는지 시험yozm.wishket.com 그래서 나는 이전에 강의로 배웠던 내용을 다시 공부하거나 부족한 부분을 채우려고 한다. 처음은 DFS와 BFS로 스타트를 끊고자 한다. 설명은 백준의 1260번..

NP 완비 NP-complete 요약하자면, 현실적인 시간 내에 답을 얻을 수 있는 해법이 존재하는 것을 말한다. 여기서 이제까지 다룬 모든 알고리즘은 다항식 시간, 즉 입력 크기가 n일 때 최악의 경우에도 수행시간이 O(n^k)의 시간이 걸리는 알고리즘들이었다. 하지만 모든 문제를 컴퓨터로 다항식 시간에 풀 수 있지 않다. 정확히는 풀 수 있으나 현실적인 시간 내에 풀 수 없는 문제가 있고, 아무리 시간이 주어져도 풀 수 없는 문제가 존재한다. 간혹 들어보는 표현 중에 "슈퍼 컴퓨터로 몇 십년 이상 걸리는 문제"가 그것이다. P 는 polynomial이란 의미로, 문제가 주어졌을 때, 대답을 다항식 시간에 할 수 있는 문제이다. NP는 yes라는 근거만 주어지면 다항식 시간에 풀 수 있는 문제이다. N..

원시적인 naive 매칭 문자열 하나하나에 패턴문자열을 대조해보는 방법으로, O(mn)의 수행시간을 갖는다. 다만 이전에 비교했던 불일치 건에 대한 사실을 전혀 활용하지 못하기에 비효율적이다. Rabin-Karp 알고리즘 문자열 패턴을 수치화하여 문자열 비교를 수치비교로 대신한다. 수치화 방법은 다음과 같다. 가능한 문자 집합의 크기에 따라 진수가 결정된다. 만약 A = {a,b,c,d,e}이면, |A| = 5이다. 여기서 문자열 ad를 수치화한다고 했을 때 수치는 다음과 같다. 0*5^1 + 3*5^0 = 4 (4가 문자열 ad의 수치화, 맨앞의 숫자는 알파벳의 순서) 문자열 수치화로 문자열 매칭을 수행하려면 다음과 같은 문제점을 해결해야 한다. 수치화 작업의 부담 보통 하나의 문자열들을 일일이 계산하..

그리디 알고리즘 눈앞의 이익만 우선 추구하는 알고리즘을 총칭한다. 최적해를 찾을 수 있으면 찾지만, 없다면 그런대로 괜찮은 해를 찾아내는 것이 목표다. 이 때문에 대부분 최적해를 보장하지 못하지만 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘으로 최적해가 보장되는 않는 예는 다음과 같다. 이진트리 최적합 경로 찾기 동전 바꾸기 배낭 문제 최적해가 보장되는 예는 다음과 같다. 최소 신장 트리 : prim, kruskal 최단 경로 : 다익스트라 회의실 배정 문제 여기서 몇가지를 뽑아서 설명하겠다. 동전 바꾸기 동전을 모아서 특정 액수를 만들되 동전의 개수를 최소로 하는 문제다. 다만 이 문제는 모든 동전의 액면이 일반적인 화폐의 유통과 같았을 때, 즉 500원, 100원, 50원, 10원일 때 그..

그래프는 정점 vertex와 간선 edge로 사물과 현상을 표현한 것이다. 이전에 다뤘기에 세세한 것은 넘어가겠다. 그래프의 표현 그래프를 표현하는 방법 중에는 인접 행렬, 인접 리스트, 인접 배열, 인접 해시테이블이 있다. 인접행렬은 간선 수 이상의 공간을 차지하고, 인접리스트는 특정 간선 존재 여부를 검사하는 데에 오래 걸린다. 이 두 단점을 커버할 수 있는 표현은 인접 배열이다. 인접배열은 정점 N개일 때 N개의 인접배열로 표현하는 것이다. 즉, 인접한 정점의 갯수만큼 배열을 또 생성한다. 인접리스트를 배열로 표현한다면 이해가 쉬울 것이다. 이때 간선 존재 여부의 수행시간은 O(log k)이다. 인접 해시테이블은 각 정점마다 인접배열을 두는 대신 하나의 해시 테이블을 사용하는 것이다. 인접한 정점이..