코드스테이츠_국비교육 158

26.02_시간 복잡도_22.09.27

시간복잡도(Time Complexity) >개요 : 문제를 해결하며 중요한 것은 답과 효율이다. : 답을 찾는 것은 알고리즘에 대한 이해와 능력이 필요 : 효율적인 측면은 시간복잡도에 대한 이해와 능력이 필요 >의미 : '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?' 를 의미 : 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화하는 것이 효율적인 알고리즘이다! >시간 복잡도 표기법 Big-O(빅-오) : 최악을 고려하는 표기법 : ~정도 시간까지 걸릴 수 있다. Big-Ω(빅-오메가) : 최선을 고려하는 표기법 : 최소 ~정도 시간이 걸린다 Big-θ(빅-세타) : 평균을 고려하는 표기법 : 평균적으로 ~정도 시간이 걸린다. =>Big-O 표기법의 표현이 문제가..

26.01_코딩 테스트 준비_22.09.27

코딩 테스트 >개요 : 상황에 따라, 조건에 따라 모든 경우의 수에서 다른 선택을 하게 됨. : 이를 코드에 반영하기 위해 알고리즘을 사용 >목차 -의사 코드(pseudocode) -시간 복잡도(Time Complexity) -Greedy -implementation - Simulation -Brute-Force Algorithm -Binary Search Algorithm -Algorithm with Math (순열 / 조합) >목표 : 알고리즘의 각각의 특성을 이해하고, 어떤 문제(상황)에서 어떤 알고리즘을 사용할 지 파악하기 위함. >알고리즘 : 문제를 해결하는 최선의 선택 의사코드, pseudocode >의미 : 코드를 작성하기 전, 프로그램의 작동 논리를 먼저 글(주석)로 써보는 것. : 코드의..

25_Searching Algorithm_22.09.26

