『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.💡 알고리즘 선택의 기준이 되는 시간 복잡도코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것이다.왜 시간 복잡도가 알고리즘 선택의 기준
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.기본 자료구조인 배열과 리스트는 비슷한 점도 많지만 다른 점도 많다.두 자료구조의 특징을 정확하게 이해하고 문제가 요구하는 조건에 따라 적절하게 선택해 사용하는 것이 중요하다.배열과 리
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.💡 코딩 테스트에서 사용 빈도가 높다.구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.구간 합 알고리즘을 활용하려면 먼저 합 배열을 구
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.두 개의 포인터를 이동해가며 리스트에 순차적으로 접근한다.$O(n)$의 시간 복잡도 알고리즘을 갖고 있다.루프를 돌면서 두 포인터 중
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.스택과 큐는 배열에서 발전된 형태의 자료구조이다. 스택과 큐는 구조는 비슷하지만 처리 방식이 다르다.스택은 삽입과 삭제 연산이 후입선출(LIFO, Last-in First-out)이 이
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.두 인접한 데이터의 크기를 비교해 정렬하는 방법이다.간단하게 구현할 수 있지만, 시간 복잡도는 $O(n^2)$으로 다른 정렬 알고리즘보다 속도가 느린 편이다.Loop를 돌면서 인접한 데
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.깊이 우선 탐색(DFS; depth-first search)은 그래프 완전 탐색 기법 중 하나이다.그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친
현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.다만, 이렇게 구한 선택지가 항상 최적의 해를 보장하는 것이 아니다.반례가 나올 수 있다.그리디 알고리즘으로 풀었을 때 최적의 해가 나올지 아닐지를 고민하며 문제를 풀
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.소수(Prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.1과 자기 자신 외의 약수가 존재하지 않는 수코딩 테스트에서는 이러한 소수를
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.노드와 에지로 구성된 집합이다.노드: 데이터를 표현하는 단위에지: 노드를 연결하는 선Tree도 그래프의 일종이다.그래프는 여러 알고리즘에 많이 사용되는 자료구조이므로 코딩 테스트에 자주
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘이
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.노드 간의 순서를 결정한다.사이클이 없어야 한다.노드 수를 $V$, 에지 수를 $E$라고 했을 때 시간 복잡도는 $O(V+E
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.다익스트라(dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.출발 노드와 모든 노드 간의 최단 거리를 탐색한다.에지는 항상 모두 양수이다.노드 수를 $V$, 에지
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.최소 신장 트리(minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.사이클이 포함되면 가중치의 합이 최소가
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다.즉, 그래프의 표현으로도 tree를 표현할 수 있다.트리의 특징은 다음과 같다.순환 구조(cycle)를 지니고 있지 않고
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.조합은 그 자체로 코딩 테스트에 자주 출제되는 주제이며, 동적 계획법을 이해하는데 기초가 된다.조합은 $\_nC_r$으로 표현하며, n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.순열
『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.사실 모든 알고리즘 문제들은 완전 탐색을 이용해 정답을 도출할 수 있다. 단지 비효율적인 연산과 시간을 없애고, 답을 효율적으로 도출하기 위해 여러 알고리즘 기법이 생긴 것이다.동적 계