문제 해결 알고리즘 기초/몸 풀기 (4) 썸네일형 리스트형 O(N * M) 과 O(N) 으로 해결하는 이동 평균 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 이동평균 (Moving Average) 이동 평균이란 말 그대로 어떤 기간의 평균을 시간의 흐름에 따라 이동하며 구하는 것이다. 예를 들어, 지난 1년 동안 몸무게의 3개월 이동 평균을 구한다면 1~3월의 평균, 2~4월의 평균... 9~11월의 평균, 10~12월의 평균을 구한다. 기본적으로 완전 탐색의 방식으로 구할 수 있다. 전체 구간 N 동안 기간 M 에 (N > M) 대한 이동 평균을 구한다면 (N-M+1)*M 만큼 연산하므로 시간 복잡도는 O(N*M). 다음은 주어진 몸무게 목록 weight vector 에 대해 interval 만큼의 기간에 대한 이동 평균을 구하는 방법이다. for(int front = 0; front 정렬 알고리즘 (거품, 선택, 삽입 정렬) ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 목차 (눌러서 이동) 거품 정렬 (Bubble Sort) 바로 뒤의 원소와 비교해 순서를 바꾸는 작업을 원소의 개수만큼 반복한다. 반복할 때마다 가장 큰 원소가 맨 뒤에 위치하므로 매번 반복의 길이는 1씩 줄어든다. N 개 원소에 대해 N + (N-1) + (N-2) + ... + 2 + 1, 즉, (N + 1) * N / 2 만큼 연산한다. 최대 차항은 N^2 이므로 O(N^2) 의 시간 복잡도를 가진다. void bubbleSort(vector& v) { for (int i = 0; i < v.size() - 1; ++i) { for (int j = 0; j < v.size() - (i + 1); ++j) if (v[j + 1] < v[j.. 배열에서 두 원소의 합 (2Sum) ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 2Sum 정수 배열과 목표 숫자 가 주어지면 배열의 원소들 중 2 개를 골라 합산하여 목표수를 만들 수 있는지 계산한다. N 개의 원소를 N 번 반복해 답을 구하는 완전 탐색이 가능하지만, O(N^2) 의 시간복잡도를 가지므로 개선된 두 가지 방식으로 풀어본다. Two pointer 첫 번째는 두 개의 포인터를 사용하는 방법으로 O(N*logN) 에 문제를 해결한다. 정렬된 배열이 필요하므로 N 개의 원소에 대해 N * logN 만큼 연산하고, 정렬된 배열을 한 번 반복하며 합을 찾으므로 N 만큼의 시간이 더 든다. bool twoPointerSolution(const vector& ori, int target) { int lo = 0, hi.. 가위 바위 보 게임 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 가위 바위 보 게임 가위는 보를 이기고, 보는 바위를 이기고, 바위는 가위를 이긴다. 세 가지 수에 의해 승패가 순환되므로 모듈러 연산을 통해 승패를 구분지을 수 있다. 가위 ↗ ↘ 바위 ← 보 가위 : 1, 바위 : 2, 보 : 3, 내가 낸 것 : x, 상대가 낸 것 : y 이면, (x % 3) + 1 == y 일 때 나는 진다. 따라서, 다음 세 가지 경우를 검사해 승패를 결정 지을 수 있다. 1. x == y (무승부) 2. (x % 3) + 1 == y (패배) 3. else (승리) void rockPaperScissors(int x, int y) { if (x == y) cout 이전 1 다음