코딩테스트

그리디 알고리즘(Greedy Algorithm)이란?

개념 그리디 알고리즘은 "탐욕 알고리즘" 또는 "욕심쟁이 알고리즘" 이라고도 불린다. 말 그래도 탐욕스러운 욕심쟁이이기 때문에 선택의 순간마다 최적의 선택을 하여 전체적으로도 최적이길 바라는 방법이다. 선택의 순간마다 최적의 선택을 하여 해답을 만들었다고 해서 그것이 최적의 해답이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용하는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘을 적용하기 위한 2가지 조건 1. 탐욕스러운 선택 조건 (Greedy Choice Property) => 앞의 선택이 이후의 선택에 영향을 주지 않는 것 2. 최적 부분 구조 조건 (Optimal Substructure) => 문제에 대한 최적해가 부분 문제에 대해서도 최적해라는 것 위 조건이 성립하지 ..

삽입 정렬(Insertion Sort)이란?

개념 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 즉, 삽입 정렬은 2번째 요소부터 시작하여 앞 쪽과 비교하여 위치를 지정한다. 삽입 정렬에서는 정렬할 자료가 2개의 부분집합인 S(Sorted)와 U(Unsorted)로 나뉘어져 있다. 정렬된 앞부분의 요소들은 부분집합 S이고, 정렬되지 않은 나머지 요소들은 부분집합 U이다. 부분집합 U에서 요소를 하나씩 꺼내서 이미 정렬된 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다. 따라서 S의 요소는 1개씩 늘리고, U의 요소는 1개씩 줄인다. 이렇게 U의 요소를 모두 S에 삽입하여 공집합이 되면 삽입 정렬이 끝난다. 과정 시작 지점이 있으..

버블정렬(Bubble Sort)이란?

개념 버블 정렬은 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다. 과정 (굵은 글자는 인접한 두 개의 비교를 뜻하고, 빨간색은 자리 교환이 이루어진 것) {16, 2, 31, 14, 5} 리스트가 있을 때 버블 정렬을 시작하면 1회전 {2, 16, 31, 14, 5} ⇒ (16, 2) 비교하여 16이 더 크므로 자리 교환 {2, 16, 31, 14, 5} ⇒ (16, 31) 비교하여 31이 더 크므로 자리 교환 안함 {2, 16, 14, 31, 5} ⇒ (31, 14) 비교하여 31이 더 크므로 자리 교환 {2, 16, 14, 5, 31} ⇒ (31, 5) 비교하여 31이 더 크므로 자리 교환 1회전을 끝내면 가장 큰 자료인 31이 맨 뒤로 이동하게 된다. 2회전 1회전 때 나온 맨 뒷자리를 ..

선택정렬(Selection Sort)이란?

개념 선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 과정 주어진 리스트 중 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. (패스(pass)) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 과정 - 그림설명 1단계 : 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중 가장 작은 원소인 2를 선택하여 자리를 교환한다. 2단계 : 두 번째 자리를 기준 위치로 정하고, 1번 위치를 제외한 나머지 원소 중 가장 작은 원소인 10과 교환한다. 3단계 : 세 번째 자리를 기준 위치로 정하고, 1번과 2번 위치를 제외한 나머지 원소 중 가장 작은 16과 교환한다. 4단계 : 네 번째 자리를 기준 위치로 정하고, 1번과 2번과 ..

시간복잡도 Big-O(빅오)란?

알고리즘이란? 어떤 문제나 목적을 달성하기 위해 거쳐야 하는 여러 과정들을 의미한다. 이 과정들은 다양하고, 상황에 따라 알고리즘은 모두 다르다. 따라서 상황에 맞게 시간 복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. (효율적이고 사용 환경에 최적인 알고리즘을 선택하여 사용한다.) 일반적으로 알고리즘의 성능 분석은 실행에 필요한 공간 측면에서 분석하는 공간 복잡도, 실행 소요시간 측면에서 분석하는 시간 복잡도를 추정하여 평가를 한다. 알고리즘의 실행 시간이란? 알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 컴파일러 속도에 달려있다. 알고리즘의 실행 시간을 두 부분으로 나누면 다음과 같다. 입력값의 크기에 따른 알고리즘의 실..

[백준] 3003번 - Java(자바)

백준 3003번 자바 https://www.acmicpc.net/problem/3003 3003번: 킹, 퀸, 룩, 비숍, 나이트, 폰 첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다. www.acmicpc.net 문제내용은 아래 더보기를 누르면 나온다. 더보기 알고리즘 체스 16개의 피스 킹, 퀸, 룩, 비숍, 나이트, 폰 의 개수를 배열로 저장하여 비교한다. (1개, 1개, 2개, 2개, 2개, 8개) 첫째 줄에 동혁이가 가지고 있는 피스와 비교하여 빼야하는지 더해야하는지 구한다. 1. 체스 배열 chessArr = {1, 1, 2, 2, 2, 8} 을 만든다. 2. 체스 배열의 길이만큼 반복한다. 2-1..

[백준] 2292번 - Java(자바)

https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제내용은 아래 더보기를 누르면 나온다. 더보기 알고리즘 육각형으로 이루어진 방들이 중앙의 1번부터 시작해서 이웃하여 퍼져나간다. 숫자 N은 1,000,000,000 이하까지 주어진다. 1에서 N번방까지 최소 몇 개의 방을 지나가는지 시작과 끝을 포함하여 출력하면 된다. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 위 이미지 오른쪽에 숫자에 따른 거리를 한 줄씩 표시했는데 +6 단위로 거리가 ..

[백준] 1712번 - Java(자바)

백준 1712번 자바 https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 문제 내용은 아래 더보기를 누르면 나온다. 더보기 알고리즘 A = 고정 비용 B = 가변 비용 C = 노트북 가격 손익분기점 : 총 수입(판매비용) > 총 비용(A + B) 노트북을 얼마나 팔아서 손익분기점을 넘기는지 구하시오. (A, B, C는 21억 이하 자연수) 손익분기점이 나오지않으면 -1 출력해야한다. 여기서 우리는 손익분기점에 대해 생각해야한다. A + B * 판매대수 ..