Algorithm & PS/Algorithm

알고리듬 - 버블, 선택, 삽입 정렬

버블, 선택, 삽입 정렬은 구현하기 쉬운 대신 성능이 낮은 정렬 알고리즘이다. 이에 대해 하나씩 알아보자. 버블 정렬 버블 정렬은 앞부터 인접한 두 개의 수를 비교해 큰 숫자를 뒤로 보내는 작업을 반복한다. 동작은 아래 그림과 같다. 세 번째처럼 교환이 일어나지 않았을 때는 모든 값이 정렬된 것이므로 동작을 멈추게 해 조금이나마 시간을 줄일 수 있다. 간단히 코드를 보자면 아래와 같다. void bubble_sort(int arr[]) { int tmp = 0; for(int i = 0; i arr[j+1]) { tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } ..

알고리듬 - 슬라이딩 윈도우

슬라이딩 윈도우는 쉽게 설명하자면 투 포인터가 일정한 간격을 두고 이동하는 것이다. 동작 과정은 아래와 같다. 위와 같이 동작하는 것이 일반적인데, 아래처럼 시작해야 할 때도 있다. 이를 활용하는 문제는 아래와 같다. 백준: DNA 비밀번호 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 해당 문제는 슬라이딩 윈도우를 활용하라고 나온 문제로 동작 방식을 이해하면 쉽게 풀 수 있다.

알고리듬 - 투 포인터

투 포인터 2개의 포인터를 활용해 문제를 푸는 방식이다. 일반적으로 두 개의 포인터가 모두 앞에서 시작하는 경우 하나는 앞, 하나는 뒤에서 시작하는 경우 로 구분된다. 이를 활용하는 문제를 바로 보자. 백준: 수들의 합 5 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 해당 문제는 정수 N이 주어질 때 N 미만의 연속된 자연수의 합으로 N을 나타낼 수 있는 경우의 수를 구해야 한다. 만약 N이 6이라면 답은 2(1+2+3..

알고리듬 - 구간 합

구간 합 구간 합은 배열, 리스트 등의 인자를 더한 결과를 저장한 것으로 시간복잡도를 줄이기 위해 활용한다. 예를 들어 아래 그림과 같이 배열 A가 있다면 순서대로 값을 더한 배열 S를 구해 문제를 푸는 것이다. 아래는 구간 합을 이용하는 간단한 문제 중 하나이다. 백준: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 해당 문제는 간단히 값을 받을 때마다 for문을 이용해 풀 수는 있지만 시간 초과로..

알고리듬 - 시간복잡도(Time Complexity)

출발지에서 목적지까지 가는 방법이 여러 가지인 것처럼 어떤 문제를 풀 때 하나의 알고리듬만 있는 것이 아니다. x * y만 해도 Long Multiplication, Lattice Multiplication, Peasant Multiplication 등 방법이 다양하다. 그렇다면 다양한 알고리듬 중 어떤 것이 더 좋은지 어떻게 구분할까? 시간복잡도 & 공간복잡도를 알아보자. 공간복잡도(Space Complexity) 공간복잡도는(Space Complexity)는 알고리듬 실행에 필요한 저장 공간을 나타낸다. 만약 알고리즘 1이 10MB, 알고리즘 2가 100MB만큼의 저장 공간을 요구한다면 공간 복잡도 측면에서 알고리즘 1이 알고리즘 2보다 효율적인 것이다. 하지만 알고리듬의 복잡도를 따질 때 공간복잡도..

알고리듬 - dx, dy를 이용한 이차원 배열 이동

프로그래머스 - 정수를 나선형으로 배치하기 문제를 풀고 다른 사람들의 풀이를 보면서 dx, dy를 처음 접했다. 출처: 프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/courses/30/lessons/181832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dx dy 테크닉 해당 기술은 이차원 배열에서 상황에 맞게 상, 하, 좌, 우로 움직일 수 있게 한다. 만약 움직여야 하는 개체가 [1][1]에 있을 때, 동쪽으로 움직이려면 x = x + 0, y = y + 1을 해야 한다. 북쪽으로 움직이려면 x..