반응형

문제 풀이

1. dictionary 자료구조를 활용하여 각 나무의 등장 횟수를 세어줍니다.

2. 이 때, defaultdict를 사용하면, 해당 나무가 이미 등장한 적이 있는지 검사하는 코드를 작성할 필요가 없습니다.

3. format 함수를 이용하여 각 나무의 점유율을 소수점 넷째 자리까지 출력합니다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
from collections import defaultdict
 
readline = sys.stdin.readline
 
def main():
    dic = defaultdict(int)
    tot = 0
    try:
        while 1:
            word = readline().rstrip()
            if not word:
                break
            dic[word] += 1
            tot += 1
    except EOFError:
        exit()
 
    for t in sorted(dic.keys()):
        print(t,format(dic[t]/tot*100,'.4f'))
if __name__=='__main__':
    main()
cs

 

 

문제링크

 

4358번: 생태학

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어

www.acmicpc.net

 

반응형

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

백준 20299 3대 측정  (0) 2020.12.04
백준 11057 오르막 수 Python  (0) 2020.12.03
백준 1520 내리막 길  (0) 2020.10.20
백준 1152 단어의 개수  (0) 2020.08.31
백준 2884 알람 시계  (0) 2020.05.08
반응형

문제 풀이

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

 

반응형

+ Recent posts