조합은 n개의 index 중 0n, 1n, 2~n ... 순으로 append 하며, 고른 요소의 수(level)가 r에 도달하면 return하는 방식

example: 5C3

[1,]                                                               
    [1,2,]
        [1,2,3], [1,2,4], [1,2,5] 
    [1,3,]
        [1,3,4], [1,3,5]
    [1,4,]
        [1,4,5]
[2,]
    [2,3,]
        [2,3,4], [2,3,5]
    [2,4,]
        [2,4,5]
[3,]
    [3,4,]
        [3,4,5]

-> index의 시작점을 1씩 늘리는 재귀적 구조로 구현 가능.

# lst의 요소를 nCr
N = 5
R = 3
choose = []
lst = [1,2,3,4,5]

def combination(index, level):
    global N, R, choose, lst
    if level == R:
        print(choose)
        return
    for i in range(index, N):
        choose.append(lst[i])
        combination(i+1, level+1)
        choose.pop()

combination(0,0)

순열(Permutation)

순열의 경우 순서가 있다는 특성에 의해, index를 매번 0~n 순으로 append 하며 고른 요소의 수(level)가 r에 도달하면 return. 단, 중복을 피하기 위한 check 리스트가 필요하다.

example: 5P3

[1,]                                                               
    [1,2,]
        [1,2,3], [1,2,4], [1,2,5] 
    [1,3,]
        [1,3,2], [1,3,4], [1,3,5]
    [1,4,]
        [1,4,2], [1,4,3], [1,4,5]
    [1,5,]
        [1,5,2], [1,5,3], [1,5,4]
[2,]
    [2,1,]
        [2,1,3], [2,1,4], [2,1,5]
    [2,3,]
        [2,3,1], [2,3,4], [2,3,5]
    [2,4,]
        [2,4,1], [2,4,3], [2,4,5]
    [2,5,]
        [2,5,1], [2,5,3], [2,5,4]
[3,]
    [3,1,]
        [3,1,2], [3,1,4], [3,1,5]
    [3,2,]
        [3,2,1], [3,2,4], [3,2,5]
    [3,4,]
        [3,4,1], [3,4,2], [3,4,5]
    [3,5,]
        [3,5,1], [3,5,2], [3,5,4]
[4,]
    [4,1,]
        [4,1,2], [4,1,3], [4,1,5]
    [4,2,]
        [4,2,1], [4,2,3], [4,2,5]
    [4,3,]
        [4,3,1], [4,3,2], [4,3,5]
    [4,5,]
        [4,5,1], [4,5,2], [4,5,3]
[5,]
    [5,1,]
        [5,1,2], [5,1,3], [5,1,4]
    [5,2,]
        [5,2,1], [5,2,3], [5,2,4]
    [5,3,]
        [5,3,1], [5,3,2], [5,3,4]
    [5,4,]
        [5,4,1], [5,4,2], [5,4,3]

# lst의 요소를 nPr
N = 5
R = 3
choose = []
check = [False] * N
lst = [1,2,3,4,5]

def permutation(level):    # 매 요소에서 0~N까지 
    global N, R, choose, lst
    if level == R:
        print(choose)
        return
    for i in range(N):
        if check[i] == True:    # 중복된 요소라면 append 하지 않음
            continue
        choose.append(lst[i])
        check[i] = True        # 중복 표기
        permutation(level+1)
        check[i] = False    # 중복 해제
        choose.pop()

permutation(0)

중복조합, 중복순열

중복순열(nπr)의 경우 permutation 구현에서 중복요소 check만 빠지면 된다!

# lst의 요소를 nπr
N = 5
R = 3
choose = []
lst = [1,2,3,4,5]

def product(level):
    global N, R, choose, lst
    if level == R:
        print(choose)
        return
    for i in range(N):
        choose.append(lst[i])
        product(level+1)
        choose.pop()

permutation(0)

