이왕 발 디딘 이승, 원없이 즐겨야하지 않겠소?

완전탐색 (Brute-Force) BP라고 불리는 완전탐색은 단어 그래로 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 강력한 방식이지만, 시간은 최대로 들어간다. 예를들어 비밀번호가 4자리이고 숫자로만 이루어져 있다면, 0 ~ 9999까지 다 해보면된다. 경우의 수는 10,000가지이다. 만약 한 숫자당 1초가 걸린다고 하면 10,000초 = 2.7시간정도가 걸린다. 따라서 완전탐색을 풀기위해서는 대표적으로 4가지를 생각해볼 수 있다. for문 사용 순열, 조합 사용 재귀함수 사용 비트마스크 사용 2309번 일곱 난쟁이 조합을 이용해서 풀면된다. 1476번 날짜 계산 나머지를 이용 14500번 테트로미노 노가다 문제... 1966번 프린터 큐 큐 개념도 연습할 수 있다. 2231번 분해합 순열(..

Study/Algorithm 2022. 3. 19. 23:07

동적 계획법(Dynamic Programming) 정리 큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법입니다. DP 속성 Overlapping Subproblem (부분 문제가 겹친다.) Optimal Substructure (최적 부분 구조) Overlapping Subproblem 대표적인 예로 피보나치 수를 들 수 있다. Fn = Fn-1 + Fn-2 여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 Fn-1, Fn-2를 작은 문제로 나눈다고 생각하면 된다. Optimal Substructure 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 위의 예에서 작은 문제로 쪼갠 우측항의 Fn-1 + Fn-2로 큰 문제인 Fn의 값을 구할 수 ..

Study/Algorithm 2022. 3. 19. 23:07

1. 프로세스(Process)와 스레드(Thread) 먼저, 프로세스(process)란 무엇일까? 프로세스는 단순하게 말하면 일을 처리하는 일련의 과정을 말합니다. 예를 들어, 아침에 일어나 학교에 가는 과정도 하나의 프로세스라고 할 수 있습니다. 아침에 일어나서 씻고 준비를 한다. 역으로 걸어간다 지하철을 탄다 역에서 내려 학교로 간다. 💡 컴퓨터에게는 프로세스란 운영체제로부터 시스템 자원을 할당받는 작업의 단위 컴퓨터에서 연속적으로 실행되고 있는 프로그램 메모리에 올라와 실행되고 있는 프로그램의 인스턴스를 말합니다. 💡 하나의 프로세스는 크게 코드영역(code), 데이터 영역(date), 스택 영역(stack), 힙 영역(heap) 4가지로 이루어져 있습니다. Code : 코드 자체를 구성하는 메모리..

Study/Algorithm 2022. 3. 19. 23:06

1. 프로세스(Process)와 스레드(Thread) 먼저, 프로세스(process)란 무엇일까? 프로세스는 단순하게 말하면 일을 처리하는 일련의 과정을 말합니다. 예를 들어, 아침에 일어나 학교에 가는 과정도 하나의 프로세스라고 할 수 있습니다. 아침에 일어나서 씻고 준비를 한다. 역으로 걸어간다 지하철을 탄다 역에서 내려 학교로 간다. 💡 컴퓨터에게는 프로세스란 운영체제로부터 시스템 자원을 할당받는 작업의 단위 컴퓨터에서 연속적으로 실행되고 있는 프로그램 메모리에 올라와 실행되고 있는 프로그램의 인스턴스를 말합니다. 💡 하나의 프로세스는 크게 코드영역(code), 데이터 영역(date), 스택 영역(stack), 힙 영역(heap) 4가지로 이루어져 있습니다. Code : 코드 자체를 구성하는 메모리..

Study/Algorithm 2022. 3. 19. 23:01

스택 (STACK)이란? 📌 스택의 개념 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 📌 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자..

Study/Algorithm 2022. 3. 19. 23:00

래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 📌여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다. 그래프와 트리의 차이가 궁금하다면? 👇🏻 큰 특징만 말하자면, 그래프 중에서 방향성이 있는 비순환 그래프 를 트리라고 말합니다. 1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 💡 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분..

Study/Algorithm 2022. 3. 19. 22:58

정렬이 필요할때마다 직접 만들어서 사용할수도 있겠지만 매번 만들어서 사용하기는 번거롭습니다. 간편하게 정렬을 하고 싶다면 직접구현보다는 헤더를 include하여 그 안에 있는 sort()함수를 사용하시면 간편하게 정렬을 할 수 있습니다. sort() 함수는 C++ STL에서 제공하는 함수로써 각종 알고리즘 문제를 풀 때도 활용할 수 있어 자주 쓰이는데, 이 함수의 시간 복잡도는 nlogn입니다. 이 함수는 intro sort라는 정렬 방식을 바탕으로 구현되어 있는데 이 방식은 quick sort를 기반으로 heap sort와 insertion sort를 섞은 방식으로 최악의 경우 n^2의 시간 복잡도를 가지는 quick sort와는 달리, 최악의 경우에도 nlogn을 보장하는 정렬 알고리즘입니다. 배열의..

Study/Algorithm 2022. 2. 26. 20:49

Stack이란? 자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띠는 자료구조입니다. 이 방식이 Stack의 가장 큰 특징이자 스택을 사용하는 이유라고 할 수 있습니다. Stack은 C++ 표준 라이브러리(Standard Template Library)에 있는 정의되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하시면 편리합니다. Stack의 특징 1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조 2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 ..

Study/Algorithm 2022. 2. 26. 20:46