Do it! 알고리즘 코딩테스트

시간복잡도 & 디버깅

📍 배열과 리스트 배열 : 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 리스트 : 노드(값+포인터)를 포인터로 연결한 자료 구조 ✅ 배열과 리스트의 특징 (한 눈에 보기) 배열 리스트 인덱스 O (값에 바로 접근 가능) X 수정 X (어려움) O (쉬움) 배열의 크기 변경 X (불가능) O (가능) 구조의 복잡성 단순 복잡 ✅ 배열의 ...

.

.

버블정렬 : 인접한 두 데이터끼리 swap, O(n^2) / 선택정렬 : 최댓값 또는 최솟값 정한 후, 남은 정렬 가장 앞에 있는 데이터와 swap, O(n^2)

삽입정렬 : 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 / 퀵정렬 : 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘

병합 정렬 : 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘을 말한다. / 기수 정렬 : 값을 비교하지 않는 특이한 정렬이다.

.

.

그리디 알고리즘은 현재 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘을 말한다.

수의 성질을 탐구하고 공부하는 분야를 말한다.코딩테스트에서는 소수 부분과 호제법 부분이 가장 많이 등장한다.소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.즉, 1과 자기 자신 외에 약수가 존재하지 않는 수를

유클리드 호제법과 MOD 연산

그래프의 표현 - 에지 리스트 & 인접 행렬 & 인접 리스트

유니온 파인드(union-find)는 일반적으로 여러 노드가 있을 때특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘을 말한다.

위상 정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.이미지 출처 : 나무위키, 위상정렬항상 유일한 값으로 정렬되지 않는다.사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.진입차

다익스트라 알고리즘은 출발 노드와 모든 노드 간의 최단 거리를 탐색하는 알고리즘이다.

.

최소 신장 트리(minimum spanning tree)란그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리를 말한다.

트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다.순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.

이진 트리 : 전위 / 중위 / 후위 순회

📍 세그먼트 트리✅ 정의주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태를 말한다.더 큰 범위는 인덱스 트리라고 부른다.✅ 핵심 이론세그먼트 트리의 종류 : 구간 합, 최대 및 최소 구하기구현 단계 : 트리 초기화 하기, 질

트리 그래프에서 처음 공통으로 만나게 되는 부모 노드를 뜻한다.임의의 두 노들르 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색할 때 부르는 뜻이다.일반적인 최소 공통 조상 구하기주로 트리의 높이가 크지 않을 때 구하는 방법이다.트리의 높이

c

정답코드

📍 백준 14501번 시간제한 메모리제한 제출 정답 맞힌 사람 비율 2 초 512 MB 110687 57025 37525 50.740% ✅ 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했...

📍 백준 10844번시간제한 메모리제한 제출 정답 맞힌 사람 비율2 초 512 MB 110687 57025 37525 50.740%✅ 문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많

📍 백준 1915번 시간제한 메모리제한 제출정답 정답맞힌 사람 정답 비율 2 초 128 MB 16320 4923 3808 34.168% ✅ 문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. ✅ 입력 첫째 줄에...

📍 백준 11049번 시간제한 메모리제한 제출 정답 맞힌 사람 비율 1초 256 MB 41457 18578 13401 43.615% ✅ 문제 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. 예를 들어, A의 크기가 ...

점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘이다.실제 코딩 테스트에서의 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀 수 있다.CCW(Counter-ClockWise)는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리