분류 전체보기

다이나믹 프로그래밍다이나믹 프로그래밍은 하나의 문제를 단 한 번만 풀도록 하는 것이 핵심입니다. 어떤 특정 범위까지의 값을 구한다고 할 때, 그것을 하위나 상위 등 다른 범위의 값을 이용하여 효율적으로 푸는 알고리즘이 바로 다이나믹 프로그래밍, 혹은 동적 계획법입니다. 현재 주어진 문제를 더 작은 문제로 나누어 각 부분 문제의 값을 계산하고, 최종적인 결과 값을 도출한다는 점에서 분할 정복 알고리즘과 비슷하지만, 명백한 차이점이 있습니다. 다이나믹 프로그래밍 vs 분할 정복 알고리즘다이나믹 프로그래밍은 분할 정복 알고리즘과 다르게 동일한 계산을 할 경우 계산한 결과를 미리 저장해 두었다가, 필요한 경우 꺼내서 사용합니다. 즉 메모리라는 공간 자원을 활용하여 불필요한 계산을 줄여 계산에 소요되는 시간을 줄..

위상정렬위상 정렬이란 방향그래프(Directed Graph)에서 순서가 정해져 있는 작업을 수행할 경우, 순서를 결정하기 위해 사용하는 정렬 알고리즘입니다. O(V+E)의 시간복잡도를 가집니다.  우리가 등교를 위해 옷을 입는 과정을 생각해 봅시다. 셔츠를 먼저 입을 수도, 양말을 먼저 신을 수도, 속옷을 먼저 입을 수도 있지만,신발을 신고 양말을 신거나 바지를 입고 속옷을 입을 수는 없습니다. 이처럼 순서가 정해져 있는 작업을 수행할 경우 올바른 순서를 도출해 내기 위해 위상정렬을 사용합니다. 위상정렬을 사용하기 위한 조건- 그래프가 비순환 방향 그래프(DAG: Directed Acyclic Graph)여야 합니다. DAG는 모든 노드에 대해 어떤 노드로부터 다른 노드로의 경로가 유일하며, 다시 출발점..

신장 트리(Spanning Tree)신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 연결하는 트리입니다. 신장 트리의 속성- N개의 정점이 있는 그래프의 경우 해당 그래프에 대한 신장 트리의 간선 개수는 N-1개입니다.- 연결이 끊어진 그래프에는 신장 트리가 없습니다.- 신장 트리에는 순환이 없습니다. 하나의 정점에서 출발하여 해당 정점으로 다시 이어지는 간선이 존재한다면 신장 트리가 아닙니다. 최소 신장 트리(MST, Minimum Spanning Tree)그래프 내에 존재하는 Spanning Tree 중 사용 간선들의 가중치 합이 최소가 되는 트리를 MST(Minimum Spanning Tree), 최소 신장 트리라고 합니다. 최소 신장 트리의 속성- N개로 이루어진 그래프라면 반드시..

1.1 정보는 비트와 컨텍스트로 이루어진다컴퓨터 시스템은 소프트웨어와 하드웨어로 구성됩니다. 텍스트 파일: 아스키 문자로만 이루어진 파일바이너리 파일: 제외한 다른 모든 파일 프로그래머가 작성한 소스파일은 컴파일 과정을 거쳐서 0과 1로 표시되는 비트들로 변환됩니다. 바이트(Byte)는 8비트로 구성됩니다. 프로그램 내의 문자 데이터들은 아스키 표준(ASCII)을 사용해서 표시됩니다. 아스키 코드: 각 문자열을 이진수로 표현하고 예시로 'a' = 97, byte 값: 01100001, 저장크기: 1byte(8bit) 아스키 코드는 7 bit 아스키, 8 bit 확장 아스키로 나뉩니다. 7 bit는 알파벳, 기본 기호 다루고 다양한 언어, 특수기호를 다루기 위해 8 bit 아스키/확장 인코딩이 도입되었습니..

크래프톤 정글에서의 1주 차가 끝났습니다! 이제 몸은 정글이라는 곳에 슬슬 적응해 가는 것 같은데.. 마음은 아닌 것 같네요.. 솔직하게 말하면 집에 가고 싶습니다..ㅠ 집에서 엄마가 해주는 밥, 집이 너무 그립네요..ㅠ 전 제가 고향을 이렇게 사랑하는 사람인 줄 몰랐어요. 1주 차에 많은 일이 있었지만 굵직굵직한 큰 이벤트로 나누어보면 총 2가지가 있었습니다. 1. 퀴즈 및 시험📝 2. 크래프톤 장병규 의장님과의 티타임🫖 이번 주차에 모든 것 다 제쳐두고 퀴즈와 시험을 1순위로 두고 공부를 하면서 진행했었습니다. 매주 있는 시험이고, 석차가 나오는 것도 아니고 시험 못 친다고 그 누구도 뭐라 하지 않지만, 저도 그렇고 다른 분들 모두 시험 준비를 열심히 하며 1주 차를 보냈습니다. 누가 한국인들 아니랄..

복잡도란 알고리즘의 효율성을 평가하는 중요한 척도입니다. 오늘 설명할 시간복잡도는 알고리즘이 수행되는데 소요되는 시간, 공간복잡도는 알고리즘이 수행되는데 소요되는 메모리의 양을 의미합니다. 사실 요즘 시대에 공간복잡도는 시간복잡도만큼 그 중요도가 높지 않습니다. 무어의 법칙이라는 게 있죠? (반도체 메모리의 용량은 1년지 지날 때마다 2배씩 증가한다.) 현시대에 컴퓨터의 메모리 기술이 급속도로 성장함에 따라 알고리즘에서의 메모리 사용 효율성인 공간복잡도의 중요도는 과거에 비해 많이 낮아졌습니다. 시간 복잡도(Time Complexity)시간 복잡도는 알고리즘이 입력 크기 n에 따라 얼마나 오래 걸리는지를 측정하는 척도입니다. 보통은 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 변하는지를 나타..