문제 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 풀이 저는 나머지 연산%을 통해 알고리즘을 구현하려고 하였지만 최대 범위값이 0으로 표현 되는 문제가 있어 코드가 복잡해지는 부작용이 있어 값을 하나씩 증가 하고 범위를 넘어가면 1로 초기화 해주는 방법으로 다시 풀었습니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader impo..

문제 https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 풀이 입력이 아래와 같을 경우를 풀어 봅시다 6 9 2 7 4 1 5 3 재료 개수 n : 6 갑옷을 만드는데 필요한 수 m : 9 갑옷 재료 번호 배열 arrNum : 2 7 4 1 5 3 갑옷 재료 2가지를 조합하여 숫자 9가 충족되는 조합은 몇가지 인지를 출력하면 됩니다. 투포인터로 쉽게 풀수 있는데요 이전에 배열 원소 값들을 오름차순 정렬 해줍니다. 그림 1과..

이진 탐색이란? 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘 입니다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교합니다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색합니다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교합니다. 해당 값을 찾을 때까지 이 과정을 반복합니다. 아래의 배열에서 17 을 이진 탐색으로 찾아보자. { 17, 28, 43, 67, 88, 92, 100, 200 } 중간 값 : 88 -> 작다 -> { 17, 28, 43, 67 } 중간 값 : 43 -> 작다 -> { 17, 28 } 중간 값 : 28 -> 작다 -> { 17 } 중간 값..

문제 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 풀이 입력값이 아래와 같다고 가정 해봅시다 4 2 GATA 1 0 0 1 임의로 만든 dna 문자열 GATA에서 사용할 부분문자열의 길이는 2입니다. 아래 그림1 처럼 GA, AT, TA 를 검사 하면 됩니다. 1001의 값은 ACGT의 충족 갯수의 값으로 부분 문자열이 충족해야할 조건은 그림2 처럼 A문자 1개 포함, T문자 1개 포함입니다. 즉, A,T가 포함되는 ..

알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측 합니다.ex) 시간제한이 2초면 약 2억번의 연산 안에 해결해야 된다는 뜻 시간 복잡도 유형 1. 빅-오 : 최악일때의 연산 횟수를 나타낸 표기법2. 빅-세타 : 보통(평균)일때의 연산 횟수를 나타낸 표기법3. 빅-오메가 : 최선일때의 연산 횟수를 나타낸 표기법 코딩테스트에서는 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격이기 때문에 빅-오 표기법( O(n) ) 기준으로 수행시간을 계산하는 것이 좋습니다.   알고리즘별 시간복잡도를 예를 들어보자면 버블정렬 O(n^2), 병합정렬 O(nlog n), 바이너리 서치 O(log n).  연산 횟수 계산..

에라토스테네스의 체 란? 수학에서 에라토스테네스의 체는 소수를 찾는 방법입니다. 고대 그리스 수학자 에라토스테네스가 발견하였습니다. 알고리즘 과정 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반..