트리 순회 >의미 : (특정 목적을 위해)트리의 모든 노드를 한 번씩 방문하는 것. >전위 순회 : [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회 >중위 순회 : [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회 >후위 순회 : [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회 그래프 순회 >의미 : (특정 목적을 위해) 그래프의 모든 정점을 한 번씩 방문하는 것. >BFS(Breadth-First Search) : 너비 우선 탐색 : 두 정점의 최단 경로를 찾을 때 주로 사용 : 시작점에 인접한 정점을 먼저 탐색하는 방법 : 검색 속도는 DFS보다 상대적으로 빠르다 : 검색 방법은 DFS보다 상대적으로 복잡하다 : 보통 재귀적인 방식보다는 큐를 이용하고, 어떤 정점을 방문했는지의 여부를 검사하..

24.03_Binary Search Tree_22.09.23

>Tree 구조 발전 과정 : 기존 트리는 편리한 구조로 저장할 순 있었지만, 특정 데이터를 검색하기 위해선 거의 모든 node를 순회하며 찾아야했음. : 효율적인 탐색을 위해 만들어진 새로운 tree구조를 만들어 나감 >Tree 구조 종류 이진트리(Binary tree) : 자식 노드가 최대 두 개인 트리 : 왼쪽 자식 노드, 오른쪽 자식 노드로 구분 가능 : 자료의 삽입, 삭제 방법에 따라 종류가 나뉨 정 이진 트리(Full binary tree) : 각 노드의 자식 노드는 0개 혹은 2개인 트리 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외하면, 모든 레벨에는 노드들이 가득 찬 트리 : 마지막 레벨의 노드는 왼쪽부터 채워짐 포화 이진 트리(Perfect binary ..

24.02_Graph_22.09.23

Graph >의미 : 여러 개의 점들이 서로 연결되어 있는 관계를 표현한 자료구조(수학에서 배운 x-y그래프 아님) : 네트워크망과 같은 구조로 생각. >Graph 구조 1. 정점(vertex) : Graph 구조에 있는 각각의 데이터 2. 간선(edge) : 정점을 잇는 통로(선) : 단방향, 양방향이 존재 3. 직접 관계 : 한 개의 간선으로 연결된 관계 4. 간접 관계 : 여러 간선과 정점을 거쳐 연결된 관계 5. 비가중치 그래프(unweighted Graph) : 연결의 강도와 같은 추가적인 정보가 없는 그래프 : vertex와 edge로만 이루어진 그래프 : 연결 유무만 확인 가능 6. 가중치 그래프(weighted Graph) : 연결의 강도와 같은 추각적인 정보가 있는 그래프 : vertex..

24.01_Tree_22.09.23

Tree >의미 : 하나의 뿌리로부터 가지가 사방으로 뻗은 형태의 자료구조 : 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 : 나무를 거꾸로 뒤집어놓은 듯한 형태 : 비선형 구조(일직선의 구조가 아님) : 단방향 그래프 >특징 1. Node : 트리 구조에 속하는 각각의 데이터 1-1. Edge : 각각의 node의 연결통로 2. Root : 트리 구조의 시작점이 되는 node 3. Parent - Child : 두 개의 노드가 상하 계층으로 연결된 경우 부모/자식 관계가 됨. 3-1. Parent Node : 부모/자식 관계에서 상위 node를 의미 3-2. Child Node : 부모/자식 관계에서 하위 node를 의미 4. Sibling : 같은 상위 node에..

23.03_Queue_22.09.22

Queue >의미 : 대기 행렬. 즉, 데이터가 들어가서 저장되었다가 들어간 순으로 뽑아냄. : Stack과 반대되는 개념의 자료구조 : 예시) 고속도로 톨게이트(자동차: 데이터) >사용 enqueue: Queue에 데이터를 넣는 것. (add) dequeue: Queue에서 데이터를 꺼내는 것. (poll) >특징 1. FIFO(First In First Out) : 먼저 들어간 데이터가 제일 처음에 나옴. (선입선출) 2. 데이터는 하나씩 넣고(add) 뺼(poll) 수 있다. : 한꺼번에 여러개의 데이터를 넣고 뺼 수 없음. 3. 두 개의 입출력 방향이 있다. : 입력, 출력 방향이 다르다. : Stack과 다르게 넣은 곳에서 뺄 필요가 없으니. >실사용 예제 : 게임 큐(Queue) 잡기 : 프린..

23.02_Stack_22.09.22

Stack >의미 : 데이터를 순서대로 쌓는 자료구조 : 예시) 막힌 골목에 쌓이는 자동차, 프링글스 등 >사용 push : stack에 데이터를 넣는 것 pop : stack에서 데이터를 꺼내는 것, pop() 호출만 가능 >특징 1. FILO or LIFO(Last In First Out) : 가장 먼저 들어간 데이터가 가장 나중에 나올 수 있다. : 가장 늦게 들어간 데이터가 가장 먼저 나올 수 있다. 2. 데이터는 하나씩 넣고(push) 뺼(pop) 수 있다. : 한꺼번에 여러개 불가! 3. 하나의 입출력 방향을 갖는다. : Stack의 데이터 입출력 방향은 같다. 여러개면 Stack 자료구조 아님 : 넣은 곳으로 빼고, 뺀 곳으로 넣고. >실사용 예시 1. 웹 페이지 뒤로가기, 앞으로 가기 2...

23.01_자료구조_22.09.22

학습 목표 각 자료구조의 특징 파악 자료구조 내부 직접 구현하며, 필요한 속성, 메서드 파악하기(동작 원리와 기능) 각 자료구조가 적합한 상황 이해 자료구조를 활용해서 알고리즘 문제 풀기 자료구조 >의미 : 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것. : 데이터를 다루는 구조가 자료구조이며, 이미 구현된 객체를 사용해도 되지만, 스스로 구현해서 만들어도 또한 자료구조이다. >자료구조 모식도 >대표적인 자료구조 4가지 Stack Queue Tree Graph

22_JSON 및 재귀 문제 풀이_22.09.21

JSON >의미 : JavaScript Object Notation의 줄임말 : 데이터 교환을 위해 만들어진 객체 형태의 포맷 : 다른 프로그램을 사용하는 사용자끼리 데이터를 교환하기 위해 만들어지고 사용하는 포맷 >JSON 기본 규칙 in Java : 키와 값, 모두에 쌍따옴표를 붙여야함 : 키와 값 사이에 공백이 있어선 안됨. >JSON 사용법 in Java 직렬화 : java 내의 코드를 JSON 형식으로 변경하는 것. 역직렬화 : JSON 형식을 java에서 읽을 수 있는 코드로 변경하는 것. jackson 라이브러리 : JSON의 형태를 객체의 형태로 변환시켜 직렬화, 역직렬화를 편하게 하기 위한 수 많은 방법 중 하나. ObjectMapper 클래스 : jackson 라이브러리에서 제공하는 클..