1. 논의 배경

• 프로파일링 기반 추천 서비스 제공과 관련한 개인정보 침해 문제

  *프로파일링 :사용자의 데이터를 분석함으로써 특정 상황이나 영역에서의 관심이나 행동을 예상하는 것

• 소비자 선택권 제한

• 소비자의 행동패턴에 맞는 추천행태에 대안 불만과 불편

이용자 생활에 밀접하게 연관되어 있는 서비스이자, 디지털 경제 시대에 한 축으로 작용하고 있는 서비스이므로 법률과 제도가 어떤 방향으로 설정되느냐에 따라 산업의 발전과 침체, 이용자 편의의 제고와 하락이 결정될 것

2. 글로벌 법제 동향

1. 미국 「필터버블* 투명성 법안(Filter Bubble Transparency Act)」

*필터버블 : 이용자에게 맞춤형 정보를 제공하는 과정에서 추천 알고리즘으로 인해 이용자가 자신에게 부합하는 정보만 취득하게 되어, 비슷한 성향의 이용자끼리 한 버블 안에 다뤄지는 현상

• 목적 : 알고리즘이 이용자의 가치관이나 취향을 조종하지 못하도록 선택권 제공
  • ‘필터버블’에서 벗어날 선택권을 소비자들에게 제공

2. EU 「일반 개인정보 보호법(General Data Protection Regulation, ‘GDPR’)」

• 목적: 자동화된 의사결정을 규정, 법적 구속력 부여

  • 프로파일링의 정의

  • 프로파일링: 자연인의 업무성과, 경제적 상황, 건강, 개인적 선호, 관심사, 신뢰도, 행태, 위치 또는 이동에 관한 측면을 분석하거나 예측하기 위해 행해지는 경우로서, 자연인에 관련한 개인적인 특정 측면을 평가하기 위해 개인정보를 사용하여 이루어지는 모든 형태의 자동화된 개인정보의 처리(GDPR 4조)

  • 자동화된 의사결정 적용 배제권

  • 설명 요구건

그러나,

“법적 효력을 초래하거나 이와 유사하게 본인에게 중대한 영향을 미치는 경우”에 한하여 적용

• 구체적인 지침, 체계적 대응 X
• 머신러닝 알고리즘 사용 제한에 대한 비판

3. 국내 법제 동향

국내 법제 동향 분석

1. 프로파일링과 자동화된 의사결정 등의 개념 도입
2. 프로파일링과 추천 서비스등에 대한 사전동의 의무 부과
3. 이용자에게 적용 거부권을, 기업에게 알고리즘에 대한 설명 의무를 부과

• 서비스 개발 제한과 편의 저해 유발 비판론 존재

4. 글로벌 기업의 정책

1. 애플 “앱 추적 투명성(App Tracking Transparency, ATT)” 정책

• 광고 제공 목적으로 이용자 활동을 추적하고자 할 때, 권한 요청 사전 동의 필수

2. 구글 “프라이버시 샌드박스(Privacy Sandbox)” 정책

• 비밀리에 진행되는 데이터 수집 제한

• 개인정보를 제 3자에게 주는 것을 방지

• 구글의 서드파티 쿠키 대안 API

  • 토픽 API : 브라우저가 일주일간의 검색기록을 바탕으로 사용자의 주요 관심사를 나타내는 토픽(예: 피트니스, 여행 등)을 파악하는 기술

• 모바일 OS 사업자와 비사업자 간 데이터 보유 격차 심화 비판

• 광고 집행의 정확도 하락으로 인한 광고 비용 부담 증가

• 데이터 확보의 어려움이 더욱 커질 것으로 예상

5. 끄적끄적

확실히 민감한 문제임을 다시 실감한다.

개인화, 멋드러진 말임에는 틀림없으나 무서운 말이라는 게 새삼 명확해진다.

하지만 데이터를 다루고자 하는 사람으로서 해당 정책들을 반길 수가 없다....

데이터 수급이 더 어려워 진다,,,지금보다 더...? 있는 놈만 할 수 있는 세상...?

