🍎 🍎

Algorithm

• [Algorithm] 슬라이딩 윈도우

  Algorithm 2023. 5. 9. 09:14

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

  Read More
• [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 만약 위 문제를 완전 탐색으..

  Read More
• [Algorithm] 시간 복잡도 & 공간 복잡도

  Algorithm 2022. 1. 12. 02:35

  알고리즘을 평가하는 두 가지 요소는 시간 복잡도 (Time Comlexity)와 공간 복잡도 (Complexity)로 나뉜다. 이 두 가지는 속도와 메모리 사용량을 평가하는 것인데, 알고리즘의 수행 시간 분석 결과를 시간 복잡도라 하고 메모리 사용량에 대한 분석 결과를 공간 복잡도라고 한다. 프로그램을 짤 때에는 항상 worst case를 고려해야한다. 그렇기 때문에 시간 복잡도와 공간 복잡도는 보통 Big-Oh 표기법을 이용해서 나타낸다. ㅤ 1. 시간 복잡도 (Time Complexity) 시간 복잡도는 알고리즘의 수행 시간 분석 결과이다. 시간 복잡도를 평가할 때에는 먼저 연산의 횟수를 세고, 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 만든다. 시간 복잡도는 다음과 같이 3가지로..

  Read More
• [Algorithm] 알고리즘 팁 정리 (C++)

  Algorithm 2022. 1. 5. 10:43

  1. auto list l; string word; cin >> word; for (auto c: word) { l.push_back(c); // word에 입력된 단어를 하나하나 l에 넣는다. } for (auto c: l) cout > word; for (auto c: word) { l.push_back(c); // word에 입력된 단어를 하나하나 l에 넣는다. } for (auto i = l.begin(); i != l.end(); i++) { cout word; for (auto c: word) { l.push_back(c); // word에 입력된 단어를 하나하나 l에 넣는다. } for (auto i = l.rbegin(); i != l.rend(); i++) { cout

  Read More
• [Algorithm] 알고리즘 팁 정리 (Swift)

  Algorithm 2022. 1. 5. 10:40

  1. 배열의 모든 요소 더하기, 모두 곱하기let arr = [1, 2, 3, 4, 5]// 배열의 요소 모두 더한 값let addTotal = arr.reduce(0, +) // 15// 배열의 요소 모두 곱한 값let mulTotal = arr.reduce(1, *) // 120 2. 공백으로 숫자 여러 개 입력 받은 후 정수 배열로 저장하기// components 사용var nums = readLine()!.components(separatedBy: " ").map { Int($0)! }var nums = readLine()!.components(separatedBy: " ").compactMap { Int($0) }// split 사용var nums = readLine()!.split(separa..

  Read More