Computer Science

[알고리즘] 그리디

| 그리디란? - 그리디 알고리즘은, 매 선택에서 지금 이 순간 가장 최선이라 생각되는 답을 선택해 결과를 도출하는 것을 말한다. - 여기서 Greedy을 직역하면 '탐욕'을 뜻한다. - 왜 '탐욕'이라는 말을 쓸까? 그건 지금 이 순간의 부분적인 최적해가 항상 종합적인 최적해는 아닐 수 있음에도, 욕심쟁이와 같이 지금 보는 이 부분적인 선택이 전체의 최선이라 단정짓기 때문이다. rf. 여러 개의 도시가 연결된 도로가 있고, 그 도로 간에 이동 거리가 각각 다른 상황에서 가장 이동거리가 짧은 거리를 찾아야한다고 할 때, 그리디를 쓰면 가장 짧은 도로들을 선택하는 게 될 수 있다. - 정확함 보다는 적당히 맞는 답을 찾을 때 좋은 알고리즘이다. 따라서, 그리디 알고리즘을 근사 알고리즘으로도 부른다. - 언..

[알고리즘] 탐색 - DFS, BFS, 이진 탐색

| 탐색이란? 주어진 데이터들 중에서 원하는 데이터를 찾아내는 알고리즘 | 탐색의 종류 언제? 특징 시간복잡도 DFS(깊이 우선 탐색) 그래프의 모든 노드를 탐색하고자 할 때 - 재귀 또는 스택을 통해 구현 - 트리의 pre-order, in-order, post-order 순회 모두 DFS이다. * 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) BFS(너비 우선 탐색) 그래프의 가까운 지점부터 탐색하고자 할 때 - 큐를 통해서 구현 - 트리의 level-order 가 BFS이다. * 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) 이진 탐색 * DFS, BFS 모두 간선의 갯수가 적을 때에, 인접 리스트를 쓰는게 유리하다. 1. DFS (깊이 우선 탐색) DFS란, 루트에서 시작..

HashSet<int[]>와 Hashset<ArrayList<Integer>>

| HashSet와 Hashset 문제를 풀다보면, 좌표를 집합에 넣어야 하는 경우가 있었다. 예를 들어, (0, 1), (2, 1) 그래서 아무 생각 없이 아래와 HashSet를 쓰게 되면 contains를 할 때 검색이 제대로 되지 않는 걸 볼 수 있다. 왜 그럴까? 이유는 배열의 경우 Hashcode를 비교하고, 리스트의 경우 Wrapper된 Integer값을 비교하기 때문. HashSet int 배열의 hashcode를 비교 HashSet Integer List의 Wrapper객체(Integer)를 비교 따라서, 좌표와 같은 수열의 집합을 만든다고 하면 HashSet 안에 ArrayList로 넣는 것이 좋다. [ 참고 ] https://stackoverflow.com/questions/654546..

[알고리즘] 정렬

