Algorithm/Sort

Algorithm/Sort
[핵심 유형] 카드 정렬
문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20)..
→2021.02.03
Algorithm/Sort
[카카오 코테] 실패율
실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로..
→2021.02.03
Algorithm/Sort
어떤 상황에서 어떤 정렬 알고리즘을 사용할까
알고리즘 별 정리 - 선택정렬 방법 : "남은 것 중에서 가장 작은 값을 앞으로 가져오기" 를 반복한다. 시간복잡도 : O(N^2) - 삽입정렬 방법 : 하나씩 보면서 그 지점의 왼쪽은 정렬이 되었다고 생각하고 왼쪽의 수와 비교하며 적절한 위치에 놓는 방법 시간복잡도 : O(N^2) 특징 : 왼쪽이 정렬되었다고 생각하고 진행하기 때문에, 거의 정렬이 되어있다면 매우 빠르게 동작한다. - 퀵 정렬 방법 : pivot보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 시간복잡도 : O(N log N) 특징 : 1. pivot을 기준으로 분할함 -> 데이터의 범위가 줄어듦. 그래서 빠르다 2. 최악의 경우(이미 정렬된 배열일 때) O(N^2)의 시간복잡도를 가진다. -> 양쪽으로 분할이 안이루어짐 - 계수 정렬 ..
→2021.01.29

• 이전
• 1
• 다음