🥬 상추의 공간

이번에 글또에서 코드트리와 함께 콜라보해서 '코드트리 x 글또 블로그 챌린지'가 열렸다. 글또 회원 중 챌린지에 참여하는 사람 한에서 코드트리를 한 달간 무료로 이용할 수 있게 되어, 한 달 동안 사용해보고 느낀점을 써보려고 한다. (사실 나는 한 달이라고 하기엔 무리가 있고, 해외 연수 끝나고 좀 늦게 시작해서 2주정도 사용한 것 같다.) 일단 나는 이제 막 본격적으로 코딩테스트 공부를 시작하는 대학 4학년 되는 전공생이다. 코테 입문자라고 칭했지만, 예전부터 조금씩은 풀었어서(아주 조금) 백준은 실버5, 프로그래머스는 Lv1 문제 정도를 풀긴 한다. 내가 제대로 풀고 있는지 잘 모르겠고, 공부법, 인강, 플랫폼 등을 찾다가 우선순위에 밀려 지금까지 백준 실버 5에 머무르고 있는 것이다. 사실 코드트리..

스택 마지막에 들어간 데이터가 먼저 나가는 자료구조다. LIFO(Last Input First Out) 구조를 가진다. 실생활 예로는 페이지 뒤로가기, 되돌리기(Ctrl + Z), 책상에 쌓인 책이 있다. 큐 먼저 들어간 데이터가 먼저 나가는 자료구조다. FIFO(First Input First Out) 구조를 가진다. 실생활 예로는 줄을 서는 것이 있다.

슬라이딩 윈도우란? 슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 유사하게 부분 배열들을 활용하는 알고리즘이다. 투포인터와 다른 점은 부분 배열의 길이(크기)가 고정적이다. 그래서 포인터 변수가 2개일 필요가 없다. 이름 그대로 고정적인 너비를 가진 창문을 두고 옆으로 한칸씩 이동하며 값을 구하는 방법이다. 예를들어, N개의 원소를 갖는 배열이 있다. 이때 W의 너비를 갖는 창문이 있다. 너비가 3인 창문을 제일 왼쪽에 배치하고, 창문을 왼쪽에서 시작하여 한 칸씩 오른쪽으로 이동한다. 매 순간 창문 안에서의 정보를 활용해 유추해서 값을 구한다. 즉, 같은 너비의 연속 구간들을 연속적으로 처리할 때 주로 사용되는 테크닉이다. 인접한 구간들 사이에 겹치는 정보를 최대한 활용하는 것이 포인트다. 관련 문제 ..

투 포인터란? 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 여기서 포인터는 C언어의 포인터가 아니라 작업을 처리하기 위해 생성한 변수이다. 포인터라는 변수를 두개를 선언해서 투 포인터라고 부른다. 이분탐색 문제를 투 포인터로도 해결 할 수 있다. 완전 탐색 알고리즘으로 하면 O(N^2)의 수행시간이 나오는데, 투포인터로 시간복잡도를 O(N)으로 줄일 수 있다. 예시 문제: N개의 자연수로 구성된 수열이 있을 때, 합이 M인 부분 연속 수열의 개수 구하기. 수행 제한 시간은 O(N) 투 포인터로 문제 해결하는 방법 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다. 현재 부분 합이 M과 같다면,..

완전 탐색이란? 완전 탐색은 브루트 포스라고도 불리는데, brute force를 그대로 해석해보면 '난폭한 힘' 이다. 즉, 브루트 포스는 머리는 쓰지 않고 무식하게 모든 경우의 수를 다 해보는 방법이다. 실생활 예를 들어보면, 비밀번호를 맞춰야 하는데 범위가 0000~9999라면 0000부터 하나하나 다 시도해보는 것이다. '생일이지 않을까?'라고 유추하지 않고 말이다. 문제를 풀 때 기준점을 잡지 못할 때 주로 접근한다고 한다. 종류 순열, 백트래킹(재귀함수), BFS 가 있다. 보통 for, while, 재귀함수를 이용해 풀이한다.