코딩테스트/코딩테스트 알고리즘

슬라이딩 윈도우 알고리즘 (Sliding Window)

( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 구한다고 가정해보면 아래 5가지의 경우의 수가 나온다. [1, 2, 3], 4, 5, 6, 7 1, [2, 3, 4], 5, 6, 7 1, 2, [3, 4, 5], 6, 7 1, 2, 3, [4, 5, 6], 7 1, 2, 3, 4, [5, 6, 7] 다음으로 합을 계산하는 고정된 크기의 배열의 변화를 보면 [1,2,3] => [2,3,4] => [3,4,5] ... => [5,6,7]이다. 그렇다면 어떻게 최소한의 계산으로 다음 배열의 합을 구할 수 있을까? - 먼저 처음 배열 [1,2,3] 의 합을 구한다. =..

코딩테스트 문제 풀이 전, 시/공간 복잡도 이해하기

복잡도 코딩테스트를 준비하기 전, 시간 복잡도와 공간복잡도 이해 해야한다. 대부분의 코딩테스트 문제에는 제한 시간과 메모리가 존재한다. 이를 바탕으로 적절한 시/공간 복잡도를 계산한 뒤 적절한 알고리즘을 사용할 필요성이 있다. 시간 복잡도 '제한시간'안에 알고리즘 문제를 해결하기 위해서는 시간복잡도를 이해해야 한다. 일반적으로 O(N)과 같은 빅오 표기법을 기준으로 연산 횟수를 계산한다. for 문으로 문제를 해결할 시 시간복잡도는 다음과 같다. 단일 for문: O(N) 이중 for문: O(N²) 삼중 for문: O(N³) N값이 어떻게 주어지냐에 따라 시간복잡도를 계산해보자면 N = 500 O(N³)일 경우 1.25 * 10⁸의 연산 횟수가 필요하다. O(N²)일 경우 2.5 * 10⁵의 연산 횟수가 ..

[C] 이진 탐색 (Binary Search) 알고리즘 개념과 예제

이진 탐색 이진 탐색은 오름차순으로 정렬되어있는 데이터에서 원하는 값(타겟 넘버)의 위치를 찾아내는 알고리즘이다. 여기서 이진(Binary)는 우리가 알고있는 그 이진 코드 (0101001...) 가 아니라 데이터를 반(2개)으로 나누어서 비교하고 찾는 방식이여서 이진 탐색이라고 한다. 이진 탐색의 알고리즘 진행방식은 아래와 같다. 정렬되어있는 데이터의 중간 값을 임의의 값 X로 정함 타겟 넘버의 값과 X를 비교 타겟 넘버의 값이 X보다 크다면, 타겟 넘버는 데이터에서 X보다 우측에 위치해 있으니 반으로 나눈 데이터의 우측에서 1번 과정부터 다시 시작 타겟 넘버의 값이 X보다 작다면, 타겟 넘버는 데이터에서 X보다 좌측에 위치해 있으니 반으로 나눈 데이터의 좌측에서 1번 과정부터 다시 시작 이진 탐색 예..

오목 AI 제작 - MIN_MAX 전략을 통한 필승 수 구현

탐색을 적용시킨 오목 AI를 구현해보고 싶어서 3일동안 AI 제작을 진행하게 됐습니다. 먼저 19*19 바둑판 맵을 다 탐색을 하여 돌의 연결상태를 확인한 후 각 돌의 연결 상황마다 가중치를 부여했습니다. 그 후 Search 함수를 통해 탐색 과정에서 AI끼리 각자 가지치기 방식으로 최적의 수를 두어나갑니다. 탐색 중 상대방이 이기는 경우가 발생 하면 return 하여 가지가 갈라지는 분기점으로 돌아가 재 탐색을 시작합니다. 그렇게 탐색하는 도중 자신의 AI가 이기는 상황이 발생하면 맨 처음 좌표값을 저장한 후 그 이후부터는 모든 상황에 대해 return하여 탐색을 종료시켜 제작하였습니다. 최대 깊이 탐색은 현재 시점으로부터 30수까지 설정해 놓았습니다. 그 이유는 웬만하면 승부가 나는 시점까지 도달하고..

투 포인터 알고리즘(Two Pointers Algorithm)

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘이다. 절대 답이 되지 않는 경우는 계산하지 않아 시간을 단축시켜준다. Q. 배열에서 부분 배열의 합이 M이 되는 경우의 수를 구하여라! A1. 가장 쉽고 단순한 방법으로는 이중 for문을 이용해서 모든 경우의 수를 구할 수 있다. 시간 복잡도 O(N^2) A2. 투 포인터 알고리즘을 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 주로 적용되는 문제 유형 - 연속된 수들의 합 - 부분 배열의 합 풀이 방법 1. 포인터 2개가 같은 방향으로 진행해 나아가는 것 2. 포인터 2개가 양끝에서 반대로 진행하는 것 대표 문제 풀이 1 - 백준 [2003] 수들의 합 2 www.acm..

달팽이 방향으로 배열 순회

아래는 소스코드다, v 벡터의 크기와 상관 없이 달팽이 방향으로 순회한다, 로직은 매우 간단하다. sr = 행 시작, sc = 열 시작, er = 행 끝, ec = 열 끝 좌측에서 우측으로 순회할 때마다 시작되는 행을 한 칸씩 증가 상 측에서 하 측으로 순회할 때마다 끝나는 열을 한 칸씩 축소 우측에서 좌측으로 순회할 때마다 끝나는 행을 한 칸씩 축소 하 측에서 상 측으로 순회할 때마다 시작되는 열을 한 칸씩 증가 순회할 때마다 배열에 저장 후 기반 범위 for문 써서 출력. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(N..

스위핑 알고리즘 (Sweeping algorithm)

스위핑 알고리즘(sweeping algorithm)은 그냥 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 건데 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해 주면 정답이 구해지는 형태다. 추천 문제 2170 선 긋기 2836 수상 택시 10000 원 영역 5419 북서풍 3392 화성 지도 10534 City Park

구조체 또는 클래스 관련 정렬 (sort 함수)

구조체 또는 클래스는 항상 연산자 오버로딩을 해줘야하고 클래스명으로 가야한다. struct Student { int id, pow; char team; Student(int a, char b, int c) : id(a),team(b),pow(c) { } bool operator(const Student& b) const { return pow > b.pow; } }; 여기서 pow 기준으로 정렬할텐데 이때 algorithm 헤더파일 내에 sort 함수를 사용하고 pred 인자로 해당 연산자 오버로딩 함수를 보내주면 된다. 디폴트 값 : less(); vector st; // pred 템플릿 인자로 무조건 클래스명으로 줘야한다. sort(st.begin(), st.end(), greater()); less..