algorithm

[알고리즘] 그리디 알고리즘 (탐욕 알고리즘)

Greedy algorithm 최적의 해에 가까운 값을 구하기 위해 사용된다. 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식이다. 매 순간 최적을 선택하기 때문에 현재 상황의 선택이 나중에 미칠 영향은 고려하지 않는다. 때문에 최적이라는 보장이 없다. 때문에 문제를 풀때 현재 상황에서 최적의 답만 선택해도 풀 수 있는 문제인지 파악해야 한다. 그리디 알고리즘을 적용해서 최적해를 구할 수 있는 문제는 2가지 조건을 만족한다. 현재 선택이 이 후의 선택에 영향을 주지 않는다. 매 순간 최적의 해가 문제 전체에 대한 최적의 해 이다. 그리디 알고리즘이 최적해를 보장받지는 못하더라도 어느 정도까지 가까운 해를 구할 수 있기 때문에 근사 알고리즘으로 그리디 알고리즘을 ..

[알고리즘] 연속 부분수열

Q. N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 만약 N=8, M=6이고 수열이 다음과 같다면 1 2 1 3 1 1 1 2 합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다. - 입력 설명 첫 줄에 N(5

[알고리즘] 최대 매출

Q. 현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다. 만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면 12 15 11 20 25 10 20 19 13 15 연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요. - 입력 설명 첫 줄에 N(5

[알고리즘] 공통원소 구하기

Q. A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요. - 입력 설명 첫 번째 줄에 집합 A의 크기 N(1

[알고리즘] 두 배열 합치기(two pointers algorithm)

Q. 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요. - 입력 설명 첫 번째 줄에 첫 번째 배열의 크기 N(1

[알고리즘] 암호

Q. 현수는 영희에게 알파벳 대문자로 구성된 비밀편지를 매일 컴퓨터를 이용해 보냅니다. 비밀편지는 현수와 영희가 서로 약속한 암호로 구성되어 있습니다. 비밀편지는 알파벳 한 문자마다 # 또는 *이 일곱 개로 구성되어 있습니다. 만약 현수가 “#*****#”으로 구성된 문자를 보냈다면 영희는 현수와 약속한 규칙대로 다음과 같이 해석합니다. 1. “#*****#”를 일곱자리의 이진수로 바꿉니다. #은 이진수의 1로, *이진수의 0으로 변환합 니다. 결과는 “1000001”로 변환됩니다. 2. 바뀐 2진수를 10진수화 합니다. “1000001”을 10진수화 하면 65가 됩니다. 3. 아스키 번호가 65문자로 변환합니다. 즉 아스크번호 65는 대문자 'A'입니다. 참고로 대문자들의 아스키 번호는 'A'는 65번..

[알고리즘] 문장 속 단어

Q. 한 개의 문장이 주어지면 그 문장 속에서 가장 긴 단어를 출력하는 프로그램을 작성하세요. 문장속의 각 단어는 공백으로 구분됩니다. - 입력 설명 첫 줄에 길이가 100을 넘지 않는 한 개의 문장이 주어집니다. 문장은 영어 알파벳으로만 구성 되어 있습니다. - 출력 설명 첫 줄에 가장 긴 단어를 출력한다. 가장 긴 단어가 여러개일 경우 문장속에가 가장 앞쪽에 위 치한 단어를 답으로 합니다. - 입력 예제 1 it is time to study - 출력예제 1 study public static String solution(String s) { String answer = ""; int size = 0; String[] s1 = s.split(" "); for (String str : s1) { if ..

[알고리즘] 퀵 정렬 (quick sort)

1. 퀵 정렬 - 코드가 간결하고, 속도가 빠르다. (파이썬에서는 간결하지만, 자바에서는 그다지..) - 기준점을 정하여 기준점보다 작은 데이터는 왼쪽에, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다. - 이때 기준점은 보통 맨 앞을 선택한다. - 각 왼쪽, 오른쪽은 재귀 용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다. - 함수는 왼쪽 + 기준점 오른쪽을 리턴한다. - 분할 정복 알고리즘 전략을 사용하고 있다. 2. 알고리즘 구현 import java.util.*; public class QuickSort { public ArrayList sort(ArrayList data) { if (data.size() pivot) { rightArr.add(data.get(i)); } else {..