1. 선택 정렬 선택 정렬은 정렬 알고리즘 중 하나로 정렬되지 않은 부분에서 최솟값이나 최댓값을 찾아서 정렬되지 않은 첫 원소와 자리를 교환하는 방식으로 정렬하는 알고리즘이다. 원리가 간단하기 때문에 한 번쯤 배워볼 만하다. 2. 선택 정렬 성능 평균 시간복잡도 $O(N^2)$ ...

1. 삽입 정렬 삽입 정렬은 정렬 알고리즘 중 하나로 정렬되지 않은 각 원소를 정렬된 부분의 적절한 위치에 삽입하는 방식으로 정렬하는 알고리즘이다. 원리가 간단하기 때문에 한 번쯤 배워볼 만하다. 2. 삽입 정렬 성능 평균 시간복잡도 $O(N^2)$ 최선 시간복잡도 ...

1. 버블 정렬 버블 정렬은 정렬 알고리즘 중 하나로 원소의 이동이 거품이 수면으로 올라오는 듯한 모습으로 보이기 때문에 지어진 이름이다. 코드가 단순하기 때문에 간단한 정렬 알고리즘으로 한 번쯤 배워볼 만하다. 2. 버블 정렬 성능 평균 시간복잡도 $O(N^2)$ ...

1. LCS LCS(Longest Common Subsequence)는 최장 공통 부분 수열이라는 뜻으로 주어진 여러 개의 수열 모두의 부분 수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다. 이 문제를 해결하는 간단한 방법은 다이나믹 프로그래밍을 활용하는 것이다. 2. 2차원 배열을 활용한 LCS 주어진 두 문자열의 LCS를 구하는 상황을...

1. LCS LCS(Longest Common Substring)는 최장 공통 부분 문자열이라는 뜻으로 주어진 여러 개의 문자열 모두의 부분 문자열이 되는 문자열들 중에 가장 긴 것을 찾는 문제다. 최장 공통 부분 수열인 LCS(Longest Common Subsequence)와는 다르다는 것에 주의해야 한다.(LCS) 최장 공통 부분 수열과 마찬가...

1. 무한 배낭 문제 0／1 배낭 문제 가 각 물건이 1개씩 있고 배낭에 담느냐 안 담느냐를 선택하는 문제였다면 무한 배낭 문제는 각 물건이 무한히 이상 있는 경우 배낭의 물건의 가치가 최대가 되게 하는 문제다. 무한 배낭 문제는 0／1 배낭 문제와 유사한데 현재 물건을 담을지 말지 판단할 때 현재 물건을 이미 담았던 배낭을 통해 탐색하는 과정만 ...

1. 다중 배낭 문제 0／1 배낭 문제 가 각 물건이 1개씩 있고 배낭에 담느냐 안 담느냐를 선택하는 문제였다면 다중 배낭 문제는 각 물건이 1개 이상 있는 경우 배낭의 물건의 가치가 최대가 되게 하는 문제다. 이때 각 물건이 무한히 있지는 않다. 다중 배낭 문제는 이를 0／1 배낭 문제로 변형하여 해결할 수 있다. 2. 단순 변형 가장 간...

1. 0／1 배낭 문제 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제로 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 중 0／1 배낭 문제는 짐을 쪼갤 수 없는...

Intro 이번 프리코스의 미션은 오픈 미션으로 여러 선택지 중 하나를 골라 해결하는 유형의 미션이었다. 나는 난이도는 평범하나 평소에 잘 사용하지 않는 개발 도구나 언어로 문제를 해결한다.를 미션 주제로 잡았고 C++을 활용한 CLI 체스 프로그램을 구현하는 것을 목표로 잡았다. 체스라는 게임 자체를 좋아해서 한 때 체스닷컴에서 많이 플레이를 하기...

3주차 프리코스 과제는 로또를 구현하는 문제였다. 1 ~ 45 사이의 중복되지 않는 숫자 6개를 갖는 각 로또 번호 조합에 대해 당첨 결과와 수익률을 출력해야 하는 문제로 기존 자동차 게임 상위 버전의 느낌이 있었다. 요구사항이 까다롭고 디테일해서 큰 그림을 잘 그리는 것이 중요했다. 구현 링크 1. 애플리케이션 아키텍처 설계 크게 Do...