📕Backtracking이란? 영어 사전에서 backtrack이란 단어를 검색하면 나오는 결과이다. '(방금 왔던 길을) 되짚어 가다' 미로찾기를 한다고 생각해보자, 두갈래 갈림길이 나왔을때 왼쪽으로 가다가 막히면 어떻게 하는가? 다시 갈림길이 있는 곳으로 돌아와서 오른쪽으로 가지 않겠는가? 이것이 바로 백트래킹의 핵심이다. 길이 막혔을 경우 다시 돌아가는 것을 원하는 결과가 나올때까지 반복하는 것이 바로 백트래킹이다. 간간단한 예제를 살펴보자. S = {W1 = 5, W2 = 6, W3 = 10, W4 = 11, W5 = 16} and W = 21 S에 있는 수를 뽑아 W를 만드려고 한다. 이때 생기는 조합은 여러가지가 있다. {W1, W2, W3} , {W1, W5}, {W3, W4} = 21 이러한..

📕Huffman code 란?압축은 자료의 크기를 줄이기 위해서 사용된다. 그리고 이 압축을 하는 방식에 따라서 압축된 파일의 용량이 달라질 수 있는데, 그 중 Huffman code는 문자의 출현 빈도에 따라서 다른 길이를 사용하여 압축하는 알고리즘이다. Huffman code도 그리디 알고리즘의 일종이다. 허프만코드는 데이터를 매우 효율적으로 압축하는데, 20~90%의 용량을 아낄 수 있다. 허프만 코드는 prefix-free* codes로 표현된다. prefix-free코드는 어떠한 문자라도 항상 최적의 데이터 압축을 보장한다. (*prefix codes가 표준 표기이긴 하지만, prefix-free codes가 좀 더 맞는 이름이기 때문에 여기에서는 prefix-free codes로 표기하겠다) ..

📕그리디 알고리즘이란 ? 그리디 알고리즘은 코딩테스트에 자주 나오는 단골 문제이면서, 알고리즘 문제에 널리 사용되는 알고리즘이다. 그리디 알고리즘은 무엇일까? 그리디 알고리즘의 정의는 다음과 같이 말할 수 있다. "A greedy algorithm always makes the choice that looks best at the moment" 그리디 알고리즘은 '지금 당장 좋은 것을 고르는 방법'이다. 즉, 선택의 순간이 왔을 그때, 가장 좋은 것을 선택하는 것이다. ('Greedy'라는 이름을 보더라도 탐욕적인 것을 알 수 있다.) 📕 Greedy algorithm vs Dynamic programming 그리디 알고리즘과 다이나믹 프로그래밍을 언뜻 보면 비슷하다고 생각할 수 있다. 절차적으로 해결법..

📕 큐란?? 자료구조 큐를 이해하기 위해서는 영어 queue가 무엇인지를 알면 역시 이해하기 쉽다.Queue는 명사 '줄' 이라는 뜻이 있다. 그렇다면 대체 왜 "줄"을 자료구조 컨테이너의 이름으로 정했을까?그건 줄을 서는 상황을 생각해보면 알 수 있다.놀이공원에 들어가기 위해서 줄을 선다고 생각해보자. 그렇다면 가장 먼저 입장하는 사람은 누구겠는가?당연히 줄 가장 앞에 있는 사람일 것이다. 반대로 가장 늦게 입장하는 사람은 줄 마지막에 서 있는 사람일 것이다. 아래는 큐를 그린 그림이다.📕 큐의 특징 큐 == 줄 이기 때문에 생기는 특징이 있다.바로 선입선출, First In First Out이다. 그렇기 때문에, pop 함수를 호출하면, 가장 앞에 있는 element가 큐에서 삭제되며,push..

📕 스택이란?? 자료구조 스택을 이해하기 위해서는 영어 stack이 무엇인지를 알면 이해가 쉽다.stack은 '무더기', '쌓아놓은 더미' 등을 가리키는 명사의 뜻과 '쌓다'라는 동사의 뜻이 있다.여기서 우리가 눈여겨봐야 할 것은 '쌓는다'라는 특성이다. 📕 스택의 특징 어떠한 것을 '쌓는' 것이기 때문에 생기는 특성이 있는데, 바로 후입선출(LIFO)즉, 먼저 들어간 것이 나중에 나오는 특성이다.간단한 예시로 책 더미를 생각해보자.책을 위로 점점 쌓고난 후, 맨 밑에 있는 책을 꺼내기 보기 위해서는 그 책위로 쌓여있는 책을 다 빼낸 후에야 가능할 것이다.반대로, 맨 마지막에 쌓은 책의 경우 가장 위에 있기 때문에 제일 먼저 꺼낼 수 있을 것이다.그렇기 때문에 후입선출, Last In First ..