슬라이딩 윈도우 알고리즘 이름만 들어도 참 길다. 하지만, 그 이름 자체에 모든 의미가 내포되어있다. 슬라이딩 윈도우 기법이란 2개의 포인터로 범위를 지정한 후에 그 범위를 유지한 채로 이동하며 문제를 해결한다. 투 포인터 알고리즘과 비슷하고 그 사용법 또한 어렵지 않다. 그렇다면 왜 사용하는가? 개인적으로는 탐색에 있어 좋은 효율을 보여주기 위해. 그리고 사고의 단순화를 위해서라고 생각이 든다. 슬라이딩 윈도우 기법은 쉽지만, 무엇과 어떻게 활용할 수 있냐에 따라 그 난이도가 달라진다. 아래 예시 코드로 슬라이딩 윈도우 기법의 예시를 살펴보자. 일반적인 슬라이딩 윈도우 기법 해당 문제는 백준 12891번 문제로, 일반적으로 슬라이딩 윈도우 기법을 사용하는 경우다. 12891번: DNA 비밀번호 평소에 ..
투 포인터 알고리즘? 정렬되어 있는 배열에서 크기를 비교하기 위해서 사용되는 알고리즘이다. 이게 왜 좋냐면, 투 포인터 알고리즘 자체가 O(logN)을 보장하기 때문이다. 즉, 시간 초과를 막기 위한 효율적인 수단 중 하나이다. 일반적인 자바 정렬의 경우(Arrays.sort())에는 O(nlogN)의 시간 복잡도를 가지고 있으므로, 정렬과 투 포인터를 사용할 만한 상황인 지 점검할 필요가 있다. 1. 정렬이 되어 있는가? 투 포인터는 정렬된 경우에 가장 효율적이다. 만약 되어있지 않다면, 정렬 알고리즘을 적용시킨 시간 복잡도를 고려해야 한다. 2. 문제에서 크기를 비교하는 것을 요하는가? 위 조건을 만족시킨다고 했을 때, 크기를 서로 비교하는 문제를 해결하는데 효율적이다. 예시 문제 적용 방법 백준 1..
WebServer와 WAS란 무엇인가 WebServer와 WAS의 차이를 알기 위해선, 정적 페이지와 동적 페이지의 차이를 알아야 한다. 쉽게 말해 페이지가 동적으로 바뀌냐 바뀌지 않느냐의 차이다. 1) Static Pages(정적 페이지) Web Server는 파일 경로 이름을 받고 file contents를 반환한다. 이 file은 html, css, js, image와 같이 컴퓨터에 저장되어 있다. 항상 동일한 페이지를 반환한다. 2) Dynamic Pages(동적 페이지) 인자의 내용에 따라 Contents를 반환한다. 중요한 것은, 웹 서버에 의해서 실행되는 프로그램을 통해 만들어진 결과물이라는 것. Web Server와 WAS의 차이가 무엇이지를 파악하기 위해선, 각각의 정의에 대해 알아 둘 ..
typedef와 구조체 typedef : 타입 이름을 사용자가 정해준다 어떤 경우든 이름이 길어지면 알아보기 힘들기 마련이다. 구조체를 사용할 때도 마찬가지다. 구조체 타입을 알려주고 이름을 지어주어 사용해야 한다. 이는 숏코딩 중독자들인 개발자들 눈에 썩 좋지 않았나보다. 그래서 구조체의 정의와 사용을 쉽게 해보려고 도입한 것이 typedef이다. 사용법은 다음과 같은 방법들이 있다. struct point { int xpos; int ypos; }; typedef struct point Point Point p; 위처럼 작성한다면 변수 선언이 짧아진다는 장점이 있다. typedef struct point { int xpos; int ypos; } Point; Point p; 더 쉽게 사용하기 위한 것..
이전 포스팅에서 스택 프레임 내에서 사라지는 지역 변수를 보존하기 위한 방법으로 동적 메모리를 사용한다고 했었다. 그리고 동적 메모리를 사용하려면 스택과 힙을 알아야 한다. 메모리 모델 : Stack vs. Heap Stack은 무엇을 포함하는 가? 지역 변수, 인자, 리턴 주소 Heap이란 무엇인가? 변수와 비슷하지만 변수 이름이 없는 메모리 조각 (동적 변수, 무명 변수라고 부른다.) Heap에 있는 동적 변수는 함수와 독립적으로 존재한다. 이는 전역 변수와 유사하다. Heap에 있는 동적 변수는 동적으로 생성과 제거가 가능하다. 이는 전역 변수와 다른 점이다. 따라서 동적으로 생성하고 제거하기 하기위한 함수가 존재한다. 생성 함수 malloc(), new() 제거 함수 free() Stack 지역 ..
포인터 배열, 배열 포인터 혼용하여 쓰다보면 이게 정확히 무슨 개념인지 스스로 깨닫지 못하고 사용하는 경우가 많다. 한번 이해해보자. 포인터 배열이란? 포인터 배열이란 각 배열의 요소가 포인터(자료형이 주소)인 것을 뜻한다. 다음 예시를 보자. char * strArr[3] = { "cat", "dog", "bird" }; printf("%s", strArr[0]); printf("%s", strArr[1]); printf("%s", strArr[2]); strArr는 포인터 배열이다. 각 배열의 요소가 포인터이기 때문이다. 문자열이 왜 포인터인가? 이는 배열 안에 내부적으로 문자열의 시작 주소를 나타내는 포인터이기 때문이다. 포인터 배열과 더블 포인터 포인터 배열의 또 다른 표현 방법으로 더블 포인터를..
C언어에 대해 공부하다 보니 어색한 문법과 익숙하지 않은 문법들이 퍼즐처럼 다가오곤 한다. 그럼에도 가장 기본이 되는 언어이기도 하고, 분명 도움이 되는 부분도 많다. 지금부터 개인적으로 공부하며, 헷갈렸던 개념에 대해 정리보고자 한다. 자동 할당 문자열이란? 큰 따옴표로 둘러싸인 문자열이다. 단, char 배열 선언할 때 초기화 값으로 쓰이는 경우는 제외한다. char * str = "Oh String"; 위 구문 같이 문자열을 표현할 때 자동 할당 문자열이 쓰인다. 이 문자열은 변화할 수 없다(불변). 왜 불변인가? 이는 Const에 대해 이해할 필요가 있다. 포인터에 Const 선언 포인터(*)와 const는 위치에 따라 사용 의미가 다르다. 1. const int * ptr 해당 포인터를 통해 꺼..
정렬 알고리즘이란 n개의 숫자가 주어졌을 때, 이를 사용자가 지정한 기준에 따라 정렬하는 알고리즘을 뜻한다. 지금부터 어떤 알고리즘이 있는지 살펴보도록 하자. 비교 정렬(comparison sort) 비교 정렬은 배열의 원소 쌍 간의 비교를 기반으로 정렬하는 알고리즘이다. 가장 쉽게 생각할 수 있는 알고리즘이자 O(nlogn)이라는 시간 한계를 넘어서지 못한다. 이러한 비교 정렬의 종류로써 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort)이 있다. 선택 정렬 제일 먼저 선택 정렬이란? 배열에서 아직 정렬되지 않은 부분에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽 원소와 교환하..
이진 탐색 트리를 공부하기 앞서, 탐색 트리란 무엇인가? 이는 저장된 데이터에 대해 접근, 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조를 말한다. 탐색 트리의 종류는 굉장히 다양하지만, 제일 기본이고 선행되어 학습되어야 하는 부분이 바로 이진 탐색 트리이다. (그 외에 AVL트리, 2-3 트리, 2-3-4 트리, B-트리, RB-트리 등은 다른 포스팅을 참고하자) 이진 탐색 트리 이진 탐색 트리(Binary Search Tree)란, 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조를 말한다. 🤔 그렇다면 이진 탐색이란? 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법이다. 다시말해 이진 탐색 트리란, 트리 형태의 구조..
AVL 트리 AVL 트리는 트리가 한쪽으로 치우치는 것을 방지하여 트리 높이의 균형을 유지한다는 특징이 있다. 즉, 삽입이나 삭제 시에 균형이 어긋나게 되면 스스로 회전 연산을 통해 균형을 유지하는, 자체 힐링이 가능한 트리이다. 이러한 AVL 트리(a.k.a 균형 트리)를 사용하는 이유는 탐색, 삽입, 삭제 연산 시에 균일한 수행 시간 O(logN)을 보장하기 때문인데, 이는 AVL 트리의 높이와 관계가 있다. n개의 노드를 가진 AVL 트리의 높이는 O(logN)이다. AVL 트리의 정확한 정의를 알아보자. AVL 트리는 임의의 노드 x에 대해 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리이다. AVL 트리의 회전 연산 회전 연산의 경우 AVL트리는 회전 ..
