Archive

01. 개념노드(node): 트리를 구성하는 요소루트 노드: 노드 중 가장 위에 있는 노드부모 노드: 상대적으로 위에 있는 노드자식 노드: 상대적으로 아래에 있는 노드형제 노드: 같은 부모 노드를 갖는 노드리프 노드: 자식이 없는 리프 노드간선(edge): 노드와 노드 사이를 이어주는 선차수(degree): 특정 노드에서 아래로 향하는 간선의 개수 표현배열이나 포인터로 구현 가능(1) 배열로 표현하기배열 = 선형 자료구조, 트리 = 계층 자료구조자식이 없거나 쓰지 않는 인덱스들은 모두 빈 값이므로 메모리가 낭비배열로 트리를 표현하기 위한 3가지 규칙루트 노드는 배열 인덱스 1번에 저장왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 ..

01 . 개념해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료 구조이다. 해시는 키를 활용해 데이터 탐색을 빠르게 한다.특징단방향 동작: 키 통해 값 찾기만 가능시간 복잡도 O(1): 해시함수 덕분에 탐색 과정 필요 X해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾기 가능해시 테이블: 키와 대응한 값이 저장되어 있는 공간버킷: 해시 테이블의 각 데이터값을 인덱스로 활용하려면 변환과정 필요활용 분야비밀번호 관리데이터베이스 인덱싱블록체인 02. 해시 함수자바에서는 해시셋 혹은 해시맵이라는 표준 API를 제공해시 함수 구현시 고려사항해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다.해시 함수가 변환한 값의..

01. 집합과 상호배타적 집합의 개념집합순서와 중복이 없는 원소들을 갖는 자료구조상호배타적 집합: 교집합이 없는 집합 관계ex. A = {1,2,3} 과 B = {4,5,6,7}활용 알고리즘이미지 분할이미지를 서로 다른 부분으로 나누는 데 사용ex. 사람과 배경을 겹치지 않게 분할도로 네트워크 구성도로 구축시 각 도로를 서로 교차하지 않도록 설계하는 데 사용최소 신장 트리 알고리즘 구현간선을 추가할 때마다 사이클을 형성하는지 여부를 체크할 때 사용게임 개발캐릭터의 동작 자연스럽게 구현 가능ex. 플레이어와 적군 충돌 시 두 캐릭터가 겹치지 않도록 함클러스터링 작업각 작업이 서로 겹치지 않도록 구성 가능작업 간의 의존 관계가 없으면 동시에 여러 작업 진행 가능02. 집합의 연산보통 집합은 트리로 표현대표적..

1. 스택`스택` : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조`LIFO (Last In First Out)` : 먼저 들어간 것이 마지막에 나오는 규칙`push` : 스택에 삽입하는 연산`pop` : 스택에서 꺼내는 연산최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋음 스택의 ADTADT란 ?Abstract Data Type의 약자추상 자료형 (인터페이스만 있고 실제로 구현은 되지 않는 자료형)일종의 자료형의 설계도정의해야 할 연산 : `push` ,`pop` , `isFull` , `isEmpty`정의해야 할 상태 : `top` , `data[maxsize]` 데이터가 없으면 top = -1 스택 세부 동작1. push(3) 호출2. isFull()을 수행하..

01. 배열인덱스와 값을 일대일 대응해 관리하는 자료구조데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근 가능배열 선언int[] arr = { 0, 0, 0, 0, 0, 0 };int[] arr = new int[6];// 둘 실행 결과 같음배열은 인덱스가 0부터 시작배열과 유사한 기능을 가진 ArrayList와 차이배열: 처음 선언할 때 배열의 크기 결정정확한 데이터의 개수를 알고 있는 경우 (속도 더 빠름)ArrayList: 크기 동적임저장해야 할 데이터의 개수를 정확히 알 수 없는 경우배열과 차원컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장배열은 차원과는 무관하게 메모리에 연속 할당1차원 배열배열의 각 ..

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정ㄴ 대표적인 탐색 알고리즘: DFS & BFS자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조ㄴ 스택과 큐 : 자료구조의 기초 개념ㅤ> 삽입 (Push) & 삭제 (Pop)을 핵심으로 하여 구성됨ㅤ> 오버플로 (특정한 자료구조가 수요할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생) & 언더플로 (특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행)도 고민해야 함 스택스택 = 박스 쌓기 = 아래에서부터 위로 쌓임 = 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 함 = 선입후출 구조 (First In Last Out) = 후입선출 구조 (Last in First O..

그리디 알고리즘- 단순하지만 강력한 문제 해결 방법 - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 - 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 기준을 은근히 제시 [예제] 거스름돈*문제카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정할 때 손님에게 거슬러 줘야 할 돈이 N원 (10의 배수)일 때 거슬러 줘야 할 동전의 최소 개수 *해설가장 큰 화폐 단위부터 돈을 거슬러 주는 것N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준 후 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 ..