CodeKata

SQL

104.

• 작성한 쿼리

WITH num_cnt AS(
  SELECT
    num
    , COUNT(*) AS cnt
  FROM
    MyNumbers
  GROUP BY
    num
)
SELECT
  MAX(num) AS num
FROM
  num_cnt
WHERE
  cnt=1
;

→ HAVING을 써도 됨

WITH num_cnt AS(
  SELECT
    num
  FROM
    MyNumbers
  GROUP BY
    num
  HAVING
    COUNT(*) = 1
)
SELECT
  MAX(num) AS num
FROM
  num_cnt
;

참고할 만한 다른 풀이

SELECT IF(COUNT(*)=1,NUM,NULL) AS NUM
FROM MYNUMBERS
GROUP BY NUM
ORDER BY NUM DESC
LIMIT 1;

with cte as 
(select num
from MyNumbers
group by num
having count(num)=1 )

select case when count(*)>0  then max(num) else null end as num 
from cte 

select coalesce(max(num),null) as num from (select num from MyNumbers group by num having COUNT(num) = 1) as unique_num

→ MySQL에서 COALESCE 함수는 입력된 값 중 첫 번째로 NULL이 아닌 값을 반환하는 함수입니다. COALESCE 함수는 두 개 이상의 인수를 받을 수 있습니다. COALESCE(expr1, expr2, ...) xpr1이 NULL이 아니면 expr1을 반환하고, expr1이 NULL이면 expr2를 반환합니다. 만약 expr1과 expr2 모두 NULL이면, 다음 인수로 넘어가서 NULL이 아닌 값을 반환합니다. 이 과정을 인수가 끝날 때까지 반복합니다. 모든 인수가 NULL이면, COALESCE 함수는 NULL을 반환합니다. COALESCE 함수는 논리적인 IFNULL 함수와 같은 역할을 합니다. 다만 COALESCE 함수는 두 개 이상의 인수를 받을 수 있고, IFNULL 함수는 두 개의 인수만 받을 수 있습니다.

Python

42. 삼총사

• 작성한 코드

def solution(number):
    answer = 0
    for i in range(len(number)):
        for j in range(i+1,len(number)):
            for k in range(j+1,len(number)):
                if number[i] + number[j] + number[k] == 0:
                    answer += 1
    return answer

참고할 만한 다른 풀이

• itertools 모듈을 사용하면 combination을 이용하여 중첩 반복문을 하나의 반복문으로 줄일 수 있다.

from itertools import combinations
def solution(number):
    answer = 0
    for i in combinations(number,3):
        if sum(i) == 0:
            answer += 1
    return answer

from itertools import combinations
def solution(number):
    return sum([1 for c in list(combinations(number,3)) if not sum(c)])

• Backtracking
  • 해결책을 구하기 위해 모든 가능성을 시도해보는 것이 아니라, 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지 여부를 검사해가며 해답을 찾아가는 알고리즘

def solution(number):
    tot = 0
    def dfs(i, cnt, sum_num):
        nonlocal tot
        if cnt == 3 and not sum_num:
            tot += 1
            return
        if i == len(number):
            return
        if cnt < 3:
            dfs(i+1, cnt+1, sum_num + number[i])
            dfs(i+1, cnt, sum_num)
    dfs(0,0,0)        
    answer = tot
    return answer

백트레킹(Backtracking)

해를 찾는 도중 막히면 되돌아가서 다시 해를 찾는 기법

• 최적화 문제, 결정 문제에서 많이 사용
• 미로 찾기, n-Queen 문제, Map colouring, 부분 집합의 합 등

특징

• 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 탐색
  • 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않음
  • 해답의 가능성이 있으면 유망함
• 가지치기 사용 가능
  • 유망하지 않은 노드가 포함되는 경로는 고려하지 않는 기법
• 기본적으로 재귀의 성격을 띄는 형태

백트레킹과 DFS(Depth-First Search)깊이 우선 탐색)

• 백트레킹
  • 어떤 노드에서 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음으로써 시도 횟수 감소
  • 불필요한 경로의 조기 차단
  • N!가지의 경우의 수를 가진 문제에 대해 백트레킹에 가하면 일반적으로 경우의 수가 줄어들지만 최악의 경우는 처리 불가능
  • 모든 후보를 검사하지 않음
• DFS
  • 모든 경로를 추적
  • N!가지의 경우의 수를 가진 문제에 대해 DFS를 이용하면 처리 불가능

코드 형태

