이전 포스팅에서 작성해 둔 get_clf_eval() 함수를 이용해서 사이킷런 래퍼 XGBoost로 만들어진 모델의 예측 성능 평가를 해 보겠습니다.
get_clf_eval(y_test, w_preds, w_pred_proba)
지표
이전
이후
Accuracy
약 0.96
약 0.97
Precision
약 0.97
약 0.97
Recall
약 0.97
약 0.98
F1-Score
약 0.97
약 0.98
ROC-AUC
약 0.99
약 0.99
이전 실습보다 평가 지표가 조금 상승했습니다. 이번 실습에서는 early stopping을 따로 설정하지 않은 관계로 train 데이터를 train과 valid 데이터로 나누는 과정을 생략하였고, 그래서 트레인 데이터셋의 수가 늘어난 영향이 있을 것으로 파악됩니다. (애초에 트레이닝 데이터가 풍부한 데이터셋은 아닌 관계로)
트리 기반의 앙상블 학습에서 가장 각광받고 있는 알고리즘 중 하나로, 캐글(kaggle) 등 경연 대회에서 입상한 많은 데이터 사이언티스트들이 XGboost를 사용하면서 널리 알려지게 되었습니다. 대체로 분류에 있어서 뛰어난 예측 성능을 보이는 특징을 가지고 있습니다.
XGboost는 GBM에 기반하고 있는데요. GBM보다 빠르게 학습이 가능하고 오버핏팅 규제 부재 문제 등을 해결한다는 장점이 있다고 합니다. 그 밖에도 Tree pruning이 가능하여 더 이상 긍정 이득이 없는 분할을 가지치기 해서 분할 수를 더 줄이는 추가적인 장점, 자체 내장된 교차 검증 기능, 결손값을 자체 처리할 수 있는 기능 등의 장점도 가지고 있습니다.
XGBoost API 학습을 위해 위스콘신 유방암 데이터로 실습을 진행해 본 결과를 정리하여 공유하고자 합니다 :-)
sklearn dataset 위스콘신 유방암 데이터 불러오기
sklearn의 자체 내장 데이터인 load_breast_cancer을 불러오겠습니다.
import pandas as pd
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
import warnings
warnings.filterwarnings('ignore')
dataset = load_breast_cancer()
features = dataset.data
labels = dataset.target
cancer_df = pd.DataFrame(data = features, columns = dataset.feature_names)
cancer_df.head(3)
cancer_df['target'] = labels
cancer_df.head(3)
데이터프레임 마지막에 target 컬럼을 추가하여 각 row의 label을 0 또는 1로 나타냈습니다.
문제 상황 : 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
1.
먼저 빠른 탈출을 위해 다음 4가지 경우에는 함수를 False로 얼리 리턴하도록 설정해주겠습니다.
주어진 문자열이 ")" 로 시작하는 경우
주어진 문자열이 "(" 로 끝나는 경우
주어진 문자열의 길이가 홀수인 경우
주어진 문자열이 ")" 또는 "(" 한 종류로만 이루어진 경우
def solution(s):
if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
return False
2.
다음으로 stack 리스트를 선언해주도록 하겠습니다.
stack = []
우리는 stack 리스트에 "(" 열기 괄호만 넣어줄 것입니다.
왜 열기 괄호만 넣어줄까요? 예시를 통해 한번 확인해 봅시다.
문자열 s = "(((())"가 있다고 합시다. 딱 봐도 열기 괄호는 4개인데 닫기 괄호는 2개여서 짝이 맞지 않는다는 것을 알 수 있습니다. 우리는 for루프를 통해 0번째 자릿값부터 차례대로 돌면서 해당 자리의 값이 "("이면 stack에 넣어주고, ")"이면 stack에 있는 열기괄호를 하나 빼 줄 것입니다.
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack:
return False
stack.pop()
s = "(((())"
첫 번째 자리 "(" -> stack = "("
두 번째 자리 "(" -> stack = "(", "("
세 번째 자리 "(" -> stack = "(", "(", "("
네 번째 자리 "(" -> stack = "(", "(", "(", "("
다섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop() -> stack = "(", "(", "("
여섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop() -> stack = "(", "("
if stack:
return False
else:
return True
이터레이션을 다 돌고 났을 때
stack이 비어 있으면 짝이 맞으므로 True
stack에 남은 값이 있다면 짝이 맞지 않는 것이므로 False를 리턴합니다.
결국 "("의 갯수와 ")"의 갯수가 동일한지 확인하는 것과 다름 없습니다. 다른 방법으로도 정확성 문제는 통과하는 데 어려움이 없으나, 효율성에 문제가 생기는 관계로 stack 알고리즘을 통해 효율성을 높여준 것이라고 보시면 되겠습니다.
3.
마지막으로 한 번에 코드를 보겠습니다.
def solution(s):
if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
return False
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack:
return False
stack.pop()
if stack:
return False
else:
return True
클릭하시면 태블로 퍼블릭 웹사이트에서 인터렉티브하게 직접 결과를 조절해 보실 수 있습니다.
<시각화 이후 생각해볼만한 것들>
1. 구별 화장실 수와 구별 면적의 관계는 어떻게 되는가? 2. 구별 화장실 수와 지하철 역의 개수의 상관관계가 있는가? 3. 구별 화장실 수와 구별 인구 수의 관계는 어떻게 되는가? 인구와 구별 화장실 총 수는 비례하는가? 4. 서울특별시 구별 장애인 화장실 데이터를 따로 구할 수 있는가? 구할 수 있다면, 전체 화장실과 장애인 화장실의 비율을 비교해 보자. 5. 상업 단지와 화장실 수의 상관관계가 있는가?
6. 관광 구역과 화장실 수의 상관관계가 있는가?
7. 공공화장실 중에서 지하철 역 화장실의 개수를 특정할 수 있는가? 있다면 그 비율은 어떻게 되는가?
8. 지하철 역 화장실 개수를 구할 수 있다면, 지하철 노선별 유동인구 데이터와 병합하여 화장실의 갯수가 적절하게 비치되어 있는지 비교해보자.
여기까지입니다 :-) 좀더 생각해볼 수 있을것 같지만 본격적인 개인 EDA 프로젝트 준비를 위해서 이번엔 이정도로 간단히만 포스팅을 마치려고 합니다. 쉽고 짧은 작업이었지만 맘에드는 공공데이터를 구하고, 정제하고, 시각화 후 생각해볼거리 도출까지 은근 시간이 걸렸네요. 다음엔 더 능숙하고 멋진 프로젝트를 가져와서 공유해보겠습니다. 감사합니다. :)
(+) 판다스 데이터프레임 CSV파일로 내보내기 한 후 태블로에 불러온 과정
t.to_csv("toilet_df.csv")
먼저 to_csv() 메소드를 통해 간단하게 csv파일로 내보내기를 해주었습니다. 저는 구글 코랩에서 실습을 진행했습니다.
구글 코랩의 왼쪽 파일메뉴에서 간단하게 바로 다운로드를 해서 다운로드 폴더에 넣어 주었는데요. 로컬 환경에 따로 다운로드하지않고 태블로 퍼블릭 환경에서 구글 드라이브를 연동해서 바로 오픈해도 됩니다.
태블로 퍼블릭 프로그램을 실행하고 로컬 환경에 다운로드한 toilet_df.csv 파일을 오픈했습니다.
따로 사용하지 않을 예정인 산지, 부지번 컬럼은 숨기기(Hide) 해주었습니다. 이후 시트 2개에서 작업을 하고 대시보드 1개에서 두개를 합쳐주는 방식으로 간단히 끝을 내주었습니다.
서울시 공중화장실 공공데이터를 가지고 아주 간단한 데이터 시각화, 분석 실습을 해 보려고 합니다. 먼저 이번 포스팅에는 파이썬 pandas 라이브러리를 이용해서 데이터 전처리 작업한 것을 간단히 정리해 보았습니다. 데이터 시각화, 분석은 태블로 프로그램을 이용하여 마친 뒤 다음 포스팅에 이어서 올리도록 하겠습니다.
파이썬 requests, BeautifulSoup 라이브러리를 이용한 웹크롤링 후 데이터분석 실습을 해보았습니다 :-)
연금복권720+은 제가 한달에 2-3회정도 꾸준하게 구매하는 최애 복권인데요. 슬프게도 지금까지 제대로 당첨된 적은 단 한번도 없지만, 앞으로도 저는 꾸준히 구매를 할 예정인 아주아주 매력적인 복권입니다. 1등에 당첨이 되면 (세전) 700만원을 매월 20년동안 수령할 수 있어요. 동행복권 온라인 사이트에서 간단히 온라인 구매를 할 수도 있구요. 1등 번호는 온라인 1명, 오프라인 1명 총 2명이 당첨될 수 있습니다. 자세한 복권 구조는 동행복권 홈페이지를 참고해 보시구요.
복권의 경우 통계를 공부해보신 분들께는 아주 친숙한 소재이실텐데요. (저는 아닙니다.ㅋㅋㅋ) 동행복권 사이트에서는 복권 당첨번호를 엑셀파일로도 제공하고 통계 자료를 따로 분석해서 메뉴도로 제공하고 있습니다. 다만 저는 철저히 requests 라이브러리를 이용한 웹크롤링에 익숙해지기 위해서 엑셀 파일이나 통계자료를 건드리지 않고 처음부터 끝까지 혼자 힘으로 본 실습을 했습니다!
[참고] 본 포스팅은 수리링 본인의 공부 기록을 목적으로 작성하였습니다. 해당 라이브러리에 대해 전혀 모르시는 분께서 보면서 따라하시기엔 많이 불친절하게 느껴질 수 있습니다. 참고하시고 봐 주시면 감사드리겠습니다 :-)
[참고] 본 포스팅은 책, 강의, 다른 사람의 포스팅을 참고하지 않은 스스로의 창작물입니다! 참고하여 포스팅 하시는 경우 출처 밝혀주심 감사드리겠습니다!
[실습 목차]
206회차로 모의 실습
원하는 회차 구간을 입력하면 모든 정보를 담아 데이터프레임으로 리턴하는 함수 작성
데이터프레임으로 간단한 데이터분석 (은근 재밌으니 귀찮으시면 이것만 보고 가세요...^^)
그런데 기본 URL에 회차 정보가 드러나지 않고 숨어 있어요. 206회를 조회해도, 200회를 조회해도 계속 같은 URL이 유지됩니다. 따라서 회차를 특정하여 정보를 뽑아낼 수가 없는 상황입니다. 우리는 회차를 조회할 수 있는 상세URL을 알아내야 해요.
문제상황을 해결하기 위해 크롬 웹브라우저의 inspection(개발자 도구) 메뉴의 Network 탭을 확인해 봅시다.
위와 같이 네트워크 탭을 켜둔 상태로 조회 버튼을 눌러봅니다. Name 탭의 맨 첫 번째 gameResult 어쩌구를 클릭한 다음 Payload를 확인합니다. (누가 봐도 수상한) Round: 206 이라는 정보를 확인했습니다. 기존 url 뒤에 &Round=206을 붙여 주면 될 것 같다는 합리적 의심을 해봅니다.
주소 뒤에 &Round=205 를 붙여넣고 엔터를 치니 205회 당첨결과 페이지로 잘 이동합니다 ㅎㅎ 찾았다 요놈! 이제 상세 url주소를 찾았으니 코드를 작성하면서 원하는 데이터를 뽑아내 보겠습니다.
1-2. requests, BeautifulSoup 라이브러리
* 본 실습에서 해당 라이브러리에 대한 상세 설명은 생략합니다
import requests
from bs4 import BeautifulSoup as BS
먼저 requests와 BeautifulSoup 라이브러리를 임포트해줍니다.
url = "https://dhlottery.co.kr/gameResult.do?method=win720&Round=206"
res = requests.get(url)
soup = BS(res.text, "html.parser")
우리가 찾아낸 url을 선언해 준 다음 차례대로 라이브러리에 넣어서 html 자료를 뽑아냅니다.
soup을 실행해 보니 html 정보가 잘 들어왔습니다 :) 저는 html 코드를 하나하나 뜯어보면서 원하는 정보를 뽑아내 봤어요.
206회차를 가지고 적당히 연습을 해 봤으니, 원하는 회차를 입력하면 하나씩 모두 조회해서 딕셔너리로 담아 리턴하는 함수를 작성해 보았습니다.
def win720(round):
# 입력받은 회차 번호로 url을 만들고 정보를 받아냅니다.
url = f"https://dhlottery.co.kr/gameResult.do?method=win720&Round={round}"
res = requests.get(url)
soup = BS(res.text, "html.parser")
rows = soup.find("tbody").find_all("tr")
# data_dict에 앞으로 하나씩 정보를 추가할 겁니다. 먼저 라운드 값을 첫 번째로 넣어줬습니다.
data_dict = {"round":round}
nums = rows[0].find_all("span", {"class":"num"})
# 1등 조, 당첨번호
group = int(nums[0].find("span").text)
n_1 = int(nums[1].find("span").text)
n_2 = int(nums[2].find("span").text)
n_3 = int(nums[3].find("span").text)
n_4 = int(nums[4].find("span").text)
n_5 = int(nums[5].find("span").text)
n_6 = int(nums[6].find("span").text)
data_dict["group"] = group
data_dict["n_1"] = n_1
data_dict["n_2"] = n_2
data_dict["n_3"] = n_3
data_dict["n_4"] = n_4
data_dict["n_5"] = n_5
data_dict["n_6"] = n_6
# 1-7등 당첨자수
for i in range(7):
rank_counts = rows[i].find_all("td", {"class":"ta_right"})[-1].text.strip()
rank_counts = re.sub(",","", rank_counts)
rank_counts = int(rank_counts)
column_name = f"rank{i+1}"
data_dict[column_name] = rank_counts
# 보너스 당첨번호 6개
for i in range(6):
bonus_num = rows[7].find_all("span", {"class" : "num"})[i].find("span").text
column_name = f"bonus_{int(i)+1}"
data_dict[column_name] = bonus_num
# 보너스 당첨자수
bonus_counts = int(rows[7].find_all("td", {"class":"ta_right"})[-1].text.strip())
data_dict["bonus"] = bonus_counts
return data_dict
더럽게 길지만 그래도 잘 작동했습다^_^;;;; 너무 길어져서 쓰면서 불길했는데 그래도 오류 수정 2-3번만에 원하는 대로 값이 나와서 다행이였어요
205회차로 테스트를 해 봤는데요. 조, 1등 넘버 6자리, 등수별 당첨매수, 보너스 번호 6자리, 보너스 당첨매수가 딕셔너리로 제대로 들어온 것을 확인했습니다 :) 이게 뭐라고 너무 재밌었어요 (ㅋㅋㅋㅋ)
2-2. 회차 구간을 설정하고 데이터프레임을 리턴하는 함수 작성하기
위에서 작성한 win720()함수를 가지고 원하는 회차 구간의 모든 정보를 담은 데이터프레임을 반환하는 함수를 작성해 주었습니다.
def lucky_chart(start, end):
lucky_results = []
for i in range(start, end+1):
win = win720(i)
values = list(win.values())
print(values)
print(len(values))
lucky_results.append(values)
columns = list(win.keys())
print(columns)
print(len(columns))
import pandas as pd
df = pd.DataFrame(lucky_results, columns = columns)
return df.set_index("round")
중간 중간에 있는 print 함수들은 제가 함수를 작성하면서 중간 과정을 시각화하기 위해 굳이 넣어줬구요, 깔끔하게 없애줘도 됩니다.
history = lucky_chart(190, 206)
190회부터 206회차까지 럭키차트 함수를 돌려보았습니다.
요런식으로 진행상황을 시각화 하기 위해 print 함수를 넣어줬습니다. (중간에 오류가 있었어서 저런식으로 시각화 하면서 수정해줬어요!)
history
알흠다운 판다스 데이터프레임이 완성되었어요 ❤️
3. 간단 데이터분석
마지막으로 데이터분석은 1회차부터 206회차까지로 구간을 늘려서 진행했습니다! (1등은 제껍니다.)
1등 조 비율이 어떻게 될까?
# 조별 value_counts() 구하기
group_counts = history['group'].value_counts()
# matplotlib 임포트
import matplotlib.pyplot as plt
# 차트 작성
plt.pie(group_counts,
labels = group_counts.index,
shadow = True,
autopct = '%1.2f%%')
plt.title("Rank 1 groups ratio")
plt.legend()
plt.show()
아주.. 흥미로운.. 결과입니댜... 연금복권720+ 1회차부터 206회차까지 모든 데이터들을 살펴본 결과... 지금까지 가장 많은 1등을 배출한 조는 4조였습니다. 4조 > 1조 > 3조 > 5조 > 2조 순이네요.
연금복권을 아는 분들께서는 이해를 하실텐데, 저는 혹시라도 번호 6개를 다 맞췄지만 조가 다를 때 2등이라도 당첨되도록 + 혹시라도 1등이 되면 2등도 동시 당첨되도록(ㅋㅋㅋ) 번호 6개를 고르고 나면 모든 조(1~5조)로 총 5줄(5,000원)을 구매해버립니다. 솔직히 이게 더 확률이 낮을 것 같기는 한데.......... 만약 특정 조를 골라서 구매해야 한다면 앞으로 저는 1조 또는 4조를 고르겠습니댜.
지금까지 역대 2등은 몇명이 나왔을까?
import seaborn as sns
sns.set_style("darkgrid")
sns.set_palette("bright")
sns.barplot(history["rank2"].value_counts())
history['rank2'].agg(['min', 'max', 'mean'])
# min 0.0
# max 8.0
# mean 4.5
1등에 가려 2등의 당첨자 수는 사실 잘 확인해 본 적이 없는데요. 2등에 당첨되면 매달 100만원씩 10년간 수령할 수 있거든요. 2등이라도 당첨시켜 주신면 제가 굉장히 감사할텐데요. 몇 명이나 당첨되나 보니, 역대 2등 당첨자 수는 최대 8명, 최소 0명(ㅋㅋㅋㅋㅋㅋ), 평균 4.5명이 나왔다고 합니다. 그래프로 확인해 보니 2등이 한 명도 나오지 않은 회차가 20번이 넘네요? 실화냐?
오랜만에 피보나치 수열 문제 풀이를 했습니다. 처음에 간단한 재귀함수를 적용해서 풀이를 했더니 테스트는 모두 통과하는데 효율성 테스트에서 시간 초과로 계속 실패를 하는 문제가 발생했습니다. 그래서 효율성을 올리기 위해 메모화를 적용해서 풀이를 했더니 효율성 테스트도 모두 통과할 수가 있었습니다 :-)
간단하게 풀이방법을 설명해 보겠습니다!
1. 메모화 없이 기본 피보나치 수열 함수 작성하기
def basic_fibonacci(n):
if n in [1, 2]:
return 1
if n == 3:
return 2
return basic_fibonacci(n-2) + basic_fibonacci(n-1)
만약 주어진 정수가 1 또는 2라면 바로 1을 리턴,
주어진 정수가 3이라면 바로 2를 리턴하도록 초기 설정을 해 줍니다.
4 이상의 정수 n이 주어졌을 때 재귀함수 형식으로 n-2와 n-1에 basic_fibonacci 함수를 적용한 값을 구해 더한 값을 리턴합니다.
위 함수는 제대로 작동하지만, n의 값이 커질수록 효율성이 급격하게 떨어진다는 단점이 있어요. 메모화를 이용해서 함수의 효율을 높여보겠습니다.
2. 메모화를 적용한 피보나치 수열 함수 작성하기
def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
if n in [2, 3, 4, 5, 6]:
return memo[n]
if n > 6:
for i in range(7, n+1):
if i in memo: pass
else:
memo[i] = memo[i-2] + memo[i-1]
return memo[n]
가장 먼저 함수를 선언할 때 파라미터 값으로 memo라는 이름으로 딕셔너리를 포함해 주었습니다. 저는 간단하게 n이 1부터 6번째일때 피보나치 수열 값을 딕셔너리에 초기값으로 미리 메모를 해 두었습니다.
def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
if n in [2, 3, 4, 5, 6]:
return memo[n]
내가 구하고자 하는 것은 피보나치 수열의 n번째 값입니다. 만약 n이 2, 3, 4, 5, 6인 경우 (문제 조건에서 n은 2 이상의 정수라고 했으므로 1은 제외합니다) memo 딕셔너리의 해당하는 value 값을 바로 리턴하고 함수를 종료하게 됩니다.
if n > 6:
for i in range(7, n+1):
if i in memo: pass
else:
memo[i] = memo[i-2] + memo[i-1]
return memo[n]
만약 n이 6보다 크면 어떻게 해야 할까요?
주어진 n의 값이 50일 때를 예시로 생각해 봅시다. 우리는 50번째 값을 구하기 위해 48, 49번째 값이 필요합니다.
49번째 값을 구하기 위해서는 47, 48번째가 필요하고
48번째 값을 구하기 위해서는 46, 47번째가 필요합니다.
결국 50번째 값을 구하기 위해서는 1부터 49번째까지 피보나치 수열 값을 모두 알아야 합니다.
그럼 메모화는 어떻게 작동할까요?
제가 만약 50번째 피보나치 수열 값을 구하기 전에,
40번째 피보나치 수열 값을 먼저 구했다고 생각해 보겠습니다.
fibonacci(40)
# 102334155
우리는 40번째 피보나치 수열 값을 구하기 위해 지금 1번째~39번째 피보나치 수열의 값을 열심히 구했습니다.
이제 다음으로 50번째 피보나치 수열 값을 구하려고 합니다.
먼저 메모화를 해놓지 않은 경우를 생각해 봅시다.
우리는 이미 1번부터 40번째까지의 값을 이전에 미리 구한 전적이 있지만
따로 기록을 해 두지 않았기 때문에 같은 계산을 또 반복해야 합니다.
1번째~49번째 피보나치 수열 값을 열심히 또 구하는 거죠.
하지만 제가 기록을(메모화를) 해 두었다면 얘기가 달라집니다.
즉 처음에 fibonacci(40)을 계산했을 때
memo 딕셔너리에 1번부터 40번까지 피보나치 수열 값을
key(n) : value(값) 형식으로 미리 저장을 해 두었다면,
우리는 fibonacci(50)을 구할 때
1. 1번부터 40번까지는 간단히 딕셔너리에서 값을 찾아 가져올 수 있습니다.
2. 41번부터 49번째 값은 새로 구하고 딕셔너리에 값을 추가해주는 방식으로 계속해서 메모를 해나갈 수 있습니다.
+ 참고로 함수를 여러번 작동하면서 메모장에 추가하는 key와 value 값은 매번 초기화되지 않고 계속해서 누적 기록을 보관합니다.
def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
# 주어진 정수가 2-6중 하나일 경우 바로 메모장에서 수열값을 찾아 리턴, 함수종료
if n in [2, 3, 4, 5, 6]:
return memo[n]
# 주어진 정수가 6보다 큰 경우(7 이상)
if n > 6:
# 7부터 n까지의 정수 i에 대해서
for i in range(7, n+1):
# 만약 메모장에 i값이 이미 메모되어 있다면 그냥 넘어가고
if i in memo:
pass
# 만약 메모장에 i값이 없다면 피보나치 수를 구해서 추가해주세요
else:
memo[i] = memo[i-2] + memo[i-1]
# 메모장에서 n번째 피보나치 수열 값을 찾아 리턴해주세요
return memo[n]
최종 피보나치 함수입니다 :)
내가 구하고자 하는 n의 피보나치 값을 찾기 위해 7부터 n-1번째의 수열값을 계속해서 차례대로 메모장에 누적 메모해나가는 방식입니다. 재귀함수랑 약간 비슷한듯 다른 느낌이네요!
3. 최종 문제풀이
마지막으로 문제 해결을 위해 피보나치 수열을 활용해서 soluton()함수를 작성했습니다. 저는 코딩테스트 문제를 풀 때 이렇게 함수를 나누어 작성하는것을 좋아합니다. 함수 안에 함수 작성하는거 시러요.....(개취)
def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
if n in [2, 3, 4, 5, 6]:
return memo[n]
if n > 6:
for i in range(7, n+1):
if i in memo:
pass
else:
memo[i] = memo[i-2] + memo[i-1]
return memo[n]
def solution(n):
fibo_num = fibonacci(n)
# fibonacci(30)< 1234567 < fibonacci(31)
# 만약 n이 30 이하라면 바로 fibo_num을 리턴하고(몫이 0이므로 나머지와 동일)
if n <= 30 :
return fibo_num
# 만약 n이 30보다 크다면 fibo_num을 1234567으로 나눈 나머지를 리턴
else :
return fibo_num % 1234567
프로그래머스 JadenCase 문자열 만들기 문제를 가지고 방법을 설명해 보겠습니다. (다른 다양한 문제에서도 활용할 수 있습니다!)
문제 : JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.
이렇게 공백문자가 연속해서 나올 수 있다는 조건이 있는 경우 split() 함수를 사용하면 공백 여러개가 모두 없어져버리므로 조심해야 합니다.
저는 먼저 단어 1개를 JadenCase로 바꾸어 리턴하는 함수 jaden을 작성했습니다.
def jaden(w):
try:
# 첫 번째 글자가 정수일 때
int(w[0])
return w[0] + w[1:].lower()
except:
# 첫 번째 글자가 정수가 아닐 때
return w[0].upper() + w[1:].lower()
이렇게 작성한 jaden 함수를 가지고 최종 solution 함수를 작성해 볼게요.
import re
먼저 정규식 패키지를 불러옵니다.
word = "Hello World Bye"
위의 예시를 단어와 공백문자로 구분한 리스트를 어떻게 만들 수 있을까요?
word = "Hello World Bye"
re.findall("\S+|\s+",word)
# ['Hello', ' ', 'World', ' ', 'Bye']
re.findall() : RE가 일치하는 모든 부분 문자열을 찾아 리스트로 반환합니다. 활용해서 원하는 구성요소를 찾아 리스트로 만들어줍니다.
\s+ : 일치하는 모든 공백 문자를 찾아줍니다. (여러 개의 공백도 하나로 평탄화하지 않고 유지한 채로 찾아줍니다.)
\S+ : 일치하는 모든 비공백 문자를 찾아줍니다.
결과를 보면 여러 개의 공백 문자가 잘 보존되어 있는 것을 볼 수 있습니다. 이제 최종 솔루션 함수를 작성해 볼게요.
def jaden(w):
try:
# 첫 번째 글자가 정수일 때
int(w[0])
return w[0] + w[1:].lower()
except:
# 첫 번째 글자가 정수가 아닐 때
return w[0].upper() + w[1:].lower()
import re
def solution(s):
# 입력 받은 s를 whitespace와 nonwhitespace로 구분합니다
words = re.findall("\S+|\s+", s)
answer = ""
for word in words:
# 만약 공백문자가 아니라면 jaden 함수를 적용해서 answer에 추가합니다.
if word.isalnum():
answer += jaden(word)
# 만약 공백문자라면 그냥 바로 answer에 추가합니다.
else:
answer += word
return answer
정확성: 100.0
합계: 100.0 / 100.0
끝입니다! 정규식이 기억에 잘 남지는 않지만,
잘만 숙지해 두면 연속 공백문자 처리를 해야하는 문제에서 요긴하게 잘 쓸 수 있답니다 :-)
프로그래머스 코딩테스트 1단계에 수록되어있는 카카오 인턴십 '키패드 누르기' 문제를 풀었습니다. 풀고 나서 코드가 좀 길다고 생각했는데 다른 사람들의 풀이를 보니 다들 비슷한 길이라서 안심이 되었습니다. (한심...ㅎ) 길다고 무조건 나쁜 코드, 짧다고 무조건 좋은 코드는 아니긴 합니다. 그래도 최대한 니트하고 간결하게 작성하고싶은 욕심이 드는 건 어쩔 수가 없네요 ㅎ_ㅎ (그럼에도 불구하고 제 코드는 항상 긴 편인거 같아요.)
저는 키패드에 좌표 개념을 도입하여 간단하게 문제를 풀어보았습니다. 문제 풀이 시간은 5분-10분정도로 그래도 최근에 연습했던 알고리즘 문제들에 비교하면 비교적 수월했던 문제였던 것 같습니다. 그럼 풀어보겠습니다!
문제 상황 :이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
1. 엄지손가락은 상하좌우 4가지 방향... (중략....)
자세한 문제 상황과 조건, 입출력, 테스트 케이스 등은 꼭 프로그래머스에서 확인해 보세요!
먼저 정수로 이루어진 리스트 numbers가 인풋으로 주어집니다. 문제 조건을 보면, 정수가 1, 4, 7일 때에는 바로 왼손을, 3, 6, 9일때는 바로 오른손을 쓰면 되기 때문에 아무런 제약이 없어서 굉장히 쉽습니다. 우리가 고민해야 할 부분은 정수가 2, 5, 8, 0일 때입니다.
2, 5, 8, 0이 주어졌을 때 조건에 맞게 손가락을 움직이기 위해서는
1) 그 전의 손가락 위치를 알고 있어야 합니다.
2) 그 전의 손가락 위치와 2/5/8/0 사이의 거리를 숫자로 나타낼 수 있어야 합니다.
첫줄을 파이썬 인덱싱과 같이 0부터 시작할까 하다가 보다 직관적으로 하기 위해 1부터 시작해줬는데, 0부터 시작해도 큰 상관은 없습니다.
current_left_thumb, current_right_thumb라는 변수명을 사용하여 왼손/오른손을 구분하여 현재 손가락이 어디 있는지를 좌표값으로 표현했습니다. 변수명이 조금 길고 번잡하긴 하지만 직관적으로 이해할 수 있어서 스스로 코드 이해하기가 편했습니다. 이 두 가지 변수는 앞으로 numbers에 주어진 정수값에 따라 손가락이 움직일 때 함께 업데이트가 되어 갈 예정입니다!
[2] 1/4/7, 3/6/9 처리
for number in numbers:
if number == 1:
answer += "L"
current_left_thumb = (1, 1)
elif number == 4:
answer += "L"
current_left_thumb = (2, 1)
elif number == 7:
answer += "L"
current_left_thumb = (3, 1)
elif number == 3:
answer += "R"
current_right_thumb = (1, 3)
elif number == 6:
answer += "R"
current_right_thumb = (2, 3)
elif number == 9:
answer += "R"
current_right_thumb = (3, 3)
다음으로 numbers 리스트의 값(value)를 가지고 하나씩 살펴보면서 이터레이션을 돌려줍니다. 리스트 이터레이션은 습관적으로 인덱스로 하게 되는데, 이번 문제에서는 굳이 인덱스로 조회할 필요가 없어서 편했습니다.
만약 number가 1/4/7중에 하나라면 answer 스트링에 L을 추가하고 해당 좌표값으로 왼손을 움직입니다(current_left_thumb 변수의 좌표를 업데이트합니다.). 만약 number 3/6/9중에 하나라면 answer 스트링에 R을 추가하고 해당 좌표값으로 오른손을 움직입니다(current_right_thumb 변수의 좌표를 업데이트합니다.).
이 부분의 문법이 어쩔수없이 위처럼 길어지게 되었는데, 어떻게 하면 더 짧게 쓸 수 있을까 잠깐 고민했어요. 하지만 지금 이대로도 아주 직관적이고 이해하기 편하기 때문에 굳이 줄이지 않아도 되겠다고 판단하고 다음 단계로 넘어갔습니다.
[3] 2/5/8/0 처리
elif number in [2, 5, 8, 0]:
if number == 2: x = 1
if number == 5: x = 2
if number == 8: x = 3
if number == 0: x = 4
다음으로 가장 중요한 2, 5, 8, 0입니다. 저는 2, 5, 8, 0이 모두 같은 세로줄에 있다는 점에 착안하여 아이디어를 얻어서 2/5/8/0의 열(y)을 2로 고정하고 행(x)만 변수로 각각 1/2/3/4를 할당해 주었습니다. 더 자세히 설명해보겠습니다.
숫자 2의 좌표값은 (1, 2)입니다.
숫자 5의 좌표값은 (2, 2)입니다.
숫자 8의 좌표값은 (3, 2)입니다.
숫자 0의 좌표값은 (4, 2)입니다.
따라서 숫자 2, 5, 8, 0의 좌표를 (x, 2)와 같이 표현하고 x에만 각각 1/2/3/4를 할당해 주어 반복을 줄이겠다는 의미입니다.
이제 거리 구하기로 넘어갑니다. 우리는 current_left_thumb와 current_right_thumb 라는 변수에 각각 왼손과 오른손 엄지의 직전 좌표값을 저장해 두고 있어요. 우리가 가고자 하는 2/5/8/0의 좌표값과 왼손, 오른손 사이의 거리를 각각 구해보도록 하겠습니다.
일반화된 식을 쓰기 전에 예시를 가지고 생각을 열어 볼게요. 키패드 2와 6 사이의 거리는 2입니다. 좌표로 어떻게 구할 수 있을까요? 키패드 2의 좌표는 (1, 2), 키패드 6의 좌표는 (2, 3)입니다. x값의 차이 1과 y값의 차이 1을 더해 주면 간단히 2가 나오는 것을 알 수 있어요. 키패드 8과 키패드 1의 경우는 어떨까요? 우선 거리는 3입니다. 좌표로 확인해 봅니다. 키패드 8의 좌표는 (3, 2)입니다. 키패드 1의 좌표는 (1, 1)입니다. x값의 차이 2와 y값의 차이는 1이며 둘을 더해 주면 3이 됩니다. 이제 일반화가 되었습니다.
if distance_r < distance_l:
# 오른손이 가야 하는 거리가 더 짧을 때
answer += "R"
current_right_thumb = (x, 2)
elif distance_r > distance_l:
# 왼손이 가야 하는 거리가 더 짧을 때
answer += "L"
current_left_thumb = (x, 2)
else:
# 왼손 = 오른손 거리가 같을 때
if hand == 'right':
# 오른손잡이라면
answer += "R"
current_right_thumb = (x, 2)
else:
# 왼손잡이라면
answer += "L"
current_left_thumb = (x, 2)
이제 거리를 비교합니다. 오른손이 가야 하는 거리가 더 짧을 때, 왼손이 가야 하는 거리가 짧을 때, 왼손과 오른손이 가야할 거리가 같을 때로 크게 셋으로 나누어 생각합니다. 특히 왼손, 오른손 거리가 같다면 왼손잡이인지 오른손잡이인지를 판단하는 것이 중요합니다.
이제 제가 작성한 함수를 한 번에 보겠습니다.
def solution(numbers, hand):
answer = ""
current_left_thumb = (4, 1)
current_right_thumb = (4, 3)
for number in numbers:
if number == 1:
answer += "L"
current_left_thumb = (1, 1)
elif number == 4:
answer += "L"
current_left_thumb = (2, 1)
elif number == 7:
answer += "L"
current_left_thumb = (3, 1)
elif number == 3:
answer += "R"
current_right_thumb = (1, 3)
elif number == 6:
answer += "R"
current_right_thumb = (2, 3)
elif number == 9:
answer += "R"
current_right_thumb = (3, 3)
elif number in [2, 5, 8, 0]:
if number == 2: x = 1
if number == 5: x = 2
if number == 8: x = 3
if number == 0: x = 4
distance_r = abs(current_right_thumb[0] - x) + abs(current_right_thumb[1] - 2)
distance_l = abs(current_left_thumb[0] - x) + abs(current_left_thumb[1] - 2)
if distance_r < distance_l:
answer += "R"
current_right_thumb = (x, 2)
elif distance_r > distance_l:
answer += "L"
current_left_thumb = (x, 2)
else:
if hand == 'right':
answer += "R"
current_right_thumb = (x, 2)
else:
answer += "L"
current_left_thumb = (x, 2)
return answer
정확성: 100.0 합계: 100.0 / 100.0
숫자가 2, 5, 8, 0일 때 열 좌표가 2로 모두 동일하다는 점에 착안하여 행 좌표만 x로 변수 할당을 해줌으로써 반복을 줄일 수 있었습니다. 비록 엄청 짧은 코드는 아니지만 깔끔하고 직관적으로 풀이할 수 있어서 좋았습니다!
0과 1로 이루어진 n * m 크기의 미로 그래프가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
먼저 상하좌우로 움직일수 있는 x, y 델타값을 리스트로 작성한다.
def dfs_escape(start = (0, 0)):
# x, y의 현재 포지션을 정해 준다.
x_pos = start[0]
y_pos = start[1]
# 할 일을 기록할 디큐 리스트 q를 작성한다.
q = deque()
# 가장 처음 초기값을 세팅해준다. x, y의 좌표값 위치를 튜플로 집어넣는다.
q.append((x_pos, y_pos))
# 할 일이 없을 때까지 반복!
while q:
now_x, now_y = q.popleft()
# 상하좌우 4번 반복
for i in range(4):
next_x = now_x + dx[i]
next_y = now_y + dy[i]
# 만약 다음으로 갈 좌표값이 미로를 벗어나지 않는다면
if 0 <= next_x < n and 0 <= next_y < m:
if graph[next_x][next_y] == 1:
graph[next_x][next_y] = graph[now_x][now_y] + 1
q.append((next_x, next_y))
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
[ 입력 조건 ] 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
[출력조건] X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다. 이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
입력 예시 1.
4 4 2 1 1 2 1 3 2 3 2 4
입력 예시 2.
4 4 1. 1 2 1 3 2 3 2 4
입력 예시 3.
4 3 2 1 1 2 1 3 1 4
출력 예시 1. 4
출력 예시 2. 2 3
출력 예시 3. -1
예시 2번으로 문제를 풀어보자.
n, m, k, x = map(int , input().split())
# 4 4 1 1
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input("출발 도착").split())
graph[a].append(b)
graph
# [[], [2, 3], [3, 4], [], []]
앞으로 출발 도시 x로부터 각각의 모든 도시까지 거리를 distance로 계산해줄 것이다.
(n+1)을 곱해주는 이유는 가상의 0번 도시를 설정하여 인덱스를 편하게 계산해주기 위함이다.
앞으로 distance에서 자기 자신과의 거리는 0으로, 자기 자신을 제외한 다른 도시는 모두 INF로 시작하는 점을 기억하자.
def solution(start):
# 앞으로 방문해야할 도시 리스트는 디큐 리스트 q로 둔다.
q = deque()
# 출발점 도시 x로부터의 거리를 나타내는 디큐 리스트 distance를 만든다.
distance = deque([INF] * (n+1))
# 초기값 세팅
q.append(start)
distance[start] = 0
# 더이상 방문할 도시가 없을 때까지 반복하기
while q:
# 지금 방문하는 도시 now
now = q.popleft()
for next_city in graph[now]:
# 만약 아무도 오지 않았던 신규 방문지라면
if distance[next_city] == INF:
# 본 문제에서는 도시간의 거리가 1이므로 1을 더하지만
# 문제 조건 따라 1이 아니게 될 수 있음
distance[next_city] = distance[now] + 1
q.append(next_city)
# 디스턴스 리스트를 리턴
return distance
dis_result = bfs_city(x)
dis_result
# deque([inf, 0, 1, 1, 2])
dis_k = [i for i, v in enumerate(dis_result) if v == k]
dis_k
# [2, 3]
if dis_k == []:
print(-1)
else:
while dis_k:
print(dis_k.pop(0))
# 2
# 3