코딩 맛집

1. 투포인터(Two Pointer) 1번 부터 8번 까지의 공이 존재 할때, 그 중 2, 3, 4, 5, 6번 순차적으로 접근해야 할 경우, 시작 점, 끝 점 으로 편하게 데이터를 나타낼 수 있습니다. 만약, 부분합이 3이 되는 연속 수열의 갯수를 찾아야 한다면, 위 그림과 같이 찾는 값이 부분합 보다 크다면, 끝 인덱스를 1 증가 시켜 데이터의 범위를 증가 시키고, 찾는값이 부분합 보다 작거나, 같다면 시작 인덱스를 1 증가 시켜 데이터의 범위를 감소 시켜, 찾는 값의 가까워지도록 탐색 할수 있습니다. 단, 이 경우 수열의 모든 값은 양의 정수 이어야 합니다. 이러한 원리를 이용해서 1, 2, 3, 4로 이루어진 배열의 부분합이 3이 되는 경우의 수를 모두 구해 보겠습니다. 2. 부분 합이 3이 되는..

조합 알고리즘 1. 순열 표현 : nPr 서로 다른 n개 중의 r개를 뽑을때, 순서를 포함한 경우의 수 만약, 중복 가능한 n개 중 r개를 뽑으면, 중복 순열 2. 조합 표현 : nCr 서로 다른 n개 중의 r개를 뽑을때, 순서의 상관없 coding-food-court.tistory.com 1. 순열 표현 : nPr 서로 다른 n개 중의 r개를 뽑을때, 순서를 포함한 경우의 수 만약, 중복 가능한 n개 중 r개를 뽑으면, 중복 순열 2. 조합 표현 : nCr 서로 다른 n개 중의 r개를 뽑을때, 순서의 상관없이 뽑는 경우의 수 만약, 중복 가능한 n개 중 r개를 뽑으면, 중복 조합 3. 순열의 갯수 순열의 갯수는 위와 같은 공식으로 구할 수 있습니다. 그럼 factorial(팩토리얼) 재귀 함수를 구현하..

1. 순열 표현 : nPr 서로 다른 n개 중의 r개를 뽑을때, 순서를 포함한 경우의 수 만약, 중복 가능한 n개 중 r개를 뽑으면, 중복 순열 2. 조합 표현 : nCr 서로 다른 n개 중의 r개를 뽑을때, 순서의 상관없이 뽑는 경우의 수 만약, 중복 가능한 n개 중 r개를 뽑으면, 중복 조합 3. 순열 vs 조합 {A, B} 중의 2개를 뽑는 순열 : {A, B}, {B, A} {A, B} 중의 2개를 뽑는 조합 : {A, B} 4. 조합 점화식 조합은 다음과 같은 점화식이 있습니다. 이 점화식이 나온 이유를 살펴 보겠습니다. n개 중 r개를 뽑는 방법을 2가지로 나누어 생각해 보겠습니다. 1. 어떤 특정한 원소를 포함하고 뽑았을 때 2. 어떤 특정한 원소를 포함하지 않고 뽑았을 때 1. 어떤 특정한..

1. 문제 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미 합니다. 예를 들어 a = {-15, -4, 2, 8, 13} 이 있을 때 a[2] = 2이므로, 고정점은 2가 됩니다. 이때, 배열이 오름차순으로 정렬 되어 있을 때, 고정점을 출력 하시오. N개의 수열로 이루어져 있고, 둘째 줄에는 수열의 값이 주어집니다. 시간 복잡도는 O(logN) 으로 알고리즘을 설계 해야 합니다. (1

18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치�� www.acmicpc.net 1. 문제 K개의 바이러스 종류가 존재 합니다. N x N 의 실험실이 존재 합니다. 바이러스는 상, 하, 좌, 우로만 전파 될 수 있고, 전파 될 위치의 다른 바이러스가 이미 전파를 하였으면, 전파 할수 없습니다. 그리고 바이러스의 종류 번호가 낮은 번호가 우선순위를 가지고 전파 됩니다. 바이러스가 전파되지 않은 곳은 0이라고 합니다. 이때 N과 K, 그리고 실험실 칸 마다의 어떤 종류의 바이러스가 전파 되었는지 입력으로 주어 ..

1. 문제 A, B 두 사람이 볼링을 치고 있습니다. 볼링공의 갯수 N이 주어지고, 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재 합니다. 이때 M이 주어지고, 각각의 무게가 차례대로 주어졌을 때, 두 사람이 고를수 있는 볼링공의 조합의 갯수를 구하시오. 각 볼링공은 무게가 같아도 고유의 번호를 가지고 있습니다. 두 사람은 서로 무게가 다른 공을 고르려고 합니다. 첫째줄은 N과 M이 순서대로 공백을 기준으로 주어지고, 둘째줄에는 볼링공의 무게가 주어집니다. 2. 입력 5 3 1 3 2 3 2 3. 출력 8 4. 접근 1. 볼링공의 무게 별로 개수를 합쳐 집게 합니다. 2. 볼링공의 최소 무게인 1부터 최대 무게 M 까지 반복문을 돌면서 3. (무게가 i 인 볼링공의 개수) * (무게가 i 인 볼링공..

1. 문제 동전의 갯수 N개 와, 각 동전의 금액이 주어졌을 때, 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟 값을 출력 하세요. 첫째줄은 N의 값(1

소수의 판별 1. 소수(Prime Number) 란? 1보다 큰 자연수 중에서 자신 보다 작은 두개의 자연수를 곱하여 만들수 없는 자연수 입니다. 2. 소수(Prime Number)의 예 6 = 2 * 3 으로 6을 만들 수 있기 때문에, 소수(Prime Number.. coding-food-court.tistory.com 1. 에라토스테네스의 체(Sieve of Eratosthenes) 란? 에라토스테네스의 체(Sieve of Eratosthenes)는 N보다 작거나 같은 모든 소수(Prime)를 찾을때 사용 하는 알고리즘 입니다. 2. 알고리즘 순서 1. 2부터 N까지의 모든 수를 나열 합니다. 2. 나열되어 있는 수 중에서 제거 되지 않은 가장 작은 수 i를 선택 합니다. 3. i를 제외한 i의 배..

1. 소수(Prime Number) 란? 1보다 큰 자연수 중에서 자신 보다 작은 두개의 자연수를 곱하여 만들수 없는 자연수 입니다. 2. 소수(Prime Number)의 예 6 = 2 * 3 으로 6을 만들 수 있기 때문에, 소수(Prime Number)가 아닙니다. 7의 경우에는 1과 7을 제외 하고는 곱하여 7을 만들 수 없기 때문에, 7은 소수(Prime Number) 입니다. 3. 소수(Prime Number) 판별 java 소스 코드 public class PrimeNumber { public static void main(String[] args) { PrimeNumber pn = new PrimeNumber(); System.out.println(pn.isPrimeNumber(6)); Sy..

1. 문제 모험가 길드가 있습니다. N명의 모험가를 대상으로, 공포도를 측정 했을 때, 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 합니다. 이 때, 모험가 그룹의 최대 갯수를 출력 하시오. 첫째 줄에 N의 값과 둘째 줄의 N명의 대한 공포도가 입력으로 주어 집니다. (1