-
6. 이진 탐색 알고리즘
2021.09.30
순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 주의할 점은 해당 알고리즘은 정렬되어있는 경우에 사용할 수 있다는 것이다. 만약 정렬이 되어있지 않은 경우에는 시간 복잡도가 '정렬 시간 복잡도' * '이분 탐색 시간 복잡도'라고 생각해야 한다. 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하다. (연산 횟수는 log(2)N에 비례한다. '()'는 밑을 의미) 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다. public class B..
-
7. 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall)
2021.08.20
플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다. 노드의 갯수가 적은 경우에서 효과적으로 사용할 수 있으며, 노드 및 간선의 개수가 많은 경우에는 일반적으로 다익스트라 알고리즘을 사용해야하는 경우가 많다. 플로이드 워셜 알고리즘 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a에서 b로 가는 최단 거..
-
7. 최단 경로 알고리즘 - 다익스트라(Dijkstra)
2021.08.20
최단 경로 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 각 노드는 문제상황에 따라 국가, 도시, 마을 등으로 다르게 정의될 수 있다. 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이..
-
스무디 한 잔 마시며 끝내는 리액트 + TDD - 5장 나의 첫 리액트 프로젝트
2021.08.19
한동안 팀프로젝트로 꽤 바쁜 일정을 소화하느라 스무디 한잔을 할 여유도 없었다... 😫 방학을 맞이하여 최소 한 챕터라도 보자는 마음으로 일단 책을 폈다. 그런데 이번장 너무 재밌겠잖어 ~? 😆 무려 시작부터 관심사였던 타입스크립트를 소개한다. 타입스크립트 리액트는 js이며, js는 동적 프로그래밍 언어(Dynamic Programming Language)이다. 동적 프로그래밍 언어는 런타임 시 변수의 타입이 결정된다. 그렇기 때문에 변수의 타입 때문에 발생한느 버그와 에러는 js를 실행해 보지 않으면 알 수가 없다. 리액트에서는 이런 문제를 해결하고자 플로우(Flow)라는 정적 타입 분석기를 사용할 수 있다. 플로우는 페이스북에서 만들었고, 리액트, 리액트 네이티브에서 변수의 타입을 미리 지정하여 변수..
-
4장 - 클래스, 객체, 인터페이스
2021.08.18
코틀린의 클래스와 인터페이스는 자바 클래스, 인터페이스와는 약간 다르다. 이번장에서는 코틀린의클래스, 객체, 인터페이스에 대해 알아본다. 클래스 계층 정의 코틀린에서 클래스 계층을 정의하는 방식과 자바 방식을 비교한다. 그후 코틀린의 가시성과 접근 변경자에 대해 살펴본다. 코틀린 가시성/접근 변경자는 자바와 비슷하지만 아무것도 지정하지 않는 경우 기본 가시성은 다르다. 또한 코틀린에 새로 도입한 sealed 변경자에 대해 설명한다. sealed는 클래스 상속을 제한한다. 코틀린 인터페이스 인터페이스를 정의하고 구현하는 방법을 살펴보자. 코틀린 인터페이스는 자바 8 인터페이스와 비슷하다. 코틀린 인터페이스 안에는 추상 메서드뿐 아니라 구현이 있는 메서드도 정의할 수 있다(이는 자바 8의 디폴트 메서드와 비..
-
8. 위상 정렬
2021.08.18
공부할 내용 서로소 집합 신장 트리 크루스칼 알고리즘 위상 정렬 공부 방법 기타 그래프 이론 - 동빈나 영상 시청 및 정리 이것이 코딩테스트다 책 참고 추천문제 풀기 (블로그에 문제 풀이를 게시하지는 않겠음) 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 예시) 선수과목을 고려한 학습 순서 설정 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 진입차수와 진출차수 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 큐를 이용하는 위상 정렬 알고..
