공상개발

상상 박스

Computer Science/Algorithm

안녕하세요 공상 개발입니다. 오늘은 LCS(Longest Common Subsequence) 유형의 백준 문제를 한번 풀어봅시다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net # 문제 LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCA..

2021. 5. 9.

Computer Science/Algorithm

# 소개 안녕하세요 공상 개발입니다. 오늘은 전형적인 DP 문제인 행렬 경로 문제에 대해 알아보겠습니다. 앞서 다루었던 '피보나치수열' 보다 관계식을 유추하기 다소 어렵긴 하지만 같이 풀어봅시다. # 행렬 경로 문제 n * n 행렬의 좌측 상단에서 시작하여 우측 하단까지 오른쪽 혹은 아래쪽으로만 이동하여 도달하는 방법들 중 이동 경로상의 점수의 합을 최대로 하는 경로를 찾는 문제. 최장 경로 문제 : 최장 경로상의 부분 경로가 반드시 두 점상의 최장 경로는 아니다. 단순히 부분 경로에서 제일 큰 값을 따라가는 것이 아닌 경로상에 있는 모든 값들을 더했을 때 최대가 되는 최적의 경로를 찾아야 됩니다. 최단 경로 문제 : 최단 경로상의 모든 부분 경로들 역시 해당 정점들에 대하여 최적. 1. m [][] 배..

2021. 5. 8.

Computer Science/Algorithm

# 소개 안녕하세요. 공상 개발입니다. 오늘은 동적 프로그래밍이 무엇인지 피보나치 예제를 통해 가볍게 다루어 볼 것입니다. 동적 프로그래밍은 코딩 테스트에서 자주 언급되는 부분이기도 하고 처음 접하면 많이들 어렵다고 느낍니다. 천천히 같이 살펴봅시다. # 동적 프로그래밍 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 프로그래밍은 작은 문제를 먼저 해결하여 결과를 테이블에 저장한 후, 그 결과가 필요할 때마다 사용하여 상향식으로 해답을 구축합니다. # 분할 정복 vs 동적 프로그래밍 지금까지 우리는 피보나치를 구현할 때 재귀 알고리즘으로 구현했습니다. 그 과정에서 문제를 분할하고, 부분 문제를 재귀적으로 해결한 후, 통합하는 하향식 접..

2021. 5. 6.

Computer Science/Algorithm

안녕하세요. 공상 개발입니다. 오늘은 분할 정복 알고리즘의 일종인 퀵 정렬에 대해 알아보는 시간을 가지겠습니다. 퀵 정렬은 정렬 알고리즘 중 제일 까다롭다고 생각합니다. 1. 퀵 정렬(quick sort) 2. 퀵 정렬 알고리즘 실행 과정 # 퀵 정렬(quick sort) 퀵 정렬은 분할 알고리즘으로 분할된 부분 배열을 재귀적으로 정렬하는 알고리즘입니다. 피벗을 정한 뒤 피벗의 위치를 확정해가며 정렬이 이루어집니다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다. 퀵 정렬 로직 분할 : 분할 원소를 중심으로 두 부분 배열로 분할 정복 : 분할 원소를 제외한 나머지 두 부분 배열에 퀵 정렬을 재귀 호출하여 정렬 통합 : 필요 없음 이때, 분할(partition) 알고..

2021. 4. 10.

Computer Science/Algorithm

안녕하세요. 공상 개발입니다. 오늘은 분할 정복 알고리즘의 일종인 병합 정렬에 대해 알아보는 시간을 가지겠습니다. 1. 병합 정렬(merge sort) 2. 병합 정렬 알고리즘 실행 과정 # 병합 정렬(merge sort) 병합 정렬은 모든 숫자를 다 나눈 다음에 병합하는 방식으로 정렬을 진행합니다. 병합 정렬 로직 1. 분할 과정과 정복 과정으로 나누어진다. 2. 모든 숫자를 독립적으로 분할한다. 3. 크기를 비교해서 하나의 그룹으로 병합한다. 아래의 이미지와 같이 모든 숫자가 독립이 될 때까지 분할합니다. 분할하는 전체적인 과정을 아래의 이미지를 통해 한번 보겠습니다. 병합 과정은 예비 그릇에 옮겼다가 본래 배열로 옮겨주면 됩니다. 소스 코드 수정 : line 11 -> 병합 과정 출력 값 # 병합 ..

2021. 4. 9.

Computer Science/Algorithm

안녕하세요 공상 개발입니다. 이번 시간에는 재귀(Recursion) 알고리즘에 대해서 알아보는 시간을 가지겠습니다. 1. 분할 정복법(divide-and-conquer) 2. 재귀(recursion) 알고리즘 # 분할 정복법(divide-and-conquer) 분할 정복 설계 전략 step1(분할) 문제를 (하나 이상의) 더 작은 문제로 분할합니다. step2(정복) 작은 문제들을 각각 재귀적으로 정복(해결)합니다. step3(통합) 필요한 경우, 작은 문제에 대한 해답을 통합하여 원래 문제의 해답을 구합니다. 하향식(top-down) 접근 방식 상위 사례의 해답을 더 작은 사례에 대한 해답을 재귀적으로 구함으로써 문제를 해결합니다. 대표적인 분할 정복 정렬 알고리즘으로는 병합 정렬과 퀵 정렬이 있습니다..

2021. 3. 21.

Computer Science/Algorithm

안녕하세요 공상 개발입니다. 이번 시간에는 대표적인 정렬 알고리즘인 삽입 정렬, 버블 정렬, 선택 정렬에 대해서 알아보는 시간을 가지겠습니다. 1. 정렬(Sort)의 개요 2. 선택 정렬(Selection Sort) 3. 버블 정렬(Bubble Sort) 4. 삽입 정렬(Insertion Sorting) # 정렬(Sort)의 개요 정렬은 주어진 객체들의 리스트를 정해진 기준으로 순서대로 나열하는 것입니다. 정렬은 정적(static) 집합을 대상으로 합니다. # 정적 집합이란, 레코드의 추가 및 삭제, 변경이 없는 경우를 말합니다. 대표적인 정렬 알고리즘으로는 아래와 같습니다 삽입정렬, 버블정렬, 선택정렬 병합정렬, 퀵정렬, 힙정렬 기수정렬, 계수정렬, 버킷정렬 정렬 알고리즘을 본격적으로 알아보기 전에 안..

2021. 3. 16.

Computer Science/Algorithm

안녕하세요 공상 개발입니다. 이번 시간에는 알고리즘의 개요에 대해 알아보는 시간을 가지도록 하겠습니다. 1. 알고리즘이란? 2. 알고리즘의 표현 3. 알고리즘의 분석 # 알고리즘이란? 알고리즘(algorithm)은 주어진 문제에 대한 답을 찾는 단계적 절차 혹은 기법을 말합니다. 컴퓨터공학에서 알고리즘은 프로그램에서 어떤 특정한 일을 수행하는 개별적인 모듈과 유사합니다. 우리는 아래의 내용들을 중심으로 학습할 것입니다. 주어진 문제를 해결하는 알고리즘의 설계 기법 알고리즘의 효율성 분석 기법 중요한 문제에 대한 효율적 알고리즘의 이해 적절하고 효율적인 자료구조를 이용한 알고리즘의 구현 알고리즘 과목 자체가 어려운 것은 맞지만 사실 자료구조 과목에서 배웠던 내용과 겹치는 부분이 많이 있습니다. 알고리즘에서..

2021. 3. 14.