![]()
시간 복잡도란?알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다.시간 복잡도는 낮으면 낮을수록 좋다. 예시만약 1차원 배열에 값이 들어가 있고, 특정 값을 배열의 맨 앞에서 순서대로 검색한다면 연산 횟수가 가장 적을 때와 가장 많을 때는? 연산 횟수가 가장 적은 경우다음 그림과 같이 찾는 값이 검색 시작 위치에 바로 있는 경우이다. 연산 횟수가 가장 많은 경우찾으려는 값이 아에 없거나 가장 마지막에 위치한 경우이다.이러한 경우 시간 복잡도는 연산 횟수가 가장 적은 경우 시간 복잡도가 낮다라고 표현할 수 있다. 빅오 표기법점근적 표기법인 상한선을 활용하여 시간 복잡도를 표기하는 방법이다.어떤 프로그램 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워 ..
요세푸스 순열이란요세푸스 문제에서 나온 순열이다.두 자연수 n과 k가 주어졌을 때 (n > k).n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다.남은 n - 1명에서 다시 다음부터 순서를 세서 k번째 사람을 모임에서 제외한다.이것을 아무도 남지 않을 때까지 계속해서 반복한다.이 때 제외되는 사람의 순서를 요세푸스 순열이라고 한다.마지막으로 제외되는 사람을 구하는 것이 요세푸스의 문제이다. Ex) n = 7, k = 3인 경우 3, 6, 2, 7, 5, 1 순서로 제거된 후 4가 마지막으로 남는다. Pythonn = 7, k = 3일 때 요세푸스 순열을 구하라.n, k = map(int, input().split());arr = [];result = [];ind..
![]()
유클리드 호제법이란두 양의 정수 혹은 두 다항식의 최대 공약수를 구하는 방법이다.호제법이란 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다. 알고리즘두 양의 정수 a, b (a > b)에 대하여 a를 b로 나눈 나머지를 r이라 하면, a, b의 최대 공약수는 b와 r의 최대 공약수와 같다.이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. Ex) 78696, 19332의 최대 공약수를 구하시오.더보기78696 = 19332 x 4 + 136819332 = 1368 x 14 + 1801368 = 180 x 7 + 108180 = 108 x 1 + 72108..
![]()
문제https://www.acmicpc.net/problem/11050 이항 계수란조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다.하나의 아이템에서 "뽑거나", "안뽑거나" 두 가지 선택이 있기 때문에 "이항"이라는 말이 붙었다. 이항 계수의 정의전체 집합에서 원소의 개수 n에 대해 k개의 아이템을 뽑는 이항 계수는 다음과 같이 정의한다.ex) 원소 개수 6개에 대해 2개의 아이템을 뽑는 이항계수는?- 6! / 4! / 2! = 720 / 24 / 2 = 15, 즉 15가 된다. 이항 계수의 성질2번, n개 중에서 k를 선택하는 것은 선택하지 않은 나머지 (n-k)개를 선택하는 것과 같다.3번, 이항 계수 정의를 유도하면 3번식 도출할 수 있다...
문제 설명두 배열이 얼마나 유사한지 확인해보려고 합니다. 문자열 배열 s1과 s2가 주어질 때 같은 원소의 개수를 return 하도록 solution함수를 완성해주세요. 제한 사항1 ≤ s1, s2의 길이 ≤ 1001 ≤ s1, s2의 원소의 길이 ≤ 10s1과 s2의 원소는 알파벳 소문자로만 이루어져 있습니다s1과 s2는 각각 중복된 원소를 갖지 않습니다. 입출력 예s1s2result["a", "b", "c"]["com", "b", "d", "p", "c"]2["n", "omg"]["m", "dot"]0 나의 풀이function solution(s1, s2) { let cnt = 0; for(let i = 0; i 이중 for문을 사용하여 s1의 모든 원소를 s2와 비교하여 카운트한다. 다..
문제 풀이정수가 담긴 리스트 num_list가 주어질 때, num_list의 원소 중 짝수와 홀수의 개수를 담은 배열을 return 하도록 solution 함수를 완성해보세요. 제한사항1 ≤ num_list의 길이 ≤ 1000 ≤ num_list의 원소 ≤ 1,000 입출력 예num_listresult[1, 2, 3, 4, 5][2, 3][1, 3, 5, 7][0, 4] 나의 풀이function solution(num_list) { let odd = 0; let even = 0; let result = []; for(let i = 0; i num_list 길이 만큼 for문을 돌려 짝수면 even 카운트를 +1, 홀수면 odd 카운트를 +1 한다.해당 카운트 된 even, odd를..
문제 풀이정수 n과 정수 배열 numlist가 매개변수로 주어질 때, numlist에서 n의 배수가 아닌 수들을 제거한 배열을 return 하도록 solution 함수를 완성해주세요. 제한사항1 ≤ n ≤ 10,0001 ≤ numlist의 크기 ≤ 1001 ≤ numlist의 원소 ≤ 100,000 입출력 예nnumlistresult3[4, 5, 6, 7, 8, 9, 10, 11, 12][6, 9, 12]5[1, 9 ,3, 10, 13, 5][10, 5]12[2, 100, 120, 600, 12, 12][120, 600, 12, 12] 나의 풀이function solution(n, numlist) { let result = [] for(let i = 0; i 빈 배열 result를 선언한 뒤..
문제 설명정수 배열 array가 매개변수로 주어질 때, 가장 큰 수와 그 수의 인덱스를 담은 배열 return 하도록 solution 함수를 완성해보세요. 제한 사항1 ≤ array의 길이 ≤ 1000 ≤ array 원소 ≤ 1,000array에 중복된 숫자는 없습니다. 입출력 예arrayresult[1, 8, 3][8, 1][9, 10, 11, 8][11, 2] 나의 풀이function solution(array) { let result = []; result.push(Math.max(...array), array.indexOf(Math.max(...array))) return result;}result란 빈 배열을 선언하고 큰 값과, 그 값의 인덱스를 push한다.Math.max 함..
