다이나믹 프로그래밍(dynamic programming, DP)이란? 다이나믹 프로그래밍은(DP) 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 구하는 알고리즘 설계 기법이다. 앞에서 구했던 답을 뒤에서도 이용하고, 또 그 뒤에서도 이용할 수 있다. 쉽게 말해서는 답을 재활용하는 것이고, 같은 말로 프로그래밍 영역에서는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. DP는 구체적인 알고리즘이라기 보다는 문제해결 패러다임에 가깝다. DP는 아래와 같은 특징이 있다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 DP의 구현은 일반적으로 두 가지(탑다운 - 하향식, 바텀업 - 상향식) 방식으로 구현함 ..

그래프 순회(Graph Traversal) 그래프 순회란 그래프 탐색(Search)이라고도 불리우며, 그래프의 각 정점을 방문하는 과정을 말한다. 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversls)에는 크게 깊이 우선 탐색 DFS(Depth-First Search, DFS)과 너비 우선 탐색 BFS(Breadth-First Search, BFS) 2가지 알고리즘이 있다. 두 가지 모두 탐색 알고리즘에 해당한다. DFS는 주로 스택 또는 재귀로 구현한다. BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. 깊이 우선 탐색 - DFS(Depth-First Search, DFS) 깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고..

그래프(Graph) 비선형 자료구조인 그래프 또는 트리에서 자료를(원소) 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며, 정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부른다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있다. 즉, 연결 관계를 표현하는 자료구조라고 할 수 있다. 아래의 이미지처럼 그래프는 트리보다 더 넓은 범위라고 할 수 있다. 그래프의 종류 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph) 무방향 그래프는 간선을 통해 양방향으로 갈 수 있다. 방향 그래프는 간선의 방향이 존재하는 그래프로 한 방향으로만 갈 수 있다. 노드 사이에 양방향으로 표시된 간선은 양방향으로 통행..

1. 컴퓨터 시스템으로의 여행 컴퓨터 시스템은 하드웨어와 시스템 소프트웨어로 구성되며, 이들이 함께 작동하여 응용프로그램을 실행한다. 모든 컴퓨터 시스템들은 유사한 기능을 수행하는 유사한 하드웨어와 소프트웨어 컴포넌트를 가지고 있다. HTML 삽입 미리보기할 수 없는 소스 이들 컴포넌트들이 어떻게 동작하고, 프로그램의 성능과 정확성에 어떤 영향을 주는지 알아야 프로그램을 더 잘 개발할 수 있다고 한다. CSAPP에서 배우는 주요 내용 컴퓨터가 숫자를 표시하는 방법 때문에 생기는 이상한 숫자 에러를 피하는 방법 최신 프로세서와 메모리 시스템의 설계를 활용하는 효과적인 기법을 사용해 C 코드를 최적화하는 방법 컴파일러가 프로시저 호출을 어떻게 구현하는지 인터넷과 네트워크 소프트웨어를 감염시키는 버퍼 오버플로..

분할 정복(Divide and Conquer) 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다. 분할 정복(Divide and conquer)은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다. 대표적인 분할 정복 알고리즘으로는 병합 정렬이 있다. 위의 이미지에 보이듯이 병합 정렬은 상단에서 '분할' 하고, 중앙에서 '정복' 하고, 하단에서 '조합' 한다. 이를 좀 더 구체적으로 살펴보면 아래의 이미지와 같다. 중요 개념 정리 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합: 하위 문제에 대한 결과를 ..

오늘은 2022년 11월 7일, 크래프톤 정글 생활을 한지 15일차 크래프톤 정글에 합류하기 전에는 매일 TIL(Today I Learned)을 작성하고, 주간 회고는 입소 첫 주, 일요일을 기점으로 매주 작성하려고 했지만 당장 해결해야 할 과제들을 처리하는 것조차 버거웠다.(물론 지금도 마찬가지 ^^;;) 하지만 이런 좋은 기회를 경험하게 되면서 글로서 남기지 않으면 나중에 땅을 치고 후회할 것이기 때문에 힘을 내서 써보려고 한다!! 그리고 매주 한 번씩 회고록을 통해 자기 스스로를 점검하는 시간을 가져볼 수 있다는 점에서 가치가 있을 것 같다. WEEK00 주 차는 첫날 입소하자마자 팀 배정이 이루어지고, 팀 프로젝트를 이어나갔는데 굉장히 험난했다^^ (실제 정글에 가서도 마찬가지로 1일 차라고 쉬는..