본문 바로가기

분류 전체보기

 (231)
[알고리즘] 비교기반 정렬의 한계/비교에 기반하지 않은 정렬 비교 기반 정렬의 시간복잡도 한계 위 트리는 이진 트리이다. (크기 비교에 따른 두 가지 경우의 수) 트리의 리프 수 L은 n개의 값을 정렬하는 모든 경우를 포함한다. L = n! ≤ 2^h h ≥ log L = log(n!) (n/2)^(n/2) ≤ n! ≤ n^n log(n!) = Ω(n log n) 따라서 두 원소의 비교에 기반한 정렬 알고리즘은 Ω(n log n)보다 빠를 수 없다. 비교에 기반하지 않은 정렬 1 : 버킷 정렬 정렬될 데이터가 자릿수 개념이 있다면, 이를 이용한다. 예를 들어 정렬될 데이터가 택배 주소(~시 ~구 ~동)라면, 처음 위치(~시)만 보고도 데이터 분류가 가능. 분류한 데이터를 각각 정렬하고, 이를 이으면 정렬 완료 시간 복잡도 : Best = c개의 버킷으로 모든 원소..
[알고리즘] 비교 기반 정렬 문제 정렬 문제→ 여러 방법이 존재하며, 방법마다 특징이 다름 → 시간복잡도, 최적성에 대해 증명이 쉬움 → n개의 서로 다른 수가 주어질 떄, 이들을 이동하여 점점 커지게(오름차순) 또는 점점 작아지게(내림차순)으로 만드는 문제 가정 : 정렬한 데이터가 담긴 배열의 각 원소를 O(1)시간에 접근 가능하다. (= 데이터가 메인 메모리에 저장되어 있다.) 버블 정렬 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해가면서, 큰 수가 오른쪽으로 가도록 교환함. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복 정확성 : 자명함 시간 복잡도 : 처음 가장 큰 원소를 구할 때 n-1번 비교, 두 번째 큰 원소를 구할 때 n-2번 비교 (n-1) + (n-2) + … + 1 =..
[알고리즘] 점화식의 이해(recurrence relation) 점화식 수열의 귀납적 정의와 유사 차이 : 인접한 항간의 관계만을 다루는 것은 아니다. 어떤 함수를 자신보다 더 작은 변수에 대한 함수 자신과의 관계로 표현한 것. (수열 = 정의역이 정수인 함수) 되부름, 혹은 유사한 방식으로 문제를 풀 때 걸리는 시간을 구하는데에 사용함 ex) T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1 An = T(n), An = 2A(n-1) + 1 점화식을 푸는 법 1. 반복 대치 : 주어진 조건을 이용하여 점점 작은 함수로 반복해서 대치하는 방법. 침착하게 꼼꼼히! 2. 추정 후 증명 : 점화식의 결론을 추정하고, 귀납법으로 증명함. 반복 대치가 복잡할 때 유용함. but 추정이 쉽지 않을 수 있음 3. 마스터 정리 : 점화식 공식. 여기에서는 다..
[알고리즘] 알고리즘 개요 및 정의 알고리즘의 정의 : 어떤 입력에도 정확한 출력을 유한한 시간 안에 내는 프로그램 어떤 입력 : 문제의 난이도나, 입력의 크기에 상관없이 문제를 풀 수 있다. 정확한 출력 : 문제가 요구하는 조건을 만족한다. 정답이 요구하는 조건이 무엇인지 명시할 수 있다. 유한한 시간 : 무한루프에 빠지지 않고 납득할 수 있는 시간에 종료한다. ex) 100명의 학생들의 시험 점수 중 최댓값을 구하시오. 수학적 귀납법→ 정확성 : 자명하다. → 시간 : n명의 점수를 읽으면, n-1번 비교. → max(지금까지의 최댓값, i+1번째 학생의 점수) ex) 100명의 학생들의 시험 점수 중 최빈값을 구하시오. ex) 입력 : U={1,2, … , n} 중에서 특정한 수 하나만 빼고 무작위의 순서로 n-1개의 숫자가 한번에 ..
[PGS] Lv.1 : 소수 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12977 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상..
[PGS] Lv.1 : 음양 더하기 https://school.programmers.co.kr/learn/courses/30/lessons/76501 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 return 하도록 solution 함수를 완성해주세요. 제한사항 absolutes의 길이는 1 이상 1,000 이하입니다. absolutes의 모든 수는 각각 1 이상 1,000 이하입니..
[PGS] Lv.0 (코딩테스트 입문) 6일차 문제 프로그래머스 문자열 뒤집기 string solution(string my_string) { string answer = ""; int len = my_string.length(); for(int i=1; i> n; for(int i=0; i
[PGS] Lv.0 (코딩테스트 입문) 5일차 문제 프로그래머스 옷가게 할인 받기 int solution(int price) { if(price >= 500000) price*=0.8; else if(price >= 300000) price*=0.9; else if(price >= 100000) price*=0.95; return (int)price; } 아이스 아메리카노 vector solution(int money) { vector answer; answer.push_back(money / 5500); answer.push_back(money % 5500); return answer; } 나이 출력 int solution(int age) { int answer = 2022+1-age; return answer; } 배열 뒤집기 vector soluti..
728x90

티스토리툴바