중복조합 nHr = n+r-1Cr = n+r-1Cn-1 로 변경해서 푼다! (고등수학 수준의 중복조합 설명: https://blog.naver.com/baboedition/220933436576)

로또

-> r = 6인 전형적인 조합문제

def comb(index, level):
    global choose, lst, k
    if level == 6:
        print(' '.join(choose))
        return
    for i in range(index, k):
        choose.append(lst[i])
        comb(i+1, level+1)
        choose.pop()

while True:
    case = input().split()
    if len(case) == 1:
        break
    k = int(case[0])
    choose = []
    lst = case[1:]
    comb(0,0)
    print()

암호 만들기

-> 조건이 주어진 조합 또는 순열의 문제는 조건부를 따로 함수로 구현해두는 것이 좋다. -> 조합 또는 순열을 만드는 알고리즘은 n개의 요소를 index 순으로 삽입하기 때문에, 문제에 '사전 순으로 출력' 등의 조건이 붙은 경우 반드시 처음부터 n개의 입력 요소를 정렬하고 시작하는 것이 좋다.

L, C = tuple(map(int,input().split()))
chars = sorted(input().split())
mo_chars = ['a', 'e', 'i', 'o', 'u']
choose = []

def is_possible(choose:list):
    mo = 0
    for char in choose:
        if char in mo_chars:
            mo += 1
    ja = len(choose) - mo
    return (mo >= 1 and ja >= 2)

def com(index, level):
    global L, C, chars, choose
    if level == L:
        if is_possible(choose):
            print(''.join(choose))
        else:
            pass
    for i in range(index, C):
        choose.append(chars[i])
        com(i+1, level+1)
        choose.pop()

com(0,0)

(+) 틀린 풀이: 가능한 조합을 모두 만들어놓은 다음, 조건에 맞지 않는 조합을 삭제하는 방식 -> list를 순회하면서 요소를 제거하면, 순회 도중 list의 indexing이 변경되면서 버그가 발생하므로 오답이 됨! 이러한 논리로 문제를 풀려면 조건에 맞는 것을 다른 list에 하나씩 추가하는 식으로 진행되어야 함. -> 문자열 각각을 오름차순으로, 문자열들끼리도 오름차순(사전순)으로 정렬하기 위해 sorted()를 두번 사용하는 것 보다는 초기 input부터 정렬시키는 것이 훨씬 효율적.

from itertools import combinations

L, C = input().split()
chars = list(input().split())

mo = ['a', 'e', 'i', 'o', 'u']

candidates = list(combinations(chars, int(L)))
for can in candidates:
    mo_num, ja_num = 0, 0
    for i in can:
        if i in mo:
            mo_num += 1
        else:
            ja_num += 1
    if mo_num < 1 or ja_num < 2:
        candidates.remove(can)    # candidates의 요소를 직접 삭제하면서 indexing에 문제가 발생함.
sol = []       
for ans in candidates:
    ans_str = ''
    for i in sorted(ans):
        ans_str += i
    sol.append(ans_str)

for i in sorted(sol):    # sorted를 두번 중복으로 사용 -> 비효율
    print(i)

-> 수정된 풀이

from itertools import combinations

L, C = map(int, input().split())
chars = input().split()

mo = {'a', 'e', 'i', 'o', 'u'}

candidates = list(combinations(sorted(chars), L))    # 초기값 chars를 처음부터 정렬
valid_candidates = []

for can in candidates:
    mo_num, ja_num = 0, 0
    for i in can:
        if i in mo:
            mo_num += 1
        else:
            ja_num += 1
    if mo_num >= 1 and ja_num >= 2:
        valid_candidates.append(''.join(can))    
        # candidates의 요소를 삭제하는 것이 아니라 조건에 맞는 요소를 valid_candidates에 보관

for ans in valid_candidates:
    print(ans)

Base Case와 Recursive Case가 함께 있지 않으면 재귀함수가 아니다.

단, 재귀함수는 함수 호출을 반복하면서 '이미 구한 값을 또 구하면서' 시간 복잡도가 증가할 수 있다. 그러므로 한번 구한 값은 저장해 불필요한 중복 계산을 피하는 것이 좋다. -> 메모이제이션

핵심: f(n)과 f(n-1)의 관계를 찾아 나타낼 수 있느냐!

위의 sum_func(n) 함수는 f(n) = f(n-1) + n의 관계

피보나치 함수

-> 가장 대표적인 재귀문제 '피보나치 함수'는 f(n) = f(n-1) + f(n-2)의 관계.

n = int(input())

fibo_list = [-1] * (n + 2)    # list 공간은 미리 확보해두어야 함. (2개의 초기값이 있으므로 n+2개 공간 확보)
fibo_list[0] = 0
fibo_list[1] = 1    # 메모이제이션을 위해 각 결과를 list에 저장

def fibo(n):

    global fibo_list

    if fibo_list[n] != -1:
        return fibo_list[n]    # 이미 답을 한 번 구했다면 저장한 답을 return

    fibo_list[n] = fibo(n-1) + fibo(n-2)     # 구한 답은 list에 저장한 다음 return
    return fibo_list[n]

print(fibo(n))

칸토어 집합

-> 이 문제는 [문자열] f(n) = f(n-1) + ' ' * (3 ** (n-1)) + f(n-1)의 관계.

def sol(n):
    if n == 0:
        return('-')
    return(sol(n-1) + ' ' * pow(3,(n-1)) + sol(n-1))

while True:
    try:
        N = int(input())
        print(sol(N))
    except:
        break

(+) 다른 풀이

ans = [' ' for i in range(13)]    # 문제의 최대만큼 공간 확보
ans[0] = '-'

# 미리 만들어놓기 -> ans[12]까지!
for i in range(12):
    ans[i+1] = ans[i] + (' ' * (3 ** i)) + ans[i]

while True:
    try:
        N = int(input())
        print(ans[N])
    except:
        break

-> Two-Stage Detectors

회귀/분류 기반(Regression/Classification based)

-> One-Stage Detectors

: 클라이언트로부터의 HTTP 요청을 적절한 함수나 메소드로 연결하여 처리하는 프로세스

• 라우트는 HTTP 요청 메서드(GET, POST, PUT, PATCH, DELETE)의 요청을 수락하고, 선택적으로 인수를 받을 수 있도록 정의된다.

WAS(Wab Application Server)

: 클라이언트/서버 환경에서 트랜잭션 처리 및 관리와 애플리케이션 실행 환경을 제공하는 미들웨어 소프트 웨어 서버.

• 웹 서버, 애플리케이션, 데이터베이스의 3계층 웹 컴퓨팅 환경으로 구축됨.
• ① 애플리케이션 실행 환경과 데이터베이스 접속 기능을 제공하고, ② 트랜잭션을 관리하며, ③ 업무를 처리하는 비즈니스 로직을 수행하고, ④ 다른 기종 시스템 간의 애플리케이션 연동 등을 수행한다.

Original Json File(예시)

15_X001_C011_1006_0.json

{
  "FILE NAME": "15_X001_C011_1006_0.jpg",
  "COLLECTION METHOD": "제작자료",
  "FORM": "이미지",
  "DATE": "2020-10-06 14:40:02",
  "GPS": "37.5212093997222/126.715606899722",
  "ID CODE": "C011",
  "RESOLUTION": "1920*1440",
  "focus distance": "4.32mm",
  "exposure time": "1/278sec",
  "Aperture values": "2.52",
  "Sensitivity iso": "50",
  "exposure method": "normal program",
  "MAKE": "samsung",
  "Camera Model Name": "SM-G977N",
  "Software": "G977NKSU4CTG1",
  "File Size": "589983",
  "DAY/NIGHT": "주간",
  "PLACE": "실외",
  "PROJECT SORTING": "생활폐기물",
  "BoundingCount": "1",
  "Bounding": [
    {
      "CLASS": "비닐류",
      "DETAILS": "과자봉지",
      "DAMAGE": "일부훼손",
      "TRANSPARENCY": "불투명",
      "Color": "176/137/113",
      "Shape": "평면형",
      "Texture": "부드러움",
      "Object Size": "소",
      "Direction": "원거리",
      "Drawing": "BOX",
      "x1": "540",
      "y1": "765",
      "x2": "827",
      "y2": "930"
    }
  ]
}

1. 이 중 class와 bbox만을 필요로 하는 YOLO format에서는 사실상 나머지 정보는 필요가 없고, "Bounding" 안의 "CLASS"(혹은 "DETAILS"), "x1", "x2", "y1", "y2"가 필요할 뿐이다. class 중에서도 자신의 필요에 맞는 class만 남기고 삭제하는 작업이 필요하다.
2. YOLO format의 bbox가 nomalize된 값인 것을 고려하면 "RESOLUTION"(사진의 width와 height) 정보도 필요하나, 이는 이미지를 직접 불러와 읽어들이도록 한다.
3. "Drawing"이 "BOX"가 아니라 "POLYGON"인 것은 제외한다. 이 경우 bbox annotation을 제공하지 않은 것과 같으므로... 어쩔 수 없이 직접 bbox를 라벨링 할 수 밖에 없다.

1. labels와 images 각각 원하는 디렉토리에 옮기기

import os
import shutil

orig_label_dir = 'path/to/생활 폐기물 이미지/Validation/[V라벨링]라벨링데이터'
label_dir = 'path/to/labels'

for curDir, dirs, files in os.walk(orig_label_dir):
    for f in files:
            shutil.move(os.path.join(curDir, f), os.path.join(label_dir, f))

orig_image_dir = 'path/to/생활 폐기물 이미지/Validation'
image_dir = 'path/to/images'

for curDir, dirs, files in os.walk(orig_image_dir):
    for f in files:
        shutil.move(os.path.join(curDir, f), os.path.join(image_dir, f))

• os.walk()의 출력
  • curDir: 파일이 존재하는 모든 디렉토리 경로(str, 파일명은 미포함)
  • dirs: 모든 디렉토리 명(list)
  • files: 모든 디렉토리별로 존재하는 모든 파일명(list)

2. 필요한 class들 정의하기

-> image는 AI hub에서 부분적으로는 골라서 받을 수 있지만, label은 내 task에 필요하지 않은 것들도 한번에 받도록 되어 있으므로, 맞는 image가 없는 label data는 먼저 삭제한다.

filenames = os.listdir(image_dir)
names = [name[:-4] for name in filenames]    # '파일명.jpg'에서 '파일명'만 남김

for curDir, dirs, files in os.walk(label_dir):
    for f in files:
        if f[:-5] not in names:    # '파일명.Json'에서 '파일명'으로 판단하고 없으면 삭제
            os.remove(os.path.join(curDir, f))

-> 남은 label들이 어떤 클래스를 갖고 있는지 먼저 추리고 파악한다.

import json
labels = []
for file in names:
    json_path = os.path.join(label_dir, file+'.Json')

    # json 파일 내용에 한글이 포함되어 있으므로 encoding 추가
    with open(json_path, 'r', encoding='utf-8') as f:    
        json_data = json.load(f)
    for obj in json_data['Bounding']:
        labels.append(obj['DETAILS'])
label_set = set(labels)    # "DETAILS"를 모두 저장한 다음 set 자료형으로 중복 제거
print(label_set)

-> task 정의에 따라 label_set들을 class를 0부터 시작하는 정수 번호로 지정해주는 함수를 정의한다.

def class_choose(cls):
    bottle = ['기타술병', '맥주병', '물병', '박카스병', '소주병', '음료수병', '페트병']
    can = ['맥주캔', '음료수캔', '통조림캔', '커피캔', '참기름캔', '스팸류']
    if cls in bottle:
        return 0
    elif cls in can:
        return 1
    else:
        return 2

3. YOLO format annotation txt 파일 만들기

import json
import cv2
for file in names:
    json_path = os.path.join(label_dir, file+'.Json')
    img_path = os.path.join(image_dir, file+'.jpg')
    image = cv2.imread(img_path)
    h,w,_ = image.shape    # 이미지 처리에서는 이미지 shape를 height, width, channal 순으로 정의한다.
    with open(json_path, 'r', encoding='utf-8') as f:
        json_data = json.load(f)
    objs = []
    for obj in json_data['Bounding']:
        if obj['Drawing'] != 'BOX':    # bbox가 아닌 polygon 등 다른 방식의 annotation 제외
            break
        cls = obj['DETAILS']
        cls_num = class_choose(cls)
        x1 = int(obj['x1'])
        x2 = int(obj['x2'])
        y1 = int(obj['y1'])
        y2 = int(obj['y2'])
        center_x = (x1 + x2) / (2*w)
        center_y = (y1 + y2) / (2*h)
        width = (x2 - x1) / w
        height = (y2 - y1) / h    # YOLO format의 normalized bbox
        objs.append(f'{cls_num} {center_x} {center_y} {width} {height}\n')
    with open('path/to/yolo/labels/{file}.txt', 'w') as f:
        f.writelines(objs)

이후 적절히 annotation file과 image file의 경로를 맞추고, 라벨링 상태를 확인한 다음 YOLO를 훈련시키면 된다.

에러를 예외처리하는 것큼이나 코드 실행 프로세스에서 예상과 다르게 돌아가는 예외를 처리하는 방법도 필요하므로, raise 키워드로 예외를 발생시키기도 한다.

에러가 발생해 프로그램이 멈추지 않게 하기 위해,

1. 예외는 반드시 처리되어야 하고,
2. 그에 대한 로그가 남아야 하며,
3. 예상하지 못한 프로세스에 관해 예외를 발생시키기도 한다.
4. Python에서는 예외가 없는 것을 가정하고 프로그램을 작성 후, 런타임에서 예외가 발생 시 예외 처리하는 것을 권장한다.

에러의 예시

• SyntaxError: 문법적 오류
• TypeError: 자료형에 맞지 않는 연산을 수행하려고 할 경우

  x = [1,2]
  y = (1,2)
  print(x + y)    # TypeError: can only concatenate list (not "tuple") to list

• NameError: 참조할 변수가 선언되어 있지 않은 경우
• IndexError: 인덱스 범위를 벗어난 호출을 시도할 경우

  x = [50, 70, 90]
  print(x.pop())
  print(x.pop())
  print(x.pop())
  print(x.pop())    # IndexError: pop from empty list

• KeyError: 존재하지 않는 키를 호출할 경우

  dic = {'name': 'Lee', 'Age': 41, 'City': 'Busan'}
  print(dic['hobby'])    # KeyError: 'hobby'
  print(dic.get('hobby'))    # dictionary에서 get을 쓰는 것이 권장됨->KeyError 대신 'None'을 출력하므로.

• ValueError: 존재하지 않는 값을 호출할 경우

  x = [10, 50, 90]
  x.remove(200)    # ValueError: list.remove(x): x not in list

• AttributeError: 모듈, 클래스에 있는 속성을 잘못 사용할 경우

  import time
  print(time.time2())    # AttributeError: module 'time' has no attribute 'time2'. Did you mean: 'time'?

  예외처리 기본 문법

  try : 에러가 발생 할 가능성이 있는 코드 실행 except 에러명1: 여러개 가능 except 에러명2: else : try 블록의 에러가 없을 경우 실행 finally : 항상 실행

예외처리 패턴 4가지

1. 발생할 에러를 예측해서 명시하는 경우(권장)

   name = ['Kim', 'Lee', 'Park']
   

try: z = 'Kim' # 'Cho' x = name.index(z) print('{} Found it! {} in name'.format(z, x + 1)) except ValueError: print('Not found it! - Occurred ValueError!') else: print('Ok! else.')

2. 에러를 명시하지 않고 예외처리하는 경우

name = ['Kim', 'Lee', 'Park']

try: z = 'Cho' # 'Cho' x = name.index(z) print('{} Found it! {} in name'.format(z, x + 1)) except: print('Not found it! - Occurred ValueError!') else: print('Ok! else.')

3. 모든 에러를 Exception 객체로 묶어 표기하는 경우

name = ['Kim', 'Lee', 'Park']

try: z = 'Cho' # 'Cho' x = name.index(z) print('{} Found it! {} in name'.format(z, x + 1)) except Exception as e: print(e) # 어떤 에러 발생했는지 로그 남기기 print('Not found it! - Occurred ValueError!') else: print('Ok! else.') finally: print('Ok! finally')

4. 에러-예외처리 직접 발생 시키는 경우

try: a = 'Park' if a == 'Park': print('OK! Pass!') else: # 프로그램 목적상 'Park'이 아니면 문제가 발생한다면 에러로 처리할 수 있다 raise ValueError except ValueError: print('Occurred! Exception!') else: print('Ok! else!')

• python-ex 라는 이름의 가상환경 만들기: 가상환경을 만들 폴더로 이동해 다음 명령어 실행

  $ python -m venv python-ex

• python-ex 가상환경 실행

  $ cd python-ex/Scripts
  $ activate

• VS Code에서 python-ex 사용: commend palette(ctrl+shift+p) 에서 'python interpreter' 검색 후 선택, 또는 python-ex이 설치된 폴더에서 Scripts>python.exe 실행

• python-ex 가상환경에서 패키지 설치: 가상환경을 실행한 다음 pip

• 'Fatal error in launcher: Unable to create process using~' 오류가 생긴다면 python -m pip install --upgrade --force-reinstall pip으로 현재 가상환경에서 pip 강제 재설치

• python-ex 가상환경 종료

  $ deactivate

• 소스 코드 파일을 실행파일, 라이브러리 등의 Object 파일로 바꾸는 작업을 컴파일이라고 한다. 코드에 문법적인 오류가 있으면(컴파일되지 않으면) 실행되지 않는다. cf. 소스 코드 파일을 컴퓨터에서 실행할 수 있는 독립 소프트웨어 산출물로 변환하는 과정을 빌드라고 하며, 빌드 단계에 컴파일이 포함된다. ex. Java의 경우 class 파일이 생성된다.
• 컴파일 단계와 실행 단계가 분리되어 있으며, 컴파일은 단 한번 실행되고 실행은 컴파일 된 것을 실행만 하면 되므로 실행 속도가 빠르다.

인터프리터 언어: 컴파일러를 거쳐 기계어로 변환되지 않고 바로 실행되는 언어

• 인터프리터가 한 줄씩 해석해서 바로 실행된다. 문법적인 오류가 있어도 실행은 시작된다.
• 실행파일을 별도로 생성하지 않기 때문에 실행 시마다 인터프리트 과정이 반복 수행되어 실행 속도가 느리다.

스크립트 언어는 응용프로그램을 제어하는 언어, 즉 언어의 사용처가 어플리케이션, SW인 언어를 말하는 것이다. 언어의 기계적 해석 방식의 차이로 컴파일 언어와 인터프리터 언어를 구분하는 것과는 다른 개념. ex. JavaScript는 웹 브라우저 위에서 웹 브라우저를 제어하는 언어이므로 스크립트 언어이자, 인터프리터가 한 줄씩 번역해 실행하는 인터프리터 언어이다.