| 정렬이란 - 특정 값을 기준으로 데이터를 순서대로 배치하는 방법 - 기본 : 버블, 삽입, 선택 - 비교적 속도가 빠른 정렬 : 합병, 힙, 퀵, 트리 - 하이브리드 정렬 : 팀, 블록병합, 인트로 - 기타 : 기수, 계수(카운팅), 셸, 보고 | 정렬의 시간복잡도 요약 - 안정성이라는 것은, 어떤 데이터 { 1, 2, 3, 1, 1, 1 } 을 정렬한다고 할 때, 같은 숫자 1에 대해서 { 1, 1, 1, 1 } 의 순서가 유지되도록 정렬되는 것을 '안정성이 있다'라고 한다. - 아래의 보조 메모리는 추가적으로 드는 메모리를 이야기하는데, 버블이나 삽입, 선택의 경우 swap시에 드는 변수 1개만 필요하기 때문에 보조메모리가 1개만 소요된다. 정렬 방법 시간 복잡도 보조 메모리 안정성 Ω(n) Θ(..

[알고리즘] 알고리즘 개요

| 알고리즘이란? 알고리즘이란, 어떤 문제를 해결하기 위한 절차나 방법을 말한다. - 알고리즘의 조건 입력 데이터의 입력 출력 처리 후 출력 명확성 동작의 흐름(flow)에 대한 명확성 유한성 정해진 시간 및 공간 내에서의 처리 효율성 같은 동작을 하더라도 시간 및 공간 면에서 보다 효율적이어야 한다. | 알고리즘은 결국 정확성과 시간 복잡도, 공간 복잡도를 말한다. - 어떻게 보다 적은 자원을 효과적으로, 정확하게 만들어 내느냐가 알고리즘의 핵심 | 알고리즘 정리 개요 - 앞으로 정리할 알고리즘 목록입니다. - (글 작성 후 링크 업로드 예정) 정렬 이진탐색 / 투 포인터 그리디 알고리즘 분할 정복 / 다이나믹 프로그래밍 백 트래킹 최단 경로 최소 신장 트리 [ 참고 및 출처 ] 부트 캠프 강의를 들은..

[비선형 자료구조] 힙과 우선순위 큐

| 들어가기 전에 - 왜 우선순위 큐는 비선형 구조일까? : 큐는 선형구조로 1 : 1의 대응방식을 가진다. 앞에서 부터 데이터를 꺼내고, 뒤에서부터 데이터를 축척한다. : 우선순위 큐는 이러한 큐에 우선순위 개념을 추가한 형태로, 우선순위를 따져 우선순위가 높은 데이터를 먼저 뽑는다. : 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데 이중에서 힙으로 구현을 하는 것이 가장 효율적이다. : 따라서, 자바에서도 우선순위 큐는 힙으로 구현되었다. 힙은 완전 이진 트리 형태이며, 이는 1 : N 관계를 갖는 비선형구조이다. - 자바에서는 우선순위 큐를 힙으로 구현한다. 왜? : 위에서도 잠시 언급했던 것처럼, 힙으로 큐를 구현하는 것이 가장 효율적이기 때문에, 자바도 구현방식으로 힙을 쓴다. - 배..

[비선형 자료구조] 트리와 그래프

| 요약 핵심 단어 핵심 특성 언제 쓰면 좋을까 트리 계층, Acyclic, 4가지의 순회 포화 이진 트리의 경우, 하위로 갈수록 노드의 갯수가 2^0, 2^1, 2^2..로 증가 계층 관계의 데이터를 다룰 때 그래프 네트워크, cyclic, DFS/BFS 루트가 없고, 각 정점들간 단방향 또는 양방향의 관계를 가질 수 있음 연관 관계를 가진 데이터들에서 최적의 결과를 찾아야할 때 | 트리와 그래프의 차이 트리 그래프 개요 그래프의 한 종류 정점(vertex, 노드)과 간선(edge)으로 이루어진 자료구조 그림 출처 : 위키백과 출처 : 위키백과 방향 (단)방향 그래프 무(양)방향, (단)방향 그래프 사이클 Acyclic Cyclic 모델 계층 모델 네트워크 모델 루트 최상위 노드 없음 상-하위 관계 인..

비선형 자료구조 총정리

보호되어 있는 글입니다.

[선형자료구조] 해시테이블

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 HashTable 특징 - 해싱 함수를 통해 키 -> 해시로 변환한다 - key + value - 특정 키와 값을 연결할 때(알파벳-단어, 사전, 전화번호부) - 중복을 제거해야할 때(전체 명단 중 투표 여부 확인) 장점 - 해시 충돌이 없을 때 검색, 삽입, 삭제가 빠르다 (시간복잡도 : 평균 O(1), 최악 O(n)) - 보안성이 높다 (Key와 Hash간의 연관성X) - 데이터 캐싱에 자주 사용된다. - 중복 제거에 유리하다. 단점 - 해시 충돌 : key1과 key2가 해시함수를 거쳐 동일한 해시값(공간)을 가지는 상태 - 공간 복잡도가 커진다 - 순서가 있는 경우에는 맞지 않는다 - 해시 함수 의존도가 높다 - 해시 테이블은 키와 값을 대응시켜 저장..

[선형자료구조] 스택, 큐, 데크

| 스택 종류 구분 내용 언제 쓰는 게 좋을까 Stack 특징 - 후입선출(LIFO) - top / bottom - push, pop, peek - 데이터가 입력된 순서의 역순으로 처리되어야 할 때 Ex. - 함수 콜스택,역추적,인터럽트 처리 - 재귀, DFS - 괄호 검사, 후위 연산, 문자열 역순출력, 실행취소 장점 - top을 통한 접근, 삽입, 삭제가 빠르다. (시간복잡도 O(1)) 단점 - top 이외의 데이터에 접근 불가(탐색x) - 스택은 마치 옷을 겹겹히 쌓듯 데이터를 쌓아 올렸다가 맨 위에서부터 꺼내는 구조이다. - 스택에 대한 알고리즘 문제를 보면, "괄호 검사", "후위 연산", "문자열의 역순 출력", "실행 취소"와 같이 [ 넣었다가 위에서부터 빼는 행위 ]를 통해 문자열의 특정 ..