제뉴어리의 모든것

그리디 알고리즘이란? 탐욕 알고리즘으로도 불리며, 매순간 현재 이 순간 최선의 상황만을 쫓아 해답에 도달하는 방식의 알고리즘. 그리디 알고리즘으로 문제 해결 절차 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다. 예를 들어 설명하자면, 내가 편의점 점주이고, 고객이 440원짜리 물건을 사면서 1000원을 냈을때, 나는 500원, 100원, 50원, 10원 짜리 동전을 무한히 가지고 있다고 하자. 그럼 거스름돈은 560원일것이다..

의사코드란 의사코드란 프로그래밍을 작성하기 전에 자연스런 사람의 언어로 작성된 코드.적절한 코드도 추가하여도 좋다. 의사코드 예제 문제 : 수를 요소로 갖는 배열을 입력받아, 각 요소들이 그 이전의 요소들의 합보다 큰지를 확인하여서, 크지 않은 경우가 발생한 경우 false를 리턴한다. 발생하지 않은 경우는 true를 리턴한다. (단 수열은 음수나 0의 값이 들어오진 않는다) 문제 접근 방법 1. 인풋, 아웃풋이 무엇인지 인지한다. 인풋 : 숫자가 들어있는 배열, 아웃풋 : 이전수열의 합이 현재 요소보다 크거나 같다면 false, 반대는 true 2. 문제에서 검사를 하라고 한 조건을 어떻게 확인할 것인가 생각해본다. 1차적으로 수열에 각 요소에 접근하여야한다. 그러므로 for문 사용을 염두해야한다. 그..

DFS (Depth-First Search) 란? 깊이를 먼저 탐색하는 탐색 방법이다. 한 깊이를 끝까지 탐색한 뒤 더 이상 탐색할 하위가 없을 경우 다른 깊이를 탐색한다. DFS의 종류로는 아래와 같다 전위 순회 (PreOrder) 중위 순회 (InOrder) 후위 순회 (PostOrder) - 구현 가능 방법 종류 Stack 이용. 재귀 이용. BFS (Breadth-First Search) 란? 같은 레벨의 노드들을 먼저 탐색 하는 방법이다. 쉽게 말하자면, root의 기준에서 자식 레벨의 모든 노드를 다 방문하고, 그 다음은 자식의 자식 노드들을 다 방문하기를 반복한다. - 구현 가능 방법 종류 Queue 이용 참조 : https://www.youtube.com/watch?v=_hxFgg7TLZQ..

트리 순회(Tree traversal) 란? 트리를 순회하는 방법을 말한다. 트리 순회 종류 전위(먼저), 중위(중간에), 후위(나중에) 의 개념을 root를 기준으로 생각하면 된다. 전위 순회 (Preorder) 전위 순회의 노드를 방문(처리 or 출력) 순서 1. Root 2. Left 3. Right 중위 순회 (Inorder) 중위 순회의 노드를 방문(처리 or 출력) 순서 후위 순회 (Postorder) 후위 순회의 노드를 방문(처리 or 출력) 순서 1. Left 2. Right 3. Root 회고 개념적으로는 금방 이해되는 내용이지만, 트리의 구조가 확장 되었을때는 처리 순서를 한번에 인지하기가 쉽지가 않았다. 그래서 일단 저 위 그림에 나와있는 가장 단순한 구조(깊이가 1인 트리)의 트리에..

이진 탐색 트리 (Binary Search Tree) 란? 앞선 게시물 "2022. 07.26 - [Section2] [자료구조/알고리즘] 자료구조 - Tree" 을 통해 이진트리에 대해 알아보았다. 그럼 이번에 말하는 이진 탐색 트리는 도대체 뭐냐! 음, 사실 검색을 많이 해봐도 정식 문서를 보아도 명확하게 정의를 내려준곳은 아직 발견하지 못했다. 아니 힌트를 준곳을 하나 발견하였다. 그 관점에서 바라보고선 스스로 정리하여 답을 내려보았다. 일단, 이진트리란 1. 각 데이터는 노드의 형태를 가진다 (자신의 데이터와 하위 노드를 가질 수 있으므로) 2. 각 노드는 최대 2개의 하위 노드를 가질 수 있다. 3. 각 노드의 방향성은 하위로 뻗어 나간다. (루트로부터 역방향은 존재하지 않는다.) 이란 특징을 ..

그래프란? 여러개의 데이터들이 서로 복잡하게 연결되어 있는 데이터 구조. 일반적으로 알고 있는 수치를 나타내는 그래프와 컴퓨터 공학에서의 그래프는 무관하다. 구조를 그림으로 나타내면 마치 아래와 같다. 위 그림에서 0, 1, 2, 3, 4, 5, 6 이 데이터들이다. 그래프에서 쓰이는 명칭으로는 정점(Vertex)라고 한다. 정점 사이에는 간선(Edge)이 존재해서 데이터간의 관계를 나타낸다. 즉, 간선이 존재하다는 것은 데이터간 연결이 되어있다는것이다. 그리고 그 간선은 방향성이 존재할 수도 있고(단방향), 없을수도 있다.(없을 경우는 양방향) 그래프의 표현 방법 위와 같은 그래프를 표현 할 수 있는 방법은 크게 두가지가 있다. 인접 행렬 그래프를 행렬로써 표현한 방법이다. 인접 행렬의 의미는 인접한 ..