얼렁뚱땅 Data Science

이 문제는 2021 카카오 채용연계형 인턴십 채용을 위한 코테 문제 중 하나입니다. 생각보다 간결해 금방 풀 수 있을 것 같습니다! 문제설명 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다. 1478 → "one4seveneight" 234567 → "23four5six7" 10203 → "1zerotwozero3" 이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요. 참고로 각 숫자에 대응되는 ..

문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫..

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세..

이진 탐색 트리 (Binary Search Tree) 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값도가 큰 성질을 만족하는 이진트리 (중복데이터는 없는 것으로 가정) 정렬된 배열을 이용한 이진 탐색과의 비교 장점 : 데이터 원소의 추가, 삭제가 용이 단점 : 공간 소요가 큼 항상 O(logn)의 탐색 복잡도를 가지는가? --> NO 각 노드는 (key, value)의 쌍으로 키를 이용하여 검색 가능. 보다 복잡한 데이터 레코드로 확장 가능 연산의 정의 insert(key, data) - 트리에 주어진 데이터 원소를 추가 remove(key) - 특정 원소를 트리에서 삭제 lookup(key) - 특정 원소를 검색 ..

넓이 우선 순회의 원칙 수준이 낮은 노드를 우선으로 방문 같은 수준의 노드들 사이에서는, 부모노드의 방문 순서에따라 방문, 왼쪽 자식 노드 우선 따라서 재귀적 방법이 적합하지 않음! 한 노드를 방문했을때, 나중에 방문할 노드들을 순서대로 기록해 두어야 함 --> queue를 이용 구현 방법 (초기화) traversal

이진트리의 추상적 자료구조 연산의 정의 size() : 현재 트리에 포함되어 있는 노드의 수를 구함 재귀적으로 구하기 쉬움 전체 이진트리의 사이즈 = left subtree의 size() + right subtree의 size() + 1(자기 자신) depth() : 현재 트리의 깊이 (또는 높이)를 구함 이도 재귀적은 방법으로 쉽게 구할 수 있음 max(left subtree의 depth(), right subtree의 depth()) + 1 traversal() : 현재 트리의 노드를 방문하여 리스트에 추가함 깊이 우선 순회 (depth first traversal) 중위 순회(in-order traversal) : left subtree -> 자기 자신 -> right subtree 전위 순회(pr..

3강 : 배열 - 정렬과 탐색 1. 정렬 (Sorting) sorted() : 파이썬 내장함수, 정렬된 새로운 리스트 반환 sort() : 리스트 메서드, 해당 리스트 정렬 만약, 리스트가 string으로 이뤄져 있다면 알파벳 순서 따라서 정렬된다. 정렬 기준을 사용자가 직접 정하고 싶을때는 key 파라미터를 이용하여 정렬을 해준다. EX1) x의 길이를 기준으로 리스트를 정렬하여라. sorted(L, key = lambda x: len(x)) EX2) L이 name과 score로 이뤄진 딕셔너리가 든 리스트라 할 때, score를 기준으로 정렬하여라. L.sort(key = lambda x: x['score'], reverse = True) 2. 탐색 (Searching) 선형탐색 (Linear Sea..

Q. 우리는 왜 알고리즘과 자료구조를 배울까? 해결하고자 하는 문제에 따라 최적의 해법이 다 다르다. 자료구조 / 알고리즘을 통해 빠르고 효율적인 답을 얻을 수 있다. 알고리즘 [사전적 정의] 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합 [프로그래밍] 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택 선형 배열 (Linear Arrays) Python에서의 리스트는 다른 프로그래밍 언어들과는 달리 다양한 타입들의 원소를 가질 수 있다. 상수 시간이 걸리는 연산: 리스트의 길이와 상관없이 시간이 걸린다. (리스트 길이와 상관없이 수행됨) .pop( ) : 리스트 마지막 원소를 꺼내는 연산 .append( ) : 리스트 마지막에 괄호 안의 원소를 추가하는 연산 선형 시간이 걸리는 연산..