안된다. 그럴 수 없다..

그러면서도 내 정보는 털리기 싫다ㅎ.

모순덩어리.

🛠Problem Approach

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

• X가 5로 나누어 떨어지면, 5로 나눈다.
• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다

1. 26 - 1 = 25
2. 25 / 5 = 5
3. 5 / 5 = 1

🔑Solution

#Tabulation

n = int(input())

res =[0]*(n+1)
for i in range(2,n+1):
    res[i] = res[i-1]+1 # 1 빼기
    if i % 5 == 0: #5 나누기
        case1 = res[i//5]+1
        res[i] = min(res[i], case1)
    if i % 3 == 0: # 3 나누기
        case2 = res[i//3]+1
        res[i] = min(res[i], case2)
    if i % 2 == 0: # 2 나누기
        case3 = res[i//2]+1
        res[i] = min(res[i], case3)
print(res[n])

🛠Problem Approach

문제: 위에서 아래로

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오

입력조건

• 1≤ N ≤ 500
• N개의 숫자 입력받음

출력조건

내림차순 정렬

출력예시 65 54 34

🔑Solution

n = int(input())
num_lst = []

for i in range(n):
    num_lst.append(int(input()))

# 퀵정렬로 구현
def quick_sort(lst):
    l = len(lst)
    if l <= 1:
        return lst

    pivot = lst[0]
    # 큰 쪽
    left = [lst[j] for j in range(1,l) if lst[j] > pivot ]
    # 작은 쪽
    right = [lst[k] for k in range(l-1,1,-1) if lst[k] < pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)

ans = quick_sort(num_lst)
for i in ans:
    print(i, end=' ')

개선 코드

# ㅋ..
# 그냥 기본 라이브러리 사용하기...

num_lst = sorted(num_lst, reverse=True)

🛠Problem Approach

문제

동민이는 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러마리 괴물이 있어 이를 피해탈출해야 한다. 동빈이의 위치는 (1,1)이고, 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.

미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때, 동민이가 탈출하기 위해 움직여야하는 최소 칸의 개수는? 칸을 셀 때는 마지막 칸과 시작칸 모두 포함한다.

• 입력조건
  • 4≤ N, M ≤200
  • 공백없이 미로 값 입력
  • 시작 칸과 마지막 칸은 항상 1

✅ 최소거리를 구하는 과정이라 BFS를 사용 → 도착시, 바로 종료가 가능해서 유리

🙄 문제 : 최소거리를 측정하는데 필요 없는 곳을 조사할 때, count를 하는 문제

내 풀이

from collections import deque

n, m = map(int, input().split())
maze = [[int(i[j])for j in range(m)] for i in [input() for _ in range(n)]]
queue = deque()
visited = [[False if i[j] == 1 else True for j in range(m)] for i in maze]

cnt = 1
dr = [0,1,-1,0]
dc = [1,0,0,-1]

# 시작 위치 방문 및 큐 삽입
queue.append((0,0))
visited[0][0] = True

# bfs 시작
while queue:
    cur = queue.popleft()
    r, c = cur[0], cur[1]

    for i in range(len(dr)):
        nr = r + dr[i]
        nc = c + dc[i]
        if nr < 0 or nr >= n or nc < 0 or nc >= m:
            continue
        if maze[nr][nc] == 1 and not visited[nr][nc]: # 1이거나 미방문이면
            queue.append((nr,nc))
            visited[nr][nc] = True
            cnt += 1
            print("이프문 들어간다 후",nr,nc, '->', cnt)

            if nr == n-1 and nc == m-1: # 도착지에 도착하면 멈춤
                break
    if nr == n-1 and nc == m-1:
        break

    print("리얼현재",nr,nc, '->', cnt)

print(cnt)

🔑Solution

KEY

🌳 BFS는 시작 지점에서 가까운 노드부터 차례로 그래프의 모든 노드를 탐색한다.

🌳 모든 노드의 거리가 1로 동일하므로 모든 노드의 최단 거리값을 기록하면 해결 가능

from collections import deque

def bfs(x, y):
    queue = deque()
    queue.append((x,y))
    while queue: # 큐가 빌 때까지 반복
        x, y = queue.popleft()
        # 현재 위치에서 상, 하, 좌, 우 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 미로공간 벗어낫는가?
            if nx < 0  or nx >= n or ny < 0 or ny >=m:
                    continue

            # 괴물이 존재하는가?
            if graph[nx][ny] == 0:
                    continue

            # 방문하지 않은 곳인가?
            if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y] + 1 # 직전보다 한 노드 더 이동했으므로 -> 최단거리저장
                    queue.append((nx,ny)) # 움직인 좌표 큐에 삽입
    return graph[n-1][m-1] # 마지막 위치까지의 최단 거리 반환

n, m = map(int, input().split())
graph = [[int(i[j])for j in range(m)] for i in [input() for _ in range(n)]]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

print(bfs(0,0))

🐾 그래프에 직접 최소거리 저장하는 스킬

DFS(Depth-First Search)

깊이 우선 탐색 → 깊은 부분을 우선적으로 탐색한다

DFS는 스택 자료구조(혹은 재귀함수)를 이용한다.

1. 탐색 시작노드를 스택에 삽입, 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리
3. 방문하지 않은 인접 노드가 없다면, 스택에서 최상단 노드를 꺼냄
4. 더 이상 2~3번의 과정을 수행할 수 없을 때까지 반복

def dfs(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end=' ') # 현재 노드
    for i in graph[v]: # 현재 노드와 연결된 노드들 중에
        if not visited[i]: # 방문하지 않은 노드가 있다면
            dfs(graph, i, visited)

# graph는 2차원 리스트로 표현 (노드의 연결 정보)
# visited는 1차원 리스트로 표현 (노드의 방문 여부)

BFS(Breadth-First Search)

너비 우선 탐색 → 가까운 노드부터 우선적으로 탐색

BFS는 큐 자료구조를 이용한다.

1. 탐색 시작 노드를 큐에 삽입하고, 방문처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True # 현재 노드 방문처리
    while queue: # 큐가 빌때까지
        v = queue.popleft() # 큐에서 하나의 원소를 뽑아 출력
        print(v,end=' ')
        for i in graph[v]:# 현재 노드와 연결된 노드 중에
            if not visited[i]: # 방문하지 않은 노드가 있다면
                queue.append(i) #큐에 삽입
                visited[i] = True #방문처리

🏆Today Code Test

🛠Problem Approach

문제

NxM 크기의 어름틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1이다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다..

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요

🔑Solution

n, m = map(int, input().split())
icemap = [input() for i in range(n)]
icemap = [[int(i[j]) for j in range(m)] for i in icemap]
# visit = [True  if i[j] == 1 else False for i in icemap for j in range(m)]

def search(map, x, y):
  dx = [1,-1, 0, 0]
  dy = [0, 0, 1, -1]
  if x >= n or x < 0 or y < 0 or y >= m: # index 확인
    return False
  if map[x][y] == 0:
    map[x][y] = 1
    for i in range(4): #동서남북 접근
      search(map, x+dx[i], y+dy[i])
    return True
  return False

cnt = 0
# 모든 map 탐색
for i in range(n):
  for j in range(m):
    if search(icemap, i, j):
      cnt += 1
print(cnt)

탐색(Search)

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

• 대표적인 그래프 탐색 알고리즘 - BFS / DFS

자료구조

• 스택(Stack)

먼저 들어온 데이터가 나중에 나가는 형식 (선입후출, FILO)

⇒ 입구와 출구가 동일한 형태

삽입, 삭제 연산 _ append/pop/list 사용

👏 리스트를 거꾸로 출력하고 싶을 때 사용하는 slicing → a[::-1] / .reverse()

• 큐(Queue)

먼저 들어온 데이터가 먼저 나가는 형식 (선입선출, FIFO)

⇒ 입구와 출구가 뚫려있는 형태 (터널)

큐 연산 _ from collections import deque

→ 리스트 연산에서는 pop 연산 뒤에 원소의 위치를 조정하는 연산이 필요하기 때문: $O(k)$ 요구

• 삽입/삭제 _ append/popleft

• 재귀함수(Recursive function)

자기 자신을 다시 호출하는 함수

👏 RecursionError: maximum recursion depth exceeded while calling a python object

→ 컴퓨터 시스템 상, 스택 프레임 안 재귀함수가 메모리에 계속 쌓이므로 컴퓨터 자체의 메모리가 가득찰 수 있다. 이로 인해 문제가 발생할 수 있으므로 제한을 두는것

$\therefore$ 종료 조건을 반드시 명시해야 한다

• 대표적인 예시 : 최대 공약수계산

  유클리드 호제법

  • 두 자연수 A, B에 대하여 (A >B) A를 B로 나눈 값이 R이라 할 때, A와 B의 최대공약수는 B와 R의 공약수와 같다

      def gcd(a,b):
          if a % b == 0: # 종료조건
              return b
          else:
              return gcd(b,a%b)

• 모든 재귀함수는 반복문을 이용하여 구현이 가능하다

  → 반복문보다 유리한 경우도, 불리한 경우도 둘 다 존재한다.

• 컴퓨터가 함수를 연속적으로 호출하면, 컴퓨터 메모리 내부의 스택 프레임에 쌓아짐

  • 스택을 사용해야 할 경우, 스택 자료구조 대신 재귀함수 이용

🛠Problem Approach

문제

알파벳 대문자와 숫자 (0-9)로만 구성된 문자열이 입력으로 주어집니다. 이 때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다

🔑Solution

내 코드

string = input()
s = 0
new = []

for i in string:
    if i >= '1' and i <= '9':
        s += int(i)
    else:
        new.append(i)
new.sort()
print(''.join(new) + str(s))

영상코드

data = input()
result = []
value = 0

for x in data:
    if x.isalpha(): # 메서드 사용
        result.append(x)
    else:
        value += int(x)
result.sort()

# 숫자가 존재하면 문자열에 넣어줌
if value != 0:
    result.append(str(value))
print(''.join(result))

✅ 숫자가 존재하지 않을 경우 생각하지 않았음

✅ 메서드 사용하기!

• isalpha() # 알파벳
• isdigit() # 숫자
• isalnum() # 숫자 + 알파벳

🛠Problem Approach

문제

행복 왕국의 왕실 정원은 8 x 8 좌표 평면입니다. 나이트는 이동할 때 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없습니다.

나이트는 2가지 경우로 이동이 가능합니다.

• 수평 2칸 이동, 수직 1칸 이동
• 수직 2칸 이동, 수평 1칸 이동

이 때, 나이트가 주어진 위치에서 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하세요

🔑Solution

내 코드

cur = input()

x = ord(cur[0]) - 97
y = int(cur[1])-1

# 방향벡터 
dx = [2, 2, -2, -2, 1, 1, -1, -1]
dy = [1, -1, 1, -1, 2, -2, 2, -2]
cnt = 0

for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]

if nx < 8 and nx > -1 and ny < 8 and ny > -1: # 체스판 '안'인지 확인 (index 0부터 시작)
        cnt += 1
print(cnt)

강의 코드

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 이동할 수 있는 방향을 튜플로 설정 -> 이득은? 저장공간 이득
steps = [(-2,-1), (-2,1), (2,-1), (2,1), (-1,-2), (-1,2), (1,-2), (1,2)]
result = 0

# 각 위치로 이동이 가능한지 확인
for step in steps:
    next_row = row + step[0]
    next_column = column + step[1]

    if next_row >= 1 and next_row <= 8 and next_column >=1 and next_column <= 8:
            result += 1

print(restult)

🛠Problem Approach

문제

정수 N이 입력되면 00시 00분 00초 부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요

🔑Solution

✅ 접근 방법

가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제

따라서 시간을 1씩 증가시키며 3이 하나라도 포함되어 있는지 확인

⇒ 완전 탐색(Brute Forcing)

가능한 경우의 수 모두 검사해보는 탐색

for i in range(n+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i)+str(j)+str(k):
                cnt += 1

모든 경우의 수가 24 x 60 x 60 = 86400로,

파이썬이 1초에 연산할 수 있는 횟수인 2000만번 보다 매우 작기 때문에 완전 탐색이 가능하다.

내 코드

n = int(input())
cnt = 0

checker = sum([1 if '3' in str(j) else 0 for j in range(60)])

for i in range(n+1):
    if i == 3 or i == 13 or i == 23:
        cnt += 3600 # 60 x 60, 시간에 3이 들어가므로
    else:
        cnt += ((60 - checker) * checker) + (checker * 60) # 분 단위별 '3' 카운트
print(cnt)

Implementation(구현)

머리 속에 있는 알고리즘을 소스 코드로 바꾸는 과정

• 해당 유형 문제
  • 알고리즘 간단, 코드가 길어지는 문제
  • 실수 연산, 소수점 자리까지 컨트롤하는 문제
  • 문자열을 특정 기준에 따라 끊어 처리하는 문제
  • 적절한 라이브러리를 찾아 사용해야 하는 문제

Tools

**# Matrix**
for i in range(5):
    for j in range(5):
        print('(',i,',',j,')', end=' ')
    print()

**# direct vector**
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

x, y # 현재 위치

# 위치 이동
for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

• 해당 코드 Matrix

  

🏆Today Code Test

🛠Problem Approach

문제

여행가 A는 NxN 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당합니다.

여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작좌표는 항상 (1,1) 입니다.

L : 왼쪽으로 한 칸

R : 오른쪽으로 한 칸

U : 위쪽으로 한 칸

D : 아래로 한 칸

이 때, 여행가의 계획서는 띄어쓰기를 기준으로 적혀져 있습니다. NxN을 벗어나는 움직임은 무시됩니다. 여행자가 도착할 위치는 어디입니까?

메모리 제한 128MB

🔑Solution

생각없이 짠 코드

n = int(input())
plan = input().split()

dx = [-1,1,0,0]
dy = [0,0,-1,1]

x, y = 1, 1
for i in plan:
    p_x, p_y = x, y
    if i == 'L':
        x += dx[0]
        y += dy[0]
    elif i == 'R':
        x += dx[1]
        y += dy[1]
    elif i == 'U':
        x += dx[2]
        y += dy[2]
    else:
        x += dx[3]
        y += dy[3]
    if x < 1 or x > n or y < 1 or y > n:
        x, y =p_x, p_y

print(x,y)

개선 코드

n = int(input())
plan = input().split()

set_p = ['L','R','U','D']
dx = [-1,1,0,0]
dy = [0,0,-1,1]

x, y = 1, 1

for i in plan:
    for j in range(4):
        if i == set_p[j]:
                nx = x + dx[j]
            ny = y + dy[j]

    if nx < 1 or nx > n or ny < 1 or ny > n:
        continue

    x, y = nx, ny
print(x,y)

🛠Problem Approach

🔑Solution

n, m, k = map(int, input().split())
lst = sorted(list(map(int, input().split())),reverse=True)
total = 0 # 총 합
idx = 0
prev = 0 # 연속 횟수

# print(lst)
while m != 0: # 총 더할 횟수
    # print('m',m, 's',total)
    if k == prev: # 연속 횟수가 최대 연속 가능 수와 같으면
        total += lst[int(not(idx))]  # 두번째 큰수를 한번 더한다
        # print('+',lst[int(not(idx))])
        prev = 0 # 연속 횟수 초기화
    else:
        total += lst[idx] # 아닐경우, 연속 가능 횟수만큼 최대값 더하기
        # print(lst[idx])
        prev += 1 # 연속 횟수 증가
    m -= 1 # 더하기 연산 수 감소
print(total)

🛠Problem Approach

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

🔑My Solution

n_list = []
def list_prime(n):
    test = [1] * (2*n +1) # 1: 소수 0: 소수가 아닌 수
    # 0과 1은 소수가 될 수 없으므로
    test[0] = 0 
    test[1] = 0
    for i in range(2, 2*n + 1): # 가장 큰 수까지 전체 소수를 모두 구해놓기 위해
        for j in range(2, int(round(i**0.5, 0))+1): # 제곱근을 기준으로 약수는 대칭을 이루기 때문에
            if i % j == 0: # 나뉘면 소수가 아니므로
                test[i] = 0 
                break
    return test

while True:
    n = int(input())
    if n == 0: 
        break
    else:
        n_list.append(n)

p_list = list_prime(max(n_list)) # 매번 검사할 필요는 없다! : key -> 가장 큰 수만 검사
for n in n_list:
    print(p_list[n+1:2*n+1].count(1)) # index를 값으로 -> 조건문 대신 index slicing
# count로 잘린 리스트의 1의 값 리턴

🛠Problem Approach

문제 :

모험가 N명을 대상으로 '공포도'를 측정 하였습니다. '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험상황에서 제대로 대처할 능력이 떨어집니다. 이에 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 뗘날 수 있다고 규정 했습니다. 최대 몇 개의 모험가 그룹을 만들 수 있습니까?

조건 : 모든 모험가를 특정 그룹에 넣을 필요는 없다

입력 예시: 2 3 1 2 2

❗정당성 부여하기

그룹을 최대한 많이 만들어라 -> 작은 그룹원 수→ 많은 그룹을 만들기에 유리! -> 오름차순으로 sorting

n = int(input())
fear = sorted(list(map(int, input().split())))

g_cnt = 0 # 그룹수
max_fear = fear[0] # 그룹 내 최대 공포도
person = 0 # 그룹원 수
for i in range(1, len(fear)): # 모험가 수 만큼 돌면서
    person += 1 # 그룹원 추가 시키기
    if max_fear <= person: # 현재 그룹원 수가 그룹의 가장 큰 공포도보다 크다면 그룹원 모집 종료
        g_cnt +=1 # 그룹 추가
        person = 0 # 그룹원 초기화
        max_fear = fear[i] # 새로운 그룹의 가장 큰 공포도
print(g_cnt) # 모두 확인이 끝난 뒤 최종 그룹의 개수 리턴

🔑Solution

✅정당성

공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성한다!

n = int(input())
fear = list(map(int, input().split()))
fear.sort()

g_cnt = 0 # 그룹 수
person = 0 # 그룹원 수

for i in fear: # 공포도 낮은거 부터 확인
    person += 1 # 현재 그룹에 해당 모험가 추가
    if g_cnt >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
        g_cnt += 1 # 총 그룹의 수 증가
        person = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(g_cnt) # 총 그룹의 수 출력

✅ FeedBack

• max_fear를 굳이 설정해 주지 않아도 된다! → 이미 정렬되어 있기 때문에 항상 다음 index의 공포도가 크거나 같다!

• 명시성 더 생각하기 → 잘 짠 코드는 짧은 코드가 아니다!

🛠Problem Approach

문제

각 자리가 숫자(0-9)로 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 하나씩 모든 숫자를 확인 하며, 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램 (단, 모든 연산은 왼쪽부터 순서대로 이루어짐)

조건: 입력의 가장 큰 수는 항상 20억 이하의 정수가 되도록

❗정당성 부여하기 → 0 (다른 수가 곱해졌을 때 0으로 만듬) 혹은 1 (더하는게 곱하는것 보다 커짐) 을 제외할 시, 모두 곱할때 값이 훨씬 커짐! → 문자열의 시작이 0 이라면, 다음 인덱스의 값이 0이 아니더라도 최종값이 0이 될 수 있으므로 꼭 확인해주기

"""
! 자료의 type
int형은 21억 자리수 정수까지 커버 가능!
"""
s = input()
sum = int(s[0]) # 첫 자리 먼저 더해주기
for i in range(1,len(s)): # 0번쨰 index는 먼저 추가했으므로, 1번째 index 부터
    i = int(i)
    if i <= 1 or sum <= 1: # i가 0 혹은 1일때, sum이 0 혹은 1일때
        sum += i # 덧셈연산 수행
    else:
        sum *= i
print(sum)

🔑Solution

✅ 정당성

두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하는 것이 유리!

Greedy Algorithm

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

🔑 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구

🔑 정당성 분석이 중요!

→ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

: 최적의 해가 보장되지 않기 때문

ex) 거스름 돈

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재할 때, 손님에게 거슬러 줄 N원의 최소 동전의 개수를 구하시오. 단, N은 항상 10의 배수

