본문 바로가기

알고리즘8

[코테] 순위 Lv.3 (40%) 문제 ###### 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. ##### 제한사항 - 선수의 수는 1명 이상 100명 이하입니다. - 경기 결과는 1개 이상 4,500개 이하입니다. - results 배열 각 행 [A, .. 2024. 2. 19.
선택정렬 알고리즘 구현 (Python) 선택 정렬 위키에 있는 이미지인데 보면서 뭔가 뿌듯하다 정렬 알고리즘 비교 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 간단함 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때 가장 빠름 퀵 정렬 O(NlogN) O(N) 대부분의 경우 가장 적합함 충분히 빠름 계수 정렬 O(N+K) O(N+K) 데이터 크기가 한정된 경우에만 사용 가능 매우 빠름 알고리즘 코딩테스트를 준비하면서 기본이 되는 정렬 알고리즘을 비교해 보았다. 선택 정렬은 O(N^2)의 시간 복잡도이므로 N이 증가할수록 제곱으로 증가한다 장점: 구현이 쉽고, 데이터가 이미 정렬된 경우 빠르게 정렬 단점: 입력 데이터가 역순으로 정렬되어 있을 때, 최악의 경우 O(N^2)의 성능 (.. 2023. 12. 11.
[코테] 콜라 문제 Lv. 1 (67%) 문제 설명 오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다. 정답은 아무에게도 말하지 마세요. 콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가? 단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다. 문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있.. 2023. 8. 31.
[코테] 옹알이 (1) Lv. 0 (32%) 문제 설명 머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ babbling의 길이 ≤ 100 1 ≤ babbling[i]의 길이 ≤ 15 babbling의 각 문자열에서 "aya", "ye", "woo", "ma"는 각각 최대 한 번씩만 등장합니다. 즉, 각 문자열의 가능한 모든 부분 문자열 중에서 "aya", "ye", "woo", "ma"가 한 번씩만 등장합니다. 문자열은 알파벳 소문자로.. 2023. 8. 27.
[코테] 정수를 나선형으로 배치하기 Lv. 0 (45%) 문제 설명 양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n^2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요. 제한사항 1 ≤ n ≤ 30 입출력 예 n result 4 [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]] 5 [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]] 입출력 예 설명 입출력 예 #1 예제 1번의 n의 값은 4로 4 × 4 배열에 다음과 같이 1부터 16까지 숫자를 채울 수 있습니다.행 .. 2023. 8. 27.
[코테] 가장 긴 접두어이자 접미어(LPS) 문제 문자열을 입력받아 다음의 조건을 만족하는 LPS*를 찾아 그 길이를 리턴해야 합니다. LPS: 주어진 문자열의 가장 긴 접두어이자 접미어(Longest Prefix which is also Suffix) non-overlapping: 접두어와 접미어는 서로 겹치는 부분이 없어야 합니다. 다시 말해, prefix와 suffix는 문자열의 동일한 인덱스에 위치한 문자를 요소로 가지면 안 됩니다. 입력 인자 1 : str string 타입의 임의의 알파벳 소문자 문자열 ( str.length는 60,000 이하 출력 number 타입을 리턴해야 합니다. 주의사항 prefix(접두어)는 문자열의 첫 인덱스부터 시작하는 모든 부분 문자열을 의미합니다. suffix(접미어)는 문자열의 마지막 인덱스부터 시작하.. 2023. 2. 5.
[코테 js] treeBFS 너비 우선 탐색(BFS, Breadth First Search) 문제 임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 너비 우선 탐색(BFS, Breadth First Search)을 합니다. 이때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다. let bfs = function (node) { // TODO: 여기에 코드를 작성합니다. }; // 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요. let Node = function (value) { this.value = value; this.children = []; }; // 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다. // membership check(중복 확인)를 따로 하지 않습니다. Node.prototype.a.. 2023. 1. 18.
[코테 js] treeDFS 깊이 우선 탐색 문제 문제 임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다. 인자1 : node 'value', 'children' 속성을 갖는 객체 (Node) 'node.value'는 number 타입 'node.children'은 Node를 요소로 갖는 배열 입출력 예시 let root = new Node(1); let rootChild1 = root.addChild(new Node(2)); let rootChild2 = root.addChild(new Node(3)); let leaf1 = rootChild1.addChild(new Nod.. 2023. 1. 9.

티스토리툴바