DailyStudyNote

List 1 - Brute force, Greedy, 순열, Sort(정렬) 강의 정리(필요하다고 생각되어지는 부분) 문제풀이 정리 Exhaustive Search 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열하고 확인하는 기법을 의미한다. → Brute-force 혹은 Generate-and-Test 기법이라고도 부른다. → 모든 경우의 수를 테스트 한 후 최종 해법을 도출 하므로 수행 속도는 느릴 수 있어도 해답을 찾아내지 못할 확률이 적다. → 주어진 문제를 풀 때, 우선 완전 탐색으로 해답을 도출한 후 성능 개선을 위하여 다른 알고리즘을 사용하여 해답을 확인하는 것이 이상적인 접근 방법이다. 예시 문) Baby Gin 6개의 숫자를 입력 받아 선택된 3개의 숫자가 연속된 숫자(run) 혹..

List 1 강의 정리(필요하다고 생각되어지는 부분) 문제풀이 정리 리스트(List) 1. 시퀀스 자료형(Sequence types) 파이썬(Python)에서는 리스트(List), 튜플(Tuple), range, 문자열(String) 처럼 값이 연속적으로 이어지는 자료형을 시퀀스 자료형(Sequence types)라고 한다. [시퀀스 자료형의 특징] 데이터를 순서대로 하나씩 나열하여 나타낸 데이터 구조이므로 특정 위치의 데이터를 가리킬 수 있다. 시퀀스 자료형으로 만든 객체를 시퀀스 객체라고 하며 시퀀스 객체에 들어있는 각 값을 요소(Element)라고 한다. [시퀀스 자료형의 활용] (1) 특정 값이 있는지 확인 하기 → (값) in (시퀀스 객체) → (값) not in (시퀀스 객체) >>> a =..

힙(Heaps) 힙(Heap) 이란 ? 완전 이진 트리(Complete Binary Tree)로 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다. 최대 힙(Max heap) 원소 삭제 1. 루트 노드 제거: → Max heap의 경우 최대 값 제거 → Min heap의 경우 최소 값 제거 2. 트리의 마지막 자리 노드를 임시로 루트 노드 자리에 배치 3. 자식 노드들 과의 값 비교 하며 아래로 이동 → 자식 노드들 중 더 큰 값 기준으로 이동 최대 힙(Max heap) 원소 삭제 - ..

힙(Heap) 힙(Heap) 완전 이진 트리의 일종이며 여러 값 중 최대 값과 최소 값을 빠르게 찾아내도록 만들어진 자료구조이다. 이진 탐색 트리가 중복 값을 허용하지 않는 것과 달리 힙 트리는 중복된 값을 허용한다. 힙(Heap) 종류 [최대 힙(Max heap)] 부모 노드이 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다. [최소 힙(min heap)] 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다. 구현 힙은 배열을 사용하여 구현하게 된다. 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용하지 않는다. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 부모 노드와 자식 노드의 관계 왼쪽 자식 index = (부모 index)..

리팩토링(Refactoring) 과 시큐어 코딩(Secure Coding) 리팩토링(Refactoring) 이란 외부 동작을 바꾸지 않으면서 내부 구조를 개선하는 방법이다. 이 과정은 코드를 쉽게 이해하고 유지보수를 좋게 하는 것에 초점이 맞춰져야 한다. 가깝게 볼 때 클린 코드와 리팩토링의 차이가 별로 없어 보이지만 클린코드는 단순하게 가독성을 높이기 위한 작업인 반면 리팩토링은 클린 코드를 포함하여 유지보수를 위한 코드의 개선이라고 볼 수 있다. 클린 코드와 같은 부분은 설계단계에서 잘 이루어져 있는 것이 중요하고, 리팩토링은 결과물이 나온 이후 수정이나 추가 작업이 진행될 때 개선해 나가는 단계이다. 리팩토링(Refactoring) 목적 리팩토링의 목적은 소프트웨어를 더 이해하기 쉽고 수정하기 쉽게..

클린 코드(Clean Code) 클린 코드(Clean Code) 란 읽기 쉬운 코드가 "클린 코드(Clean Code)" 이다. 클린 코드의 가장 중요한 요소는 가독성이다. 즉, 모든 팀원이 이해하기 쉽도록 작성된 코드를 의미한다. 일반적으로 기존 코드를 변경하고자 할 때, 해석하는 시간과 수정하는 비율이 10:1 이라고 한다. 예를 들면, 코드를 변경하기 위해서 걸리는 전체 시간이 10시간이라고 하면, 사전에 코드를 분석하는 시간이 9시간 이상 걸린다는 것을 의미한다. 위의 그래프처럼 변경 비용과 대응 속도에 대한 이상치와 실제 프로젝트에서 발생하는 수치가 차이나는 이유는 프로젝트 초기에 클린코드로 개발하기 보다는 좀 더 빠르고 쉬운 방법을 선택하기 때문이다. 대표적인 것이 'Copy & Paste'이..

DFS(Depth First Search, 깊이 우선 탐색) BFS(Breadth First Search, 너비 우선 탐색) DFS(Depth First Search, 깊이 우선 탐색) 란 루트 노드 혹은 다른 임의의 노드에서 다음 분기(Branch)로 넘어가 기전에 해당 분기를 완벽하게 탐색하는 방법이며 스택(Stack) 혹은 재귀함수(Recursion)로 구현된다. 코드(Python) """ 1 / | \ 2 5 9 | /\ | 3 6 8 10 / | 4 7 """ graph = { 1: [2,5,9], 2: [3], 3: [4], 4: [], 5: [6,8], 6: [7], 7: [], 8: [], 9: [10], 10: [] } def recursive_dfs(v, visited = []): vi..

최소 공통 조상(Lowest Common Ancestor, LCA) 최소 공통 조상(Lowest Common Ancestor, LCA) 란? 최소 공통 조상(LCA) 란 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘 이다. 즉 두 정점이 만나는 최초 부모 정점을 찾는 것을 의미한다. 최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘 모든 노드에 대한 깊이(Depth)를 계산한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이(Depth)가 동일 하도록 거슬러 올라간다. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 최소 공통 조상을 찾을 두 노드를 확인한다. LCA 알고리즘 풀이 이해 1. 각 노드의 "D..