반응형

문제 풀이

dp와 dfs를 함께 사용해야하는 문제이다.

1. dp 배열에 해당 칸을 방문한 적이 없으면 -1, 있으면 해당 칸부터 (0,0)까지 갈 수 있는 현재까지 발견한 경로의 수를 담는다.

2. 위의 dp 배열과 지도를 기반으로 dfs를 진행한다.

  2-1) 이동 가능한 칸의 dp값이 -1이라면 방문한다.

  2-2) 이동 가능한 칸의 dp값이 0이라면 방문하지 않는다. 해당 칸에서는 (0,0)까지 갈 수 없다.

  2-3) 이동 가능한 칸의 dp값이 1이상이라면 현재 칸의 dp값에 이동 가능한 칸의 dp값을 더해준다. 현재 칸에서 (0,0)까지 갈 수 있는 방법의 수는, 현재 칸에서 이동할 수 있는 칸들에서부터 (0,0)까지 갈 수 있는 경로의 합이다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
sys.setrecursionlimit(10000)
# 0: 상, 1: 좌, 2: 하, 3: 우
= [0,-1,0,1]
= [-1,0,1,0]
def dfs(x,y):
    if dp[y][x] == -1 : 
        dp[y][x] = 0
    if x<0 or x>n-1 or y<0 or y>m-1return 0
    for i in range(4):
        nx = x + a[i]
        ny = y + b[i]
        if (0 <= nx <= n-1 and 0 <= ny <= m-1and maps[ny][nx] > maps[y][x] :
            if dp[ny][nx] > 0:
                dp[y][x] += dp[ny][nx]
            # 방문한 적 없으면 dfs
            elif dp[ny][nx] == -1 :
                dp[y][x] += dfs(nx,ny)
    return dp[y][x]
        
if __name__ == '__main__':
    m,n = map(int,sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
 
    dp = [[-1* n for _ in range(m)]
    dp[0][0= 1
    dfs(n-1,m-1
    print(dp[-1][-1])
 
cs

Line 9 : 지도를 벗어나면 0을 반환한다.

Line 13 : 새로운 좌표가 지도를 벗어나지 않으며 이동가능하면, 새로운 좌표를 dfs하거나(Line 17, 과정 2-2) 현재 칸의 dp 값에 새로운 좌표의 dp값을 더해준다(Line 14, 과정 2-3).

 

문제 링크

 

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으�

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 11057 오르막 수 Python  (0) 2020.12.03
백준 4358 생태학  (0) 2020.10.21
백준 1152 단어의 개수  (0) 2020.08.31
백준 2884 알람 시계  (0) 2020.05.08
백준 9465 스티커  (0) 2020.04.18
반응형

10/19

1. 정부(감정원)의 통계 표본을 50% 늘리기로 했다.

- 아파트만을 대상으로 하는 주관조사 대상이 9천가구 밖에 안된다. KB의 통계는 3만 가구 이상을 대상으로 한다.

- 집값 통계를 주간으로 하는 나라는 우리나라밖에 없다.

- 부동산 통계는 항상 논란이 된다. 종류가 많고, 모든 정보를 담을 수 있는 통계는 없다.

 

2. 대한의사협회심의위원회, 성형 앱 광고에 대한 심의 강화 요청 : 심의대상이 현재 하루 이용자가 10만명 이상인데, 5만명으로 내려달라는 요청이 있다. 현재 심의 대상에 들어가는 앱은 없다.

 

3. 전세난

- 임차인이 집을 구할 수가 없다.

- 왜 갑자기 전세가가 오르나? : 인구감소보다 가구증가가 더 크다. 세입자가 눌러앉는다. 재건축 요건 강화에 따라 실거주를 하게 된다.

- 임대사업자 등록자가 100만명이 넘는다. 이 사람들은 법규상 집을 팔수가 없다.

- 서울의 경우, 재건축 완공보다 철거량이 더 많다. 이로인한 추가 수요가 공급량보다 많다. 거기에 임대차 3법와 세법 개편까지 더해져 전세가 상승이 더욱 심해졌다.

- 해결책 : 전세 수요를 매매 수요로 돌려야 한다.

 

10/20

1. 현대차 사업설명회 : 3조원 규모의 영업이익을 사내 충당금으로 3분기에 쌓기로 했다.

- 독자 개발한 세타2 엔진에 2015년부터 문제가 나타나기 시작했고, 리콜을 하고 있다. 충당금을 이 엔진 교체 비용으로 사용하고 있다.

- 국내의 모든 세타2 엔진에 대한 평생 보장을 약속함에 따라 더 많은 액수가 필요해졌다.

- 시점에 관한 논란 : 사측은 선제적 대응이라는 입장으로, 시장의 과도한 기대가 부담스럽다. 한 분기에 너무 많은 충당금을 과도하게 쌓는 것이 아니냐는 논란과 정의선 회장 취임 관련 빅 배스가 아니냐는 논란이 있다.

 

2. 중고차 시장 : 쏘카도 중고차 시장에 진출했다.

- 쏘카 입장에서는 어차피 팔아야할 차이니 자신들의 플랫폼에서 팔면 이득이 된다.

 

3. 주식 환불 : 90% 환불은 가끔 일어난다.

- 특혜 상장사의 경우, 상장 3~6개월 후에도 최초 공모가를 못넘으면, 공모주 청약 주관 증권사가 공모가이 90% 가격에 사들여야하는 제도가 있다.

- 이러한 특수한 경우가 아니면 100% 환불은 없다.

 

4. 전세난 : 공급 부족에 따라 전세 공급자 우위시장이 형성되었다.

- 전세 가격 : 전세 수요와 공급의 속도 차이에 따라 발생한다. 저금리 기조로 반전세로 돌리거나 전세보증금을 올리는 것을 선호한다. 전월세상한제로 전세금을 올릴 수가 없어 반전세나 월세로 돌린다.

- 전국적으로는 전세가격이 상승폭이 확대되고 있다. 수도권의 상승폭이 훨씬 크다.

- 내년에는 26만여 호의 아파트 입주 물량이 예정되어, 올해보다 적다. 2017년에 부동산 가격이 낮아 준공을 시작한 물량이 적다.

- 전세는 경제학적 측면에서 임대보다는 매매에 가깝다. 월세로의 자연스러운 전환을 유도하는 정책이 필요하다.

 

10/23

1. CJ 대한통운, 택배 분류 인력 충원 방안 발표 : 아르바이트, 협력 업체 등을 활용할 것으로 예상된다.

- 분류 작업 : 물류 터미널에서 택배를 해당 지역으로 분류하는 작업이다.

- 택배 배송 과정 : 지역 터미널 하차 ->  택배 기사가 배송 동선에 맡게 트럭에 싣는다.(이 과정이 6시간 정도 되는데, 이 과정을 다른 사람이 해줄 예정이다.)

- CJ 대한통운이 전국 택배 기사의 1/3을 보유하고 있다.

- 특수 고용직으로 산재 보험을 대리점과 택배 기사가 반반씩 내야하므로, 여러가지 이유로 산재 보험을 안드는 경우가 있다. CJ 대한통운은 택배 기사 모두가 산재를 들도록 권유할 예정이다.

 

2. 구리 값이 2년만에 최고치이다. : 구리 값은 경기 선행지수로 활용되기도 한다.

- 올해 초 저점 대비 48% 상승했다.

- 중국 경제 정상화의 영향이 크다.

 

3. 뉴욕시에서는 코로나세 10%를 부과한다. 해당 수수료는 식당 주인이 가져간다.

 

4. 대출 옵션

- 원금 균등 분할 상환 : 원금을 처음부터 끝까지 일정량씩 갚는다.

- 원리금 균등 분할 상환 : 더 오래 길게 갚는 방식이다. 원금을 처음에는 조금씩 갚다가 갚는 금액을 점점 늘려나간다.

- 대출받은 사람은 이자가 싼 대출이면 원리금 균등 분할 상환이 유리하다.

 

5. 금융시장 주요 이슈

- 원화 강세 : 대선 관련 달러 약세(민주당의 우세로 돈이 많이 풀릴 것이라는 기대), 중국 경기 활황(위완화 가치가 높아지는데, 원화는 위완화와 강하게 상관되어있다. 서로 수출입 양이 많아서 그렇다. 미국 민주당이 집권하면 미중관계가 좋아질 것이라는 기대), 국내 요인이 원인이다. 

- 원화 강세 시, 내수주가 좋다. 수출 기업은 부진할 수 있다. 외화를 조달하는 은행주는 강세를 보일 수 있다.

- 한국주가 중국주의 대체제 역할을 많이 했는데, 최근 중국이 금융시장을 개방하면서 그러한 수요가 많이 줄었다.

- KB 금융지주의 3분기 실적이 1조가 넘으며 매우 우수했다. 예상과 달리 연체율이 점점 낮아지고 있고, 안전한 대출만 해준다는 비판도 있다.

 

10/26

1. 이건희 회장 별세 : 삼성전자의 87년 취임 당시의 시총 4천억원에서 2014년 5월 당시 시총 196조이었다. 수정 주가 기준 100배가 올랐다.

- 이건희 회장의 보유 주식 주가가 18조가 넘는다. 여러가지를 고려하면 상속세가 약 60%로 10조원 이상 내야한다.

- 자식 간의 갈등은 일어나지 않을 전망이다.

- 삼성전자의 최대주주가 삼성물산이며 이재용 부회장이 삼성물산을 통해 삼성전자를 지배하고 있다. 삼성생명법이 어떻게 될지가 중요하다.

 

2. 전세난을 어떻게든 진정시키겠다는 발표 : 시장에 계속 개입할 것을 밝혔다.

- 중장기적으로는 임대주택의 공급을 늘릴 예정이다.

 

3. 세대주만 주택청약 가능

- 세대주 : 가족의 대표자 같은 개념이다.

- 한 집당 한명에게만 청약 기회를 준다는 개념이다.

 

4. 배터리 산업 관련 이슈

- 배터리 관련 화재사고 : 국토부 조사 결과로는 배터리 셀 분리막이 원인이나, 분리막은 결과라는 이견이 많다.

- LG 화학의 입장은 배터리를 차량에 장착하는 과정에서 문제가 발생한 것이 아니냐는 주장을 하고 있다. 배터리는 90% 정도만 사용해야하는데, 97% 정도를 사용하다 화재가 발생했다.

- 화재가 발생한 코다 차량은 LG 화학의 배터리만 사용한다. 기아차의 전기차에도 LG 화학의 배터리가 들어가는데 화재가 발생하지 않았다.

- LG 화학과 SK 이노베이션의 배터리 기술 소송이 거의 끝나간다. 

- 배터리 업계에겐는 테슬라 등 자동차 회사의 배터리 내장화가 가장 큰 리스크이다.

 

10/29

1. 국민은행 부자보고서 : 금융자산 10억 이상이 부자의 기준으로 약 35만명이다. 1년 전보다 10% 늘었다.

- 금융자산이 300억 넘는 인원이 6400명이로, 이들의 보유 자산이 우리나라 총 자산의 24%를 가지고 있다.

- 부자들의 자산 구성은 부동산 56%, 금융자산이 34% 정도이다. 10년 전에는 우리나라도 유럽처럼 부동산 자산의 비중이 줄 것이라 예상했지만, 전혀 그렇지 않다.

- 돈 번 이유로는 사업이 30%, 부동산 투자가 29%이다.

- 상속 및 증여가 크게 늘었다. 부자 중의 부자는 더욱 많다.

 

2. 롯데슈퍼에 22억의 과징금을 부과했다.

- 납품업체에게 성수기에 물량을 많이 받아놓고 안팔리면 반품시켜버렸다.

- 물품 납품 계약서를 안쓴 경우가 많았다. 또는 물품 거래 200일 후에 계약서는 주는 경우도 많았다.

- 판촉 행사비 약 108억을 납품업체에 떠넘겼다.

 

3. 삼성물산의 탈석탄 선언 : 국내 기업 중 최초로, 탈석탄 기업이 다른 기업으로도 퍼져나갈 전망이다.

- 석탄 관련 투자를 많이 하는 기관이 산은과 수출입은행 같은 국책 기관인데 어떻게 될 지 주목된다.

 

4. 연말정산

- 연금저축의 세액공제 한도가 50대 이상에게 늘어난다. 연봉 5500, 소득세 4000만원 이하인 경우 15% 공제된다. 이 구간을 초과하면 12%가 공제되다. 50대 이상이면서 연봉 1억2천 이하 구간에서 연금저축은 600만원과 IRP은 합쳐서 900만원까지 공제된다.

- 세액 공제는 똑같지만, 연금저축은 금액의 일부만 깰 수 있다. IRP는 무조건 전체를 다 깨야한다.

- 작년과 큰 변화 없다.

- 자영업자의 경우에는 노란우산 공제를 고려할만 하다. 사업 소득이 4천만원이 넘는 경우에는 노란우산 공제가 세액공제보다 혜택이 많다.

- 안경, 렌즈는 의료비공제로 연간 50만원까지 적용된다. 시력교정용이라는 별도의 인증서를 받아야한다. 휠체어, 교복 등도 비슷한 사례이다. 시력교정용인지 알 수가 없으므로 홈텍스로 안된다.

- 내년 입학하는 대학생의 등록금을 올해 미리 내더라도 내년에 공제된다. 학자금 대출을 받은 경우에는 올해 받는다.

 

10/30

1. 2019년 직장인의 평균 대출액이 1인당 4250만원이다. : 2019년 부채 증가율이 소득 증가율을 돌파했다.

- 저금리 기조와 대출 수요가 컸다. 부동산 매매 과열과 동학 개미 운동의 영향도 있다.

- 29세 이하 직장인의 증가폭이 가장 컸다. 주택 외 담보대출이 85%로, 학자금 대출, 전세자금 대출 등이 있다. 영끌 추세가 이미 작년부터 시작되었다는 해석이 있다.

 

2. 중국, 경제개발계획으로 쌍순환 계획을 발표했다.

- 초점은 국내 대순환에 맞춰있다. 내수 진작과 기술 자립이 포인트이다.

- 87년 경제 개방 후, 처음으로 내수로 방향을 돌렸다.

- 미중 무역 갈등으로 수출 위주 경제에 문제가 생겼다.

- 기술 자립에 사활을 걸었는데, 우리나라에도 큰 영향이 있을 것이다.

 

3. 미국에서 조립식 주택의 인기 : 주택 구매 능력에 한계를 느낀 미국인들이 제조 주택에 관심을 돌리고있다.

- 일반 단독 주택의 원가와 비교했을 때, 최소 40% 이상 재조 원가가 낮다.

 

4. 이중 국적자의 상속세 : 세법상 한국인인지 아닌지 따진다(1년에 절반 이상을 한국에서 살았으면, 세법 상 한국인이다.).

- 세법 상 한국인이 아닌 경우에는 다른 나라에 상속세를 낸다. 단, 국내 자산이 2억원 이상인 경우에는 2억 이상 분에 대해서는 우리나라에 상속세를 내야한다.

 

5. 금융시장이슈

- 네이버와 CJ의 지분교환 : 네이버는 이커머스와 컨텐츠 제작에 뛰어들기 위함이다. CJ 입장에서는 안정적인 고객사를 얻었다.

- 국민연금이 LG화학의 물적분할에 반대하기로 했다. : 지분가치희석과 주주가치훼손을 이유로 반대했다. 주총 참석자의 2/3가 찬성해야하며, 외국인의 표가 중요하다.

- 다음주 미 대선 : 트럼프 지지율이 상승하기 시작했다.

반응형
반응형

문제 풀이

1. 달팽이는 아래방향, 오른쪽 방향, 대각선(왼쪽 위) 방향 이 세가지를 번갈아 움직입니다.

  - 따라서 방향을 바꿀 때마다 check 변수에 1씩 더해주며, check mod 3이 방향이 됩니다.

2. 편의상 정사각형에서 움직인다고 생각하고 풀었습니다.

3. 아래로 움직일 때의 경우의 수를 생각해보면 다음과 같습니다.

  3-1) 끝까지 왔거나, 아래 방향의 칸이 0이 아닌 경우 : 방향을 오른쪽으로 바꾼 후, 오른쪽으로 한칸 움직인 후, 해당 칸을 현재 값으로 바꿔줍니다..

  3-2) 아래 방향의 칸의 값이 0인 경우 : 아래로 이동 후, 아래 칸의 값을 현재 값으로 바꿔줍니다.

4. 3의 과정을 오른쪽 방향, 대각선 방향에 대해서도 구현해 줍니다.

5. 밑변의 길이가 n일 때, 총 칸의 수 tot(n)은 다음의 재귀식으로 나타낼 수 있습니다.

  tot(n) = tot(n-1) + 1 , tot(1) = 1

  예를 들어, n=2일 때의 칸의 수는 tot(1) + 2 = 3이고, n=3일 때의 칸의 수는 tot(3) = tot(2) + 3 = 6입니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def solution(n):
    direction = ['down','right','diagonal']
    check = 0
    answer = []
    square = [[0 for i in range(n)] for j in range(n)]
    i,j = 0,0
    square[j][i] = 1
    tot = sum(i for i in range(1,n+1))
    for s in range(2,tot+1):
        d = direction[check%3]
        if d == 'down':
            if j+1==or square[j+1][i] != 0:
                check += 1
                square[j][i+1= s
                i += 1
            else:
                square[j+1][i] = s
                j += 1
        elif d == 'right':
            if i+1 == n or square[j][i+1!= 0 :
                check += 1
                square[j-1][i-1= s
                j-=1
                i-=1
            else :
                square[j][i+1= s
                i += 1
        else :
            if square[j-1][i-1!= 0:
                check +=1
                square[j+1][i] = s
                j += 1
            else :
                square[j-1][i-1= s
                j -= 1
                i -= 1
    for i,v in enumerate(square):
        answer += v[:i+1]
    return answer
 
 
cs

 

Line 8 : 과정 5의 재귀식을 표현한 값입니다.

Line 37 : 사각형에서 필요한 부분만 잘라 answer에 붙여줍니다.

문제 링크

 

코딩테스트 연습 - 삼각 달팽이

5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

programmers.co.kr

 

반응형
반응형

2019 카카오 개발자 겨울 인턴십 문제

문제풀이

1. move의 앞에서부터 요소 m을 한개 씩 뽑습니다.

2. board에서 (m-1)열에 인형이 있는지 확인하고, 있다면 가장 높이 있는 인형의 높이를 찾습니다.

3. board에서 인형을 뽑았다면 뽑은 위치의 값을 0으로 수정합니다.

4. 인형을 넣을 스택을 선언합니다.

5. 과정 2에서 뽑은 인형을 스택의 탑과 비교한 후, 같으면 둘다 없애고 다르다면 둘다 넣어줍니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from collections import deque
 
def solution(board, moves):
    answer = 0
    q = deque()
    board.insert(0, [0 for i in board[0]])
    for m in moves:
        m -= 1
        y = get_top(board, m)
        # 들어 있으면
        if y:
            doll = board[y][m]
            board[y][m] = 0
            if q:
                tmp = q.pop()
                if doll == tmp:
                    answer += 2
                    continue
                else:
                    q.append(tmp)
                    q.append(doll)
            else:
                q.append(doll)
    return answer
# 들어 있으면, 인형의 높이를 반환
def get_top(board, idx):
    for i, v in enumerate(board):
        if v[idx] != 0:
            return i
    return 0
            
cs

Line 5 : 뽑은 인형을 넣어줄 스택으로, deque 자료구조를 사용했습니다.

Line 8 : moves의 경우 맨 앞이 0이 아닌 1이므로, 편의상 -1을 해줍니다.

Line 26 : 해당 열에 인형이 있다면 가장 높은 인형의 위치를 반환해줍니다.

Line 6 : 인형이 맨 위에 있을 경우, get_top 함수가 0을 반환하여 안들어있다고 인식하는 문제를 개선하기 위해 맨 위에 모든 요소가 0인 리스트를 넣어줬습니다. get_top 함수가 True, False를 같이 반환하도록 한다면 이 과정이 생략될 수 있습니다.

Line 11 : 해당 열에 인형이 들어있는 경우입니다.

Line 14 : 인형을 넣는 스택에 인형이 들어있는 경우입니다.

Line 16 : 스택의 탑과 인형이 같은 경우 입니다. 탑을 다시 넣어주지 않고 넘어갑니다.

Line 19 : 스택의 탑과 인형이 다른 경우, 둘다 다시 넣어줍니다. 탑을 먼저 넣어주어야합니다.

Line 22 : 스택이 비어있는 경우, 인형을 넣어줍니다.

문제 링크

 

코딩테스트 연습 - 크레인 인형뽑기 게임

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

programmers.co.kr

 

반응형
반응형

문제 풀이

1. 이중 포문을 활용해서 모든 가능한 쌍의 합을 answer에 넣어줍니다.

2. set 자료구조를 활용해서 answer에서 중복값을 없애줍니다.

3. 다시 list로 변환 후, 정렬하여 반환합니다.

 

Python Code

1
2
3
4
5
6
def solution(numbers):
    answer = []
    for i,v in enumerate(numbers):
        for j,w in enumerate(numbers[i+1:]):
            answer.append(w+v)
    return sorted(list(set(answer)))
cs

문제 링크

 

코딩테스트 연습 - 두 개 뽑아서 더하기

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한�

programmers.co.kr

 

반응형
반응형

Bayes' theorem

 Conditional probability를 활용하여 $P(A\cap B)$ 를 쓰면 다음과 같다.

$P(A\cap B) = P(A \vert B)P(B) = P(B \vert A)P(A)$

위 수식의 의미는, 사건 A와 사건 B가 함께 일어날 확률은 사건 A가 일어나고 사건 B가 일어나거나, 사건 B가 일어나고 사건 A가 일어날 확률로 쓸 수 있다는 것이다.

 위의 수식을 이용하면 $P(A \vert B)$를 다음과 같이 쓸 수 있다.

$P(A \vert B) = \frac{P(B \vert A)P(A)}{P(B)}$

이 수식을 베이즈 정리라 한다.

 

용어 정리

위 수식을 활용하기 위해 A를 가설, B를 데이터라 하면,

$P(hypothesis \vert data) = \frac{P(data \vert hypothesis)P(hypothesis)}{P(data)}$

라 쓸 수 있다.

$P(hypothesis \vert data)$ : posterior probability(사후확률)라 하며, 주어진 데이터 하에 가설이 참일 확률을 의미한다.

$P(data \vert hypothesis)$ : 가설 하의 데이터의 likelihood이다.

$P(data)$ : marginal probability

$P(hypothesis)$ : Prior probability(사전확률)로 가설에 대한 초기 믿음을 나타낸다.

 

Naive Bayes' Classifier

 입력 feature $\vec{x}$를 통해 class $y$를 유추하는 모델을 생각해보면 베이즈 정리에 의해 다음과 같이 쓸 수 있다.

$P(y_j \vert \vec{x}) = \frac{P(\vec{x} \vert y_j)P(y_j)}{P(y_j}$

우항의 분모를 다시 쓰면,

$P(\vec{x} \vert y_j)P(y_j) = P(x_1 \vert x_1, \dots, x_n, y_j)$

이며, $x_i$가 서로 독립이라는 가정을 하면(강력한 가정이며 이 때문에 Naive Bayes' classifier이다),

$P(\vec{x} \vert y_j)P(y_j) = P(x_1 \vert y_j)P(x_2 \vert y_j) \dots P(x_n \vert y_j)P(y_j) = \prod_k P(x_k \vert y_j)P(y_j)$

라 쓸 수 있다.

 이 때, 주어진 feature $\vec{x}$에 대한 예측 클래스 $\hat{y}$ 는 다음과 같다.

$\hat{y} = \underset{y_j}{argmax} \prod_k P(x_k \vert y_j)P(y_j)$

 

Laplace Smoothing

 위 모형의 문제는 샘플의 개수가 적을 때 $P(x_i \vert y_j) = 0$ 이 생기는 문제가 발생할 수 있다. 즉, 데이터 기반으로 likelihood를 계산하다보니 등장하지 않은 데이터에 대해서는 class $y_j$일 확률이 아예 없다고 하는 강력한 모형이 만들어지는 것이다. 이러한 강력한 모형은 바람직 하지 않으므로

$P(x_i \vert y_j) = \frac{\mbox{# number of }x_i + cP(x_i}{\mbox{# of } y_j + c}$

와 같이, 아주 작은 값을 분모와 분자에 더해줘 확률이 0이 되는 것을 피한다.

 

Application with Iris dataset

 붓꽃 분류 데이터를 활용하여 실습해 보겠습니다. 해당 데이터에서 feature는 4개로 ['sepal length', 'sepal width', 'petal length', 'petal width'] 이고, class는 [0,1,2] 세개로 주어집니다.

 주어진 데이터에 맞게 각 확률을 구해주면 됩니다. 또한, 계산의 편의성을 위해 모든 인풋값을 반올림하여 사용하였습니다. 연속값을 사용하는 경우에는 특정 구간의 데이터 개수를 세면 됩니다.

 Prior probability : 모든 클래스의 데이터가 각 50개씩 주어지므로 1/3으로 했습니다.

 Marginal probability : $[x_1, x_2, x_3, x_4]$ 의 개수를 센 후, 전체 개수로 나누어주면 각 인풋 데이터에 맞는 Marginal probability가 됩니다.

 Likelihood : $P(x_i \vert y)$ 의 개수를 세어 확률을 측정합니다.

 코드는 깃허브를 참조해주세요.

 Github link

 

SunggookCHOI/Laboratory

개인 학습의 기록. Contribute to SunggookCHOI/Laboratory development by creating an account on GitHub.

github.com

 학습과 테스트 데이터는 8:2로 나누었으며, 30개의 테스트셋에 대해 약 93%의 정확도를 보이는 것을 확인할 수 있습니다.

반응형

'ML > 이론' 카테고리의 다른 글

Least-Mean-Square Algorithm  (0) 2020.03.09
Maximum a posteriori estimation  (0) 2020.03.03
반응형

문제풀이

1. 키패드에서 숫자의 좌표를 정의합니다. 저는 1이 (0,0), #이 (3,2)로 했습니다.

2. numbers에서 주어진 수를 하나씩 꺼내며 숫자가 1,4,7이면 answer에 L을 더하고 왼손의 좌표를 누른 숫자의 좌표로 바꿔줍니다. 주어진 숫자가 3,6,9이면 answer에 R을 더하고 오른손의 좌표를 바꿔줍니다. 주어진 숫자가 가운데 줄에 있는 수인 경우 왼손으로부터의 거리와 오른손으로부터의 거리를 비교하여 짧은 손을 이용합니다. 거리는 각 손의 좌표와 숫자의 좌표의 x축 값끼리의 차의 절댓값과 y축 값끼리의 차의 절댓값을 더한 값이 됩니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
global dic
dic = {}
dic['0'= [3,1]
dic['*'= [3,0]
dic['#'= [3,2]
= 0
= 0
for n in range(1,10):
    dic[str(n)] = [i,j]
    j+=1
    if j==3:
        i+=1
        j=0
def solution(numbers, hand):
    global dic
    answer = ''
    l = [3,0]
    r = [3,2]
    for n in numbers:
        near = get_nearest_hand(n,l,r)
        if n in [1,4,7]:
            answer += 'L'
            l = dic[str(n)]
        elif n in [3,6,9]:
            answer += 'R'
            r = dic[str(n)]
        else:
            if near == 'l':
                answer += 'L'
                l = dic[str(n)]
            elif near == 'r':
                answer += 'R'
                r = dic[str(n)]
            else:
                if hand =='right':
                    answer +='R'
                    r = dic[str(n)]
                else:
                    answer += 'L'
                    l = dic[str(n)]
                
    return answer
 
def get_nearest_hand(num,l,r):
    global dic
    tmp = dic[str(num)]
    l_dist = abs(l[0- tmp[0]) + abs(l[1- tmp[1])
    r_dist = abs(r[0- tmp[0]) + abs(r[1- tmp[1])
    if l_dist > r_dist:
        return 'r'
    elif l_dist < r_dist:
        return 'l'
    else :
        return 's'
cs

Line 1 : dic은 키가 숫자이고 값이 좌표인 딕셔너리입니다.

Line 44 : 주어진 숫자가 2,5,8,0인 경우, 숫자로부터 더 가까운 거리의 손을 반환하는 함수입니다.

Line 34 : 양손으로부터 거리가 같은 경우, 오른손잡이인지 왼손잡이인지를 고려합니다.

 

문제 링크

programmers.co.kr/learn/courses/30/lessons/67256

 

코딩테스트 연습 - 키패드 누르기

[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL"

programmers.co.kr

 

반응형
반응형

10/5

1. 2030 신용대출 급증 : 5대 시중은행 마이너스 통장 금액의 2030의 비중이 40% 이다.

- 주식투자, 공모주 투자, 부동산 구매 등에 쓰였을 것으로 예상된다.

- 내집마련 수요 : 2030의 최우선 재무 목표는 주택 구입(61%) 였다. 결혼 자금마련은(29%) 였다.

- 미래의 자산축적이 어려울 것이라 전망하므로 조금이라도 빨리 집을 사려하고있다.

 

2. 대주주 양도소득세 과세 기준이 3억으로 낮아졌다.

- 대주주 기준이 가족 통합으로 10억에서 3억으로 낮아졌다.

- 대주주들이 이 기준을 피하기 위해 매도할 경우 주가가 급락할 수 있다.

- 관련 국민청원의 동의가 20만을 넘었고, 기재부도 검토할 것이라는 입장이다(3억원은 고수하되 가족합산은 방안을 마련하겠다는 입장).

 

3. 증권사의 대출 금리가 은행보다 비싸다 : 주식담보대출임에도 더 비쌌다.

- 금융위가 대안을 제시했다. 산정금리, 가산금리를 매월 보고받고, 감사하겠다고 발표했다. 여태까지는 증권사가 금리를 정하는 방식이 공개되지 않았다.

 

4. 비상장임에도 (주)가 회사이름 앞에 붙는 이유

- (주)는 상장 여부와 관계없이 주식회사는 반드시 회사이름의 앞 또는 뒤에 써야한다.

 

5. 트럼프 코로나 확진의 금융시장 영향

- 코로나 대응 정책이 활발히 진행되므로 대통령의 역할이 크다.

- 대선에도 영향이 있을 것이다.

- 민주당은 시장개입주의로 정권이 바뀔 경우, 기업/시장에도 변화가 예상된다.

- 추가 부양책 : 고용 지표 등이 시장의 기대치에 못 미치고 있다. 8월부터 논의되고 있는 경기 부양책이 지연되고 있다.

- 민주당은 돈을 더 쓰자, 공화당은 지출을 줄이자는 입장이다.

- 트럼프 뿐만아니라 상원의원 다수도 코로나 확진 판정을 받아 정책이 제대로 논의되고 있지 못하다.

10/7

1. 네이버 검색어 조작 : 쇼핑, 동영상 관련 검색시 자신들의 서비스 순위를 올려왔다.

- 쇼핑의 경우, 네이버 쇼핑에서 스마트스토어의 상품이 더 노출되도록 알고리즘을 조절했다.

- 네이버는 공정위의 결정에 불복하며 소송을 준비중이다.

- 네이버 측의 주장은 공정위의 거래 기간 동안 약 50번의 알고리즘 수정이 있었는데, 우연히 네이버에게 유리하게 작용했던 5건에 대해서만 공정위가 문제를 삼았다는 주장이다. 

 

2. 구글플레이 앱 매출 수수료 인상을 인도에서는 6개월 유예하기로 했다. 

- 인도의 IT 기업의 반발이 매우 심했다.

 

3.  유튜버 소득 공개 : 국세청이 유튜버에 대한 직업 코드를 만들었다.

- 국세청에 신고한 330명의 대형 유튜버의 매출이다.

- 수입의 40%가 유튜브 수입이고, 60%는 광고 수입이다.

 

4. 임대차 3법의 최근 논란 : 계약 갱신 청구권(2+2)

- 임차인이 나가기로 했다가 번복하는 경우 : 임대인은 거절할 수 없다. 매수인이 임대 계약을 승계하므로 매매도 주의해야한다. 세입자가 있는 집을 매수하는 경우, 세입자가 나가기로 했다고 해서 구매하더라도 세입자가 마음을 바꾸면 세입자가 우선이므로 주의해야한다.

- 세입자가 나가기로해서 새로운 세입자와 계약을 했는데, 기존의 세입자가 마음을 바꾼 경우 : 이러한 상황은 불가능하다.

- 집주인이 살겠다고 세입자를 내보내고 집을 매매하는 경우 : 매도의 경우에는 규정이 없다. 집주인의 의사가 세입자를 내보낸 경우에는 손해배상을 해야할 수 있다.

- 합의 갱신, 묵시적 갱신 등의 경우에는 계약갱신청구권이 사용되지 않는다. : 계약 갱신 과정에서 특약 사항 같은 곳에 계약갱신청구권을 사용하였다고 확실히 해놓아야 한다.

- 세입자의 경우에는 굳이 먼저 연락하지 않으므로써 묵시적 갱신을 노려볼 수 있다.

10/14

1. 현대차 부회장이 회장직에 오른다 : 정몽구 회장이 2018년부터 사실상 일선에서 물러나있었으므로 큰 변화는 없을 것이다.

- 이와 함께 고위 경영진도 변화해왔다.

- 정의선 부회장은 경영능력이 어느정도 검증되었다. 다만, 자동차 산업 자체가 급변기에 있다.

 

2. 한국산업연합포럼이라는 사실상의 새로운 재계 단체가 나타났다.

- 박근혜의 탄핵에 전경련이 연결되면서 재계 단체가 힘을 잃었다.

 

3. 추석 이후 신용대출을 대폭 줄였다. : 신한은행의 전문직 대상 신용대출 등

4. ETF 신탁 : ETF를 사달라고 돈을 맡기는 것을 ETF 신탁이라 한다.

- ETF에 투자하면서 직접 증권사 계좌를 만들고 할 필요가 없는 대신, 수수료(투자금의 약 1%)를 내야한다.

 

5. 식당 레시피 표절 논란

- 덮죽 관련 상표를 방송 후 다른 사람들도 출원했다.

- 피해업체도 상표출원을 했지만, 더 빨리 상표출원을 한 사람이 있다. : 상표법 상으로는 먼저 신청한 사람이 상표를 받지만, 안좋은 의도가 있는 경우 거절 당할 수 있다.

- 소상공인의 경우, 상표권에 대해 잘 모르고 당하는 경우가 있다.

- 식당 레시피도 저작권이 있나? : 레시피는 저작권 보호 대상이 아니다. 특허의 대상은 될 수 있다.

10/16

1. 집 매매 시, 매매하는 집에 세입자가 있으면 공인중개사가 직접 세입자에게 계약갱신청구권을 사용할 것인지 확인해야한다. : 임대차 3법의 대표적인 부작용이었는데, 국토부가 이번에 공식적으로 해결했다.

- 계약서에 계약갱신청구권 사용여부가 공식적으로 들어가게된다.

- 세입자의 변심이 불가능해진다.

[규제가 생긴 후, 오히려 복잡해진 것 같다는 시각도 있다.]

- 세입자 입장에서도 계약 만료 6개월 전까지는 결정 유예가 가능하므로 문제가 될 수 있다.

- 합의 연장과 계약갱신청구권 사용에 대한 임대인과 임차인 간의 마찰이 있을 수 있다.

 

2. 2년 뒤 우리나라 인구 5천만 이하로 내려갈 예정이다. : 내년부터 인구 감소가 시작된다.

- 우리나라가 OECD 가입국 중 유일하게 출산율이 0명대이다.

- 정부는 인구 감소에 따라, 각종 연금 적자 문제 등에 대한 해결의지를 내보였다.

- 외국인 거주자는 늘고 있다. : 내국인+외국인의 감소세는 9년 후에 시작된다.

- 2024년부터는 다인종 국가가 될 예정이다.(외국인 비율이 5% 이상)

 

3. 역외환율 : 역외(외국)에서 정해지는 우리나라 환율

- 외국인이 원화를 거래할 때, 외국인끼리 몇 달 후의 환율을 가지고 가상 거래를 한 후 정산할 때 적용되는 환율이다.

 

4. 금주의 경제동향

- 바이든의 당선 확률이 올라가면서, 미국채 10년 장기채 가격이 크게 올랐다. 민주당은 정부지출을 늘리고자 하므로, 부양책 실행의 기대로 시장금리가 오르고 있다.

- 금리 상승의 주식시장에 대한 영향 : 코로나로 성장주 주가가 크게 올랐는데(저금리로 주식시장에 몰린 돈), 성장주는 미래에 대한 기대감으로 가격이 결정되므로 금리가 상승하면 현재가격으로 할인할 때 기업가치가 크게 떨어진다. 반면, 금리 상승은 경기 회복을 의미하기도 한다.

- 한국의 국채 금리도 같이 오르고 있다.

- 공모주 청약에 돈이 몰려서 은행 예금이 계속 빠지고 있다.

- 정의선 부회장이 현대차 기업의 회장이 되었다. : 현대차 그룹의 순환출자의 고리를 끊어야하므로, 지배구조 개편을 노리고 있다.

반응형

+ Recent posts