문제 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다. 다른 예로, "abcabcdede"와 같은..
문제 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다. 무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠..
부속질의(subquery) 하나의 SQL 문 안에 다른 SQL 문이 중첩된 질의 다른 테이블에서 가져온 데이터로 현재 테이블에 있는 정보를 찾거나 가공할 때 사용 필요한 데이터만 찾아서 공급해주는 부속질의가 성능이 좋음 SELECT SUM(saleprice) FROM Orders WHERE custid = (SELECT custid FROM Customer WHERE name = '박지성') 부속질의의 종류 명칭 위치 영문 및 동의어 설명 스칼라 부속질의 SELECT 절 scalar subquery SELECT 절에서 단일 값 반환 인라인 뷰 FROM 절 inline view table subquery FROM 절에서 결과를 view 형태로 반환 중첩질의 WHERE 절 nested subquery pre..
숫자 함수 함수 설명 ABS(숫자) 숫자의 절댓값 계산 CEIL(숫자) 숫자보다 크거나 같은 최소의 정수 FLOOR(숫자) 숫자보다 작거나 같은 최소의 정수 ROUND(숫자, m) 숫자의 반올림(m은 반올림 기준 자릿수) TRUNCATE(숫자, m) 숫자를 버림(m은 버릴 자릿수) LOG(n, 숫자) 숫자의 자연로그 값을 반환 POWER(숫자, n) 숫자의 n제곱 값을 계산 SQRT(숫자) 숫자의 제곱근 값을 계산 SIGN(숫자) 숫자가 음수면 -1, 0이면 0, 양수면 1 문자 함수 반환 구분 함수 설명 문자값 반환 함수 s : 문자열 c : 문자 n : 정수 k : 정수 CONCAT(s1, s2) 두 문자열 연결 LOWER(s) 문자열 소문자로 변환 LPAD(s, n, c) 문자열의 왼쪽부터 지정한 ..
우선순위 큐 높은 우선순위를 가진 원소를 먼저 처리하는 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 구현 방법 리스트를 이용한 구현 : 삽입 시간 O(1), 삭제 시간 O(N) 힙(heap)을 이용한 구현 : 삽입 시간 O(logN), 삭제 시간 O(logN) 힙(Heap)의 특징 완전 이진 트리 자료구조의 일종 항상 루트 노드(root node)를 제거 최소 힙(min heap) 루트 노드가 가장 작은 값을 가진다. 따라서 값이 작은 데이터가 우선적으로 제거된다. Heapq 최소 힙(min heap)의 구조 힙을 만들기 위해서는, 초기화된 리스트 [ ] 를 사용하거나(food = [ ]), heapify를 통해 값이 들어있는 리스트를 힙으로 변환 push item을 heap에 추..
SELECT 문의 기본 문법 SELECT [ALL┃DISTINCT] 속성이름(들) FROM 테이블이름(들) [WHERE 검색조건(들)] [GROUP BY 속성이름] [HAVING 검색조건(들)] [ORDER BY 속성이름 [ASC┃DESC]] WHERE 조건 술어 연산자 사용 예 비교 =,,= price LIKE '_구%' NULL IS NULL, IS NOT NULL price IS NULL 복합조건 AND, OR, NOT price < 2000 AND price IS NULL 와일드 문자의 종류 와일드 문자 의미 사..
리스트 N*M 크기의 2차원 리스트 초기화 array = [[0] * m for _ in range(n)] 인덱싱을 통해 자료형의 값을 얻을 수 있음 함수명 설명 시간 복잡도 append() 리스트에 원소 삽입 O(1) sort() 오름차순 정렬 O(NlogN) sort(reverse = True) 내림차순 정렬 reverse() 순서 뒤집기 O(N) insert(삽입할 위치 인덱스, 값) 특정 인덱스에 원소 삽입 O(N) count(특정 값) 특정 값을 가지는 데이터 개수 세기 O(N) remove(특정 값) 특정 값을 가지는 원소 제거(하나만) O(N) # 리스트에서 특정 값을 가지는 원소 모두 제거 remove_set = {3, 5} result = [i for i in a if i not in r..
