탐욕 알고리즘(Greedy Algorithm)이란? Greedy는 탐욕스러운, 욕심 많은 이라는 뜻이다. 탐욕 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법만 의미한다. 그리디 알고리즘 문제로 유명한 거스름돈 문제를 보면서 이해해 보자. 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 1...

중첩질의 in과 exists연산자는 중첩질의 중 하나인데, 중첩질의란 SQL문을 다른 SQL문 안에 중첩하여 사용하는 질의를 의미한다. 이때 내부에 포함된 SQL문을 부 질의(sub query) 또는 내부 질의(inner query)라 하며 부 질의를 갖는 SQL문을 외부 질의(outer query)라고 한다. 스키마 course(course_...

문제 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라. 입력 [1,2,3] 출력 [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 풀이1 (DFS를 활용한 순열 생성) 순열은 모든 가능한 경우를 그래프 형태로 나열할 수 있기 때문에 그래프로 표현하면 다음과 같다....

문제 인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다. 입력 1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4 출력 1 -> 4 -> 3 -> 2 -> 5 -> NULL 풀이 ( 반복 구조로 노드 뒤집기) 이 풀이에서는 st...

정규화(normalization)란? 정규화란 불필요한 데이터의 중복을 피하기 위해 스키마를 분해하는데, 이 과정을 정규화라고 한다. 정규형의 종류 정규화는 테이블에 대한 삽입, 삭제, 수정 등의 연산으로 인해 발생할 수 있는 이상현상을 방지해준다. 그리고 각 단계별 정규화 과정을 통해 분해된 테이블들을 정규형(normal form)이라고...

문제 역순으로 저장된 연결 리스트의 숫자를 더하라. 입력 (2 -> 4 -> 3), (5 -> 6 -> 4) 출력 7 -> 0 -> 8 설명 342 + 465 = 807 풀이 1 (자료형 변환) 입력으로 들어오는 두 리스트를 역순으로 된 연결리스트로 변환 후 두 리...

문제 정렬되어 있는 두 연결 리스트를 합쳐라. 입력 1 -> 2 -> 4, 1 -> 3 -> 4 출력 1 -> 1 -> 2 -> 3 -> 4 -> 4 풀이 1 (재귀 구조로 연결) 입력으로 들어오는 두 연결 리스트는 정렬된 리스트기 때문에 첫 번째 값부터 서로 비교하면서 재귀 형태로...

문제 연결 리스트가 팰린드롬 구조인지 판별하라. 입력 1 -> 2 출력 false 입력 1 -> 2 -> 2 -> 1 출력 true 풀이1 (리스트 변환) 파이썬 리스트의 pop()연산을 통해 연결 리스트의 입력을 리스트로 변환하여 풀 수 있다. 먼저 연결 리스트를 구현한 ListNode클래스는...

문제 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. (단, 나눗셈을 사용하지 않고 O(n)에 풀이하라) 입력 [1,2,3,4] 출력 [24, 12, 8, 6] 풀이 (왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈) 이 문제의 제약사항인 나눗셈을 사용하지 않고 O(n)에 풀이하라고 ...

문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 [0,1,0,2,1,0,1,3,2,1,2,1] 출력 6 풀이 1 (투포인터 이용) 이 문제는 투포인터를 이용하여 풀이가 가능하다. 왼쪽에서 출발하는 왼쪽 포인터와 오른쪽에서 출발하는 오른쪽 포인터를 두고, 최대 높이 지점까지 가운데로 이동한다...