• 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유? 가지고 있는 동전의 큰 단위가 항상 작은 단위의 배수이므로 → 작은 단위의 동전들을 종합해 다른 단위가 나올 수 없기 때문

cf) 800원을 거슬러야 하는데 화폐 단위가 500, 400, 100 인 경우

n = 1260
count = 0

#큰 단위 화폐부터 차례대로 확인
mon = [500, 100, 50, 10]

for coin in mon:
    count += n//coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수
    n %= coin # 해당 화폐 단위 보다 작은 단위가 필요한 돈

print(count)

화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도 O(k)

🏆Today Code Test

🛠Problem Approach

'''
문제 : 어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행
(단, 두번째 연산은 N/K로 나누어 떨어질때만!)

1. N - 1
2. N / K

! 정당성
# 2번을 수행하는 게 최소값을 만드는 데 유리 -> 나누기는 N 값을 크게 낮추므로
# 1번은 2번을 수행하지 못할때만 수행하는 방법 사용
'''

N, K = map(int, input().split())
count = 0

while N != 1: # N이 1이 아닐 동안 실행
    count += 1
    if N % K == 0: # N이 K의 배수이면
        N //= K # 몫을 N으로
    else:
        N -= 1

print(count)

시간복잡도 O($k$) : count의 횟수 만큼