def 재귀함수(n):
	if 정답이면 :
		출력 or 저장
	else : 정답이 아니면 :
		for 모든 자식 노드에 대해서:
			if 정답에 유망하다면(답의 가능성이 있으면) :
				자식노드로이동
				재귀함수(n+1)
				부모노드로 이동

참고사항

• 유망 조건을 따로 함수로 만들어도 OK

def 백트래킹(n):
	if 정답이면 :
		출력 or 저장
	else :
		for 모든 자식 노드에 대해 :
			if 유망한지확인(m) :
				자식노드로 이동
				백트래킹(n+1)
				부모노드로 이동
def 유망한지확인(m):
	if 조건에 안맞으면 :
		return False
	return True

Python의 global과 nonlocal

변수의 범위(scope)

• 변수의 범위는 해당 변수를 어디에서 선언하느냐에 따라 결정됨
  • 전역(global/module) 범위 → 함수 외부
  • 지역(local/function) 범위 → 범위 함수 내부
  • 비지역(nonlocal/enclosing) → 외부 함수와 내부 함수의 사이

# outer(), inner() 함수 입장에서 전역(global) 범위
def outer():
    # outer() 함수 입장에서 지역(local) 범위
    # inner() 함수 입장에서 비지역(nonlocal) 범위
    def inner():
        # inner 함수 입장에서 지역(local) 범위

• 같은 범위 내에서는 자유롭게 변수에 접근할 수 있지만 다른 범위에서 선언된 변수에 접근할 때는 정해직 제약을 따라야 함
• 기본적으로 바깥쪽 범위에서 선언된 변수를 안쪽 범위에서 접근하는 건 되지만 안쪽 범위 내에서 선언된 변수를 바깥쪽 범위에서 접근하는 건 불가능

global_var = "전역 변수"
print(global_var) # 가능
def outer():
    nonlocal_var = "비전역 변수"
    print(global_var) # 가능
    print(nonlocal_var) # 가능
    def inner():
        local_var = "지역 변수"
        print(global_var) # 가능
        print(nonlocal_var) # 가능
        print(local_var) # 가능
    print(local_var) # 불가능 (NameError: name 'local_var' is not defined)
print(nonlocal_var) # 불가능 (NameError: name 'nonlocal_var' is not defined)
print(local_var) # 불가능 (NameError: name 'local_var' is not defined)

Variable Shadowing

• 변수 범위의 다른 중요한 특성은 서로 다른 범위에서는 변수 이름 충돌이 발생하지 않으며 안쪽 범위에서 바깥쪽 범위에서 선언된 변수와 동일한 이름의 변수를 생성할 수 있다는 점임

var = "전역 변수"
print(var)
def outer():
    var = "비지역 변수"
    print(var)
    def inner():
        var = "지역 변수"
        print(var)
    inner()
outer()
# 출력 결과:
# 전역 변수
# 비지역 변수
# 지역 변수

global 키워드

• 함수 안에서 변수 앞에 global 키워드를 붙이면 해당 변수는 함수 내에서 값을 변경하더라도 새로운 지역 변수가 되지 앟고 함수 밖에서 이미 선언된 전역 변수를 가리킴

num = 0
def change_num():
    global num
    num = 100
    print(num)
change_num()
print(num)
# 출력 결과:
# 100
# 100

nonlocal 키워드

• nonlocal 키워드도 global처럼 동일한 이름의 새로운 변수가 생성되는 것을 방지하기 위해 사용
• 차이점
  • global 키워드
    • 일반 함수 내에서 전역(global/module) 변수를 대상으로 사용
  • nonlocal 키워드
    • 중첩 함수 내에서 비지역(nonlocal/closing) 변수를 대상으로 사용

def print_num():
    num = 0
    def change_num():
        nonlocal num
        num = 100
        print(num)
    change_num()
    print(num)
print_num()
# 출력 결과:
# 100
# 100

→ 변수 앞에 nonlocal 키워드를 붙여주면 해당 변수는 중첩 함수 내에서 값을 변경하더라도 새로운 지역 변수가 되지 않고 함수 밖에서 이미 선언된 비전역 변수를 가리킴

회고

• Python3와 PyPy3 차이 읽어보기
  • PyPY3
    • 인터프리터의 느린 실행속도를 개선하기 위해(인터프리터 언어의 성능 향상을 목적으로) 도입
    • 자주 쓰이는 코드를 캐싱하는 기능이 있어 복잡한 코드(반복) 사용하는 경우 우세
  • 코드 상황에 맞추어 두 구현체(PyPy3, Python3)를 적절하게 사용하는 것이 효율적
    • 간단한 코드 → Python3가 메모리, 속도 측에서 우세
    • 복잡한 코드(반복) → PyPy3