바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 안녕하세요, 재귀 파트를 시작하겠습니다. 지금 자신 있게 말할 수 있는 게 있는데 이 파트가 정말 어려울 것입니다. 라고하심 알고리즘 설명 재귀는 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다. 이러한 예시에서, 두 가지 설명방법이 존재하는데, 1번 도미노가 쓰러지면 2번 도미노가, 그리고 3번 , 4번... 1번 도미노가 쓰러진다(참), k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다(..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 알고리즘 설명 DFS : 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘. (BFS는 너비) 예시 BFS 과정에서 다른 건 다 같고, 큐가 스택으로 바뀐 것뿐이다. BFS때와 같이 예시를 보자. (0,0)부터 이어진 파란색 칸을 확인할 것이다. (0,0)을 밟은 상태에서 시작했으니, 해당칸에 표시를 남기고 스택에 넣는다. (초기세팅) 이후에는, 스택이 빌 때까지 계속 스택의 top을 빼고 해..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 알고리즘 설명 "너비"를 우선으로 방문한다. 원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 여기서 말하는 그래프는 오른쪽 그림과 같은 모양의 그래프이고, 정점과 간선으로 이루어진 자료구조이다. (내 생각) 설명 백날 듣는 것 < 예시 보고 짜보는 것 이라고 생각하기에 코드를 보자.. STL pair #include using namespace std; int main(void) {..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 덱 양쪽 끝에서 삽입과 삭제가 전부 가능하다. => 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮다. 자명함. STL deque STL deque은 독특하게도, vector랑 비슷한데, front에서도 O(1)에 추가와 제거가 가능한 느낌이 강하다. insert, erase도 있고, 인덱스로 원소에 접근도 할 수 있다. 이와 같이, STL vector에서 제공되는 기능을 STL deque에서도 다 제..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 큐 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔지만, 큐에선 먼저 들어간 원소가 먼저 나오게 된다. 상상해 보면 자명하다. 4번 성질의 이야기는 스택에서 다루었으니 생략. STL queue STL queue를 제공한다. 큐는 보통 BFS와 Flood Fill을 할 때 쓰게 된다. #include using namespace std;..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 스택 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조. 프링글스 통을 생각하면 된다. 생각을 해보면, 자명하게 위의 모든 경우들이 이해가 된다. 성질 4번(제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능) 의 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인의 기능만 제공하는 자료구조이다. 따라서, 위 성질은 스택에서 제공하는 기능이 ..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 연결리스트 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조. 위 사진처럼, 배열은 0,1,2,3번에 사람들을 넣어두는 반면, 연결 리스트는 배열사진에서의 0번에 해당하는 사람이 1번을 기억하고, 1번이 2번을 기억하는, 구조이다. => 이렇게 되면 0번을 통해 나머지 3명이 누구인지 전부 알아낼 수 있게 된다. 연결리스트에서 k번째 원소를 찾기 위해선 O(k)의 시간..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20 알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 음 그러하다. 배열은 메모리 상에 원소를 연속하게 배치한 자료구조라서, k번째 원소의 위치를 바로 계산할 수 있다. 시작 주소에서 k칸만큼 오른쪽으로 가면 되기 때문. => 그러기에 k번째 원소를 O(1)에 확인하거나 변경할 수 있다. 배열은 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없다. 메모리 상에 데이터들이 붙어있으므로 Cache hit rate 가 높다. 메모리 상에 연속..