🔑Solution

✅정당성 : N이 아무리 큰 수여도 K(K ≥ 2)로 계속 나눈다면 기하 급수적으로 빠르게 수를 줄일 수 있음!

## 코드 솔루션

N, K = map(int, input().split())
res = 0

while True:
    target = (N//K)*K # N보다 작은 K의 최대 배수 값
    result += (n - target) # K의 배수가 아닐 시, 1번 과정(-1)을 수행 해야하는 값
    n = target # K의 최대 배수 값
    if n < k: # K보다 작아서 나눠지지 않은 값이 있다면 반복문 탈출
        break
    result += 1 # N/K를 계산한 횟수 증가 시키기
    n //= k # K로 나눠 줄인 N값 계산하기

result += (n-1) # K보다 작아서 나눠지지 않은 값이 있다면 1이 될때까지 1단계 수행하는 값 더해주기

print(result)

시간복잡도 O($\log{k}$)

→ 한 반복문 안에서 1, 2단계가 동시 수행되기 때문에 큰 수 일수록 더 유리하다

• 1일 1커밋 (먼저 66일 도전)
• 1주일에 포스팅 1개 이상
• 부트캠프 내용 정리하기 & 복습
• 건강해지기
• 원하는 옷 마음껏 입기
• DS 취업
• Pyhton은 좀 하는 사람 되기
• TOY Project 3개월에 1개씩 - 4개
• 포트폴리오 사이트 만들기
• 부트캠프 끝나면 논문 스터디 하기
• IT 경향 따라가기
• 책 하루 10분이라도 읽기
• 기록하기
• 계획적으로 살기
• 만족스러운 미트 치기
• 자세 바르게 하기
• 코테 능숙해지기
• 여러가지 색 머리 해보기
• 돈 모으기
• 미국 여행가기
• 주말에도 공부하는 습관 들이기
• 나만의 코드 공부 방법 길들이기
• 아침에 일찍 일어나기
• 아침 공복 조깅하기
• 무릎 조심하기
• 매일 스픽하기
• 하루 30분씩 4번 매일 영어공부 하기
• 강단 가지기
• 야식, 과식 줄이기
• 술먹을땐 항상 미래 생각하면서 먹기_숙취 힘들다...
• 생각하는 시간 갖기
• 잉크펜 연습하기
• 운전 능숙해지기
• 보드 타러 가기
• 좀 더 정직한, 솔직한 사람 되기
• 배려심 키우기
• 말투 바꾸기

일단, 이 중에 반만 이뤄도 백퍼 성공한 1년이 될거다. 변하기도 하고 이리 저리 난관도 만나겠지만. 적어도 올해 배운건 '일단 해봐, 뭐든 될거야' 니까. 하면, 뭐든 될거다. 세상에 쓸데 없는 일은 없고, 다 하기 나름이니까 그니까 일단 해보자고~!

• Feature Engineering 의 목적을 이해 할 수 있다.
• pandas를 통해 문자열(string)을 다룰 수 있다.
• 데이터프레임에 .apply()를 사용하여 행을 수정하거나 새로 작업 할 수 있다.

Feature Engineering

is a process of extracting useful features from raw data using math, statistics and domain knowledge.

purpose

통계 분석 혹은 머신러닝, 더 나아가 딥러닝까지 대부분의 분석은

데이터에 있는 패턴을 인식하고, 해당 패턴들을 바탕으로 예측을 하기 때문에,

더 좋은 퍼포먼스를 위하여 더 새롭고, 더 의미있는 패턴을 제공하는 것

• one-hot encoding

Data Frame(tidy 형태)

• reference https://opentutorials.org/course/4548/28928

None

• reference https://daje0601.tistory.com/53

Na : Not availabe

Null : 아무것도 존재하지 않음이 할당되어 있는 상태

NaN : Not a Number _ pandas에서 결측치를 표현하는 방법

0 : Null, NaN, Na 등의 대체 수치로도 많이 사용되고, False의 역할도 하는 필요한 존재ㅎㅎ,,

undefined : 변수가 선언되었으나 아무것도 할당 되지 않은 상태

python에서는 Na, Null, NaN이 비슷한 의미로 결측치를 표현할때 사용

String

Replace

1. 숫자가 아닌 부분을 제거
2. 문자를 숫자로 형변환

string variable.replace('character want to change','replace character')
    s = 25,970
    s = s.repalce(',','') #25970 , method이므로 할당 다시 해줄것!

Type Casting(형변환)

int() # to inteager
float() # to float
str() # to string

# 함수로도 작성 가능

Apply

• 공식문서

  pandas.DataFrame.apply - pandas 1.3.2 documentation

column 단위로 대체하고 싶을때 사용

1. apply 안에 적용시킬 함수 선언
2. column에 apply 적용

dataFrame['column name'].apply(func)

, 제거하기

• list comprehenshion
  • reference https://www.notion.so/Note-2-Feature-Engineering-e794e210d8894b29861a6635147c14c7#1bf6fd8ba8824cf5817851d26ef0b5c4

int("".join([x for x in 변수.split(',')]))

• 자리수 구분 없이 csv 불러오기

pd.read_csv(thousands=',')

• split을 이용한 다른 방법

#QUiz
tmp = "12,578"
a,b = tmp.split(",")
revenue_19_2 = int(a+b)

pd.read_csv()

• reference pandas.read_csv - pandas 1.3.2 documentation [Pandas] pd.read_csv & pd.to_csv :: csv파일 불러오기 & 내보내기, 저장하기

pd.read_csv('파일명.csv', names = [], header=0, index_col = '인덱스로 지정할 column명')
names = [] #열 이름 지정, header의 역할 까지 함 
header # column명으로 지정할 index 
index_col = '인덱스로 지정할 column명'

lambda

• reference https://wikidocs.net/64

Have to study

• https://gooopy.tistory.com/44
• https://zephyrus1111.tistory.com/73
• https://m.blog.naver.com/hancury/220396495672
• https://m.blog.naver.com/wideeyed/221964700554