득이공간

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 7장. 트리 7-1. 트리 7-2. 이진 트리 7-3. 세그먼트 트리 7-4. LCA 📌 7-1. 이진 트리 * 트리의 특징 - 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다. - 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. - 트리의 부분 트리 역시 트리의 모든 특징을 따른다. - 트리에서 임의의 두 노드를 이어주는 경로는 유일하다. * 트리의 구성 요소 - 노드: 데이터의 index와 value를 표현하는 요소 - 에지: 노드와 노드의 연결 관계를 나타내는 선 - 루트 노드: 트리에서 가장 상위에 존재하는 노드 - index..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 6장. 그래프 6-1. 유니온 파인드 6-2. 위상정렬 6-3. 다익스트라 6-4. 벨만-포드 6-5. 플로이드-워셜 6-6. 최소 신장 트리 📌 6-1. 유니온 파인드 * 유니온 파인드 - 그래프 내의 임의 두 노드가 서로 연결되어있는지 판별하기위해 사용되는 부분 알고리즘 * 유니온 파인드 용어 - union 연산: 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음 - find 연산: 두 노드가 같은 집합에 속해 있는지를 확인, 자신의 대표 노드를 찾아준다. * 유니온 파인드 동작 원리 1. 대표 노드 저장 배열에 각 노드를 초기화 2..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 5장. 정수론 5-1. 소수 구하기 5-2. 오일러 피 5-3. 유클리드 호제법 📌 5-1. 소수 구하기 * 소수 - 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수 - 1과 자기 자신 외에 약수가 존재하지 않는 수 * 에라토스테네스의 체 - 시간 복잡도: O(Nlog(logN)) * 에라토스테네스의 체 동작 원리 1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성 2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. - 이때 처음으로 선택된 숫자는 지우지 않..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 4장. 그리디 4-1. 그리디 📌 4-1. 그리디 * 그리디 - 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 * 그리디 동작 원리 1. 현재 상태에서 가장 최선이라고 생각되는 해 선택 2. 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사 3. 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사 - 해결하지 못한다면 1번부터 다시 반복

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 3장. 탐색 3-1. 깊이 우선 탐색 3-2. 너비 우선 탐색 3-3. 이진 탐색 📌 3-1. 깊이 우선 탐색 * 깊이 우선 탐색 - 시작 노드에서 출발해서 탐색할 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해서 다시 탐색을 수행하는 알고리즘 - 기능: 그래프 완전 탐색 - 특징: LIFO, 재귀 함수로 구현 or 스택 자료구조 이용 - 시간 복잡도: O(V+E) * 깊이 우선 탐색 동작 원리 1. 그래프를 인접 리스트로 표현 2. 방문 배열 초기화, 시작 노드 선택 3. 방문 배열 체크 후 인접 노드 중 미방문 노드 탐색 - 재..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 2장. 정렬 2-1. 버블 정렬 2-2. 선택 정렬 2-3. 삽입 정렬 2-4. 퀵 정렬 2-5. 병합 정렬 2-6. 기수 정렬 📌 2-1. 버블 정렬 * 버블 정렬 - 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬 - 시간 복잡도: O(N^2) * 버블 정렬 동작 원리 1. 비교 연산이 필요한 루프 범위 설정 2. 인접한 데이터 값 비교 3. swap 조건에 부합하면 swap 연산 수행 4. 루프 범위가 끝날 때까지 2~3 반복 5. 정렬 영역 설정. 다음 루프를 실행할 때는 이 영역을 제외 6. 비교 대상이 없을 때까지 1~5 반복 *..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 1장. 자료구조 1-1. 배열, 리스트, 벡터 1-2. 구간 합 1-3. 스택, 큐 📌 1-1. 배열, 리스트, 벡터 * 배열 - 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 * 배열 특징 1. 인덱스를 사용해서 값에 바로 접근할 수 있다. 2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. - 삽입 or 삭제는 해당 인덱스 주변의 값을 이동시키는 과정 필요 3. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 4. 구조가 간단해서 코딩 테스트에서 많이 사용된다. * 리스트 - 값과..