'Algorithm' 카테고리의 글 목록

[Algorithm] 슬라이딩 윈도우

Algorithm 2023. 5. 9. 09:14

슬라이딩 윈도우란? 고정된 길이의 2개의 포인터 (커서)를 같이 움직이면서 O(N)에 배열을 탐색하는 테크닉 N개의 원소를 갖는 배열이 있고, W의 넓이를 갖는 창문이 있다고 가정하자. (N, W는 고정된 상수) 창문을 왼쪽부터 시작해서 한 칸씩 오른쪽으로 이동시켜야 한다. 이동시킬 때마다 창문 안에서의 정보 유출 (ex. 합)이 필요하다. 아래 예시는 원소의 개수가 10개이면서 윈도우 크기가 3일 때이다. 문제에서 대놓고 슬라이딩 윈도우라고 언급할 때도 있지만, 몇몇 문제들은 언급 없이 슬라이딩 윈도우 테크닉을 써야할 때가 있다. 💡 슬라이딩 윈도우의 기본 아이디어 윈도우를 한 칸 옮기면 (W-1)칸은 겹친다. 이전에 내가 구해야 하는 창문의 형태와 다음 상태 사이에서 중복된 정보가 W-1개 있으므로 ..

[Algorithm] 재귀

Algorithm 2023. 5. 5. 23:54

재귀란? 하나의 함수에서 자기 자신을 다시 호출해서 작업을 수행하는 알고리즘이다. int func1(int n) { if (n == 0) return 0; return n + func1(n - 1); } 재귀로 어떤 문제를 완전 탐색으로 해결하기 위해 필요한 과정은 다음과 같다! (출처: 영균이) 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을 지를 가늠한다. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 ..

[Algorithm] 누적 합

Algorithm 2023. 5. 4. 15:17

만약 배열 [1, 2, 3, 4, 5, 6]에서 인덱스 3번째 원소 ~ 5번째 원소까지의 합을 구하려면 어떻게 해야할까? 2가지 방법이 있다. 1. 완전 탐색으로 for 문 돌리기 배열에 포함된 원소의 수가 N개일 때의 시간 복잡도는 O(N)이다. int answer = 0; for (int i = 3; i < 6; i++) { answer += arr[i]; } 2. psum 사용하기 psum을 사용하면 시간 복잡도를 O(1)로 줄일 수 있다. psum은 원본 배열의 원소들의 누적합을 구한 배열이다. i = 0일 때, psum[i] = arr[i]으로, psum[0] = arr[0]이다. i = 1일 때에는 psum[1] = arr[0] + arr[1] = psum[0] + arr[1]이고, i = 2..

[Algorithm] 투 포인터 알고리즘 (Two Pointer Algorithm)

Algorithm 2023. 5. 2. 01:57

투 포인터 기법이란?2개의 포인터를 만들어서 각각이 가리키는 원소에 의미를 부여하여 요구하는 문제를 해결하는 알고리즘O(N^2)를 O(N)으로 줄일 수 있다.대다수는 정렬된 배열에서 사용한다. 정렬된 배열에서 O(N^2) 탐색 중 필요 없는 연산을 버려서 O(N)으로 줄인다.포인터에 의미를 부여하는 작업에 대한 예시들을 다양하게 접해야 한다.투 포인터 대표 유형포인터 2개가 양끝에서 반대로 진행해 나아가는 방식포인터 2개가 같은 방향으로 진행해 나아가는 방식포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것투 포인터 동작 원리10개의 서로 다른 양의 정수로 정렬된 수열에서, 두 수 (i, j)의 합이 13을 만족하는 경우의 수를 구하시오. (1 ≤ i 만약 위 문제를 완전 탐색으..

[Algorithm] 백준 2003 수들의 합 2 (C++)

Algorithm 2023. 5. 1. 19:53

2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 알고리즘 분류 브루트포스 알고리즘 두 포인터 문제 풀이 투포인터를 활용하는 문제 2개의 포인터가 동시에 같은 위치에서 출발하는 문제다. 수열의 i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수를 구하면 된다. 그렇기 때문에 2개의 포인터를 활용하고, 2개의 포인터가 같은 위치 (0번째 인덱스)에서 출발한다. 2개의 포인터 (leftPointer, rightPointer)가 0번째 인덱스에서 출발하고, 경우에 따라서..

[Algorithm] BFS & DFS

Algorithm 2022. 3. 15. 09:24

BFS (Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 루트 노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 Queue를 이용하여 구현 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용 시간 복잡도 O(N) BFS 진행 과정 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 2. 큐에서 원소를 꺼내서 해당 칸의 상하좌우로 인접한 칸에 대해 다음 3번을 진행한다. 3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 4. 큐가 빌 때까지 2번을 반복한다. ⇒ 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때..

[Algorithm] 프로그래머스 신고 결과 받기 Level1 (Swift)

Algorithm 2022. 2. 6. 23:40

코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 문제 풀이 프로그래머스에서 Level1 문제 중 제일 마지막으로 남았던 문제.. 뭔가 그래서 더 어려운? 느낌으로 다가오지 않았나.. 싶기도.. 1차 시도는 답이 나왔지만 계속 시간 초과가 나왔다. Dictionary, Set을 조만간 다시 정리해야겠다. 1차 시도 처음 시도한 코드는 시간 초과가 나왔다. 중복 신고를 막기 위해 report를 Set으로 변환하여 저장하고 처리했는데, 아무래도 신고 당한 횟수를 체크하면서 이메일 결과를 처리하는 과정에 있어..

[Algorithm] 프로그래머스 [카카오 인턴] 키패드 누르기 Level1 (Swift)

Algorithm 2022. 2. 6. 16:02

코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 문제 풀이 입력으로 오는 numbers 배열에 있는 숫자들을 누르는데, 이 때 사용한 손가락을 문자열로 리턴하는 문제. 먼저 keypad라는 배열에 키패드 형태를 저장했다. let keypad = [["1", "2", "3"], ["4", "5", "6"], ["7", "8", "9"], ["*", "0", "#"]] 키패드 배열은 아래와 같이 저장되어..

ABOUT ME

🍎 🍎

티스토리툴바