https://www.acmicpc.net/problem/2447

문제 풀이

해당 문제는 처음 반복문을 접할 때 풀어보는 별 찍기의 재귀버전이다.

3X3 크기의 한 패턴이 정해져 있고 크기가 증가할수록 같은 패턴이 반복되는 형태인데 처음엔 직관적으로 간단하게 생각해서 9 부분으로 나눠 각 Position에 대해 번호를 파라미터로 넘기고 해당 Position에 따라 별, 공백, 별 줄 바꿈 출력을 생각했으나 뜻대로 되지 않았다.

3X3 패턴이 출력되는 만큼 줄 바꿈도 같이 출력이 되었고 일정한 패턴의 확장이 아니라 그냥 패턴의 연속된 출력이었기 때문이다.

그래서 접근 방식을 다시 생각해봤다.

일단 3X3 패턴을 하나의 원소로 가정하고 3배씩 증가할 때마다 행과 열을 복사하는 방식이다.

위 사진처럼 직전의 패턴에 대해 증가할때마다 행을 3배로 복사하고 1,3번째 행은 열을 3배로, 2번째 행은 패턴의 길이만큼 공백을 넣어주면 된다.

파이썬은 리스트나 문자열의 복사가 상당히 쉬운 편이기 때문에 다행인 것 같다.

직전의 패턴에서 한 줄씩 문자열로 치환을 하면 나머진 구현에 어려움이 있을 것 같진 않다.

N=int(input())
# 하나의 별표에서 시작한다 가정
res=["*"]
def func(n):
    global res
    if n>3:
        func(n//3)
    # 행 X3
    res=res*3

    # 열 X3
    for i in range(len(res)//3):
        res[i]=res[i]*3
    # 열 + 공백 + 열
    for i in range(len(res)//3,len(res)*2//3):
        res[i]=res[i]+" "*len(res[i])+res[i]
    # 열 X3
    for i in range(len(res)*2//3,len(res)):
        res[i]=res[i]*3

func(N)
for i in range(len(res)):
    print(res[i])

재귀를 타면서 문자열 리스트를 공유해야 하기 때문에 결과 리스트를 전역변수로 공유하는 global을 사용했다.

필자는 이게 직관적이기에 사용했는데 각자 파라미터로 직접 데이터를 보내는 방식과 비교하여 본인이 편한 방식대로 구현하면 된다.

문제에서 입력 조건이 3 이상이기 때문에 조건문에 3 초과인 경우 재귀를 타도록 구현하였는데 제출하고 생각해 보니 애초에 res 리스트는 빈 리스트로 초기화하고 n == 1인 경우에 res 리스트를 별표 문자열 하나로 초기화 하는 방식이 다소 깔끔하지 않을까 생각이 든다.  

문제를 맞긴 했지만 처음에 다소 접근 방식에서 헤맸던 문제이다.

함수를 실행시켰을 때와 재귀를 타고 다시 실행했을 때의 실행결과를 고려하다 보니 스스로 발목을 잡는 것처럼 복잡하고 헷갈려서 재귀 문제는 최대한 같은 부분을 단순화시켜서 함수 그 자체가 실행하는 과정에 집중하는 연습과 경험이 필요한 것 같다.

데이터 분석을 하기 위해선 수집된 데이터(Raw Data)를 목적에 맞게끔 가공하는 작업이 필요하다.
 
순금을 뽑기 위해 불순물을 제거하는 것처럼 분석하고자 하는 목적에 맞는 데이터를 추출해야 보다 정확한 분석이 가능하기 때문이다.
 
Raw Data를 분석에 적합한 형태로 가공하는 작업을 전처리 작업이라고 하는데 이 전처리 작업에 유용한 라이브러리인 Pandas에 대해 데이터 분석과 시각화 관련된 공부를 하는 김에 정리하려고 한다.
 

Pandas란

Pandas는 데이터 조작과 분석을 위한 Python의 라이브러리이다.
 
데이터 구조는 Series와 DataFrame으로 구성되어 있다.

• 시리즈(Series): 시리즈는 1차원 배열과 같은 데이터 구조로, 각각의 데이터에 인덱스가 부여되어 있다.
  예를 들어, 날씨 정보를 담은 시리즈에서는 날짜가 인덱스로 사용되고, 각 날짜에 해당하는 온도가 시리즈의 값으로 들어갈 수 있다.
• 데이터프레임(DataFrame): 데이터프레임은 연속된 여러 시리즈로 엑셀과 같은 표 형식의 2차원 배열 데이터 구조다.
  예를 들어, 여러 날짜에 대한 온도, 습도, 강수량 정보를 담은 여러 시리즈를 합쳐서 데이터프레임으로 만들 수 있다.

Pandas를 이용하여 Data를 쉽게 로딩하고 정리, 분석, 시각화할 수 있으며 DB와 유사한 연산을 지원하기 때문에 Data를 편리하게 처리할 수 있다.
 
따라서 Pandas는 데이터 분석, 머신러닝, 통계 등 다양한 분야에서 사용된다.
 

Pandas 사용하기

Pandas를 설치하는 명령어는 다음과 같다.

pip install pandas

위 사진처럼 뜬다면 설치가 완료된 것이다.
 
각 함수를 사용한 결과를 보면서 어떤 상황엔 어떤 함수를 써야 하는지 알아보자.
 
1. 데이터 읽어오기
 
크게 엑셀에서 읽어오거나 직접 데이터를 입력하는 두 가지 방법이 있다.
 

위 사진과 같은 데이터가 있을 때 Pandas에서 사용하는 코드와 출력 결과는 다음과 같다.
 

import pandas as pd

# 엑셀 파일에서 데이터 읽어오기
excel_file_path = 'user_data.xlsx'

# csv파일일 경우
# df = pd.read_csv(excel_file_path, encoding='utf-8-sig')

# excel파일일 경우
df = pd.read_excel(excel_file_path)

# 읽어온 데이터 출력
print(df)

# 직접 데이터 입력
data = {'이름': ['홍길동', '김철수', '이영희','고길동'],
        '나이': [25, 30, 22, None],
        '직업': ['학생', None, '디자이너','개발자']}

# 데이터프레임 생성
df = pd.DataFrame(data)

# 생성한 데이터프레임 출력
print(df)

# 데이터 일부 확인
print("df.head(2)")
print(df.head(2))
print("df.tail(1)")
print(df.tail(1))

 
출력 결과를 보면 알 수 있듯이 엑셀처럼 2차원 배열 형태를 확인할 수 있고 첫 번째 행이 컬럼 명, 두 번째 행부터는 자동으로 인덱스가 붙어있다.
 
직접 데이터를 넣을 경우엔 딕셔너리의 키를 컬럼 명으로, 값을 데이터 리스트로 만든 후 DataFrame 함수의 파라미터로 넣으면 된다.
 
또한 데이터가 많을 경우 전체 출력을 하기 어렵기 때문에 데이터 구조나 예시 데이터를 확인하기 위해 head(), tail() 함수를 사용하면 된다.
 
Default는 5줄이고 파라미터에 넣은 숫자만큼의 행을 가져오기 때문에 SQL의 LIMIT과 같은 기능이다.
 

print("컬럼 명")
print(df.columns)

print("행, 열 크기")
print(df.shape)

print("데이터 정보 확인")
print(df.info())

print("요약 통계 확인")
print(df.describe())

 
각각의 출력 결과는 다음과 같다.
 

 
컬럼명과 행열의 크기, 데이터들의 대략적인 요약, 숫자 데이터들의 통계를 확인할 수 있다.
 
이를 이용해 행렬의 크기와 non-null의 Count를 비교해서 데이터가 없는(Null 값인) 부분이 있다면 차후에 계측값 제거를 통해 가공해야겠다는 생각을 할 수 있다.
 
Data Frame에서 특정 컬럼을 선택하여 Series를 추출할 수 있는데 컬럼 하나를 추출할 때와 여러 개를 추출할 때의 파라미터 값을 잘 확인해야 한다.
 

print("열 선택")
selected_column = df['나이']
print(selected_column.head())
print(selected_column.size, selected_column.count())
selected_columns = df[['이름', '나이']]
print(selected_columns.head())
print(selected_columns.size)
print(selected_columns.count())
print(selected_columns.value_counts())

 
단일 컬럼 선택 시 문자열 하나만 들어가지만 복수 컬럼 선택 시 리스트 형태의 컬럼명을 파라미터로 보내며 Count 관련 함수는 Null 값이 들어간 행을 제외하고 세기 때문에 Law Data에서 자신에게 필요한 데이터만 추출하면 유용하게 사용할 수 있다.
 

print('조건식을 이용한 열 선택')
selected_column = df[df['이름'] == "홍길동"]
print(selected_column.head())

 
특히 특정 조건에 해당하는 데이터를 추출하려면 컬럼 선택 값으로 추출하고자 하는 조건식을 사용하면 된다.
 
이를 이용하면 특정 나이대, 특정 지역에 해당하는 데이터를 추출할 수 있다.
 

print("Null 값이 있는 데이터 갯수")
print(df.isnull().sum())
print("Null값을 제거한 데이터")
print(df.dropna())
print("직업의 Null값을 제거한 데이터")
print(df.dropna(subset=['직업']))

 
isnull() 함수는 데이터가 Null인 경우 True를 반환하는데 Sum()을 통해 합계를 구함으로써 Null값을 카운트하는 효과를 낼 수 있다.
 
또한 dropna()는 데이터가 Null인 행을 제거한 데이터를 반환하며 파라미터로 특정 컬럼의 Null 값만 제거할 수 있기 때문에 항상 Law Data를 다루기 전 dropna()를 사용하여 빈 값이 있으면 안 되는 컬럼의 데이터를 제거하는 게 좋을 것 같다.
 

print("Null값 채우기")
print(df.fillna({'나이' : 0 , '직업' : '없음'}))

 
반대로 Null 값을 일괄적으로 채워야 할 때가 있는데 fillna() 함수를 사용하면 된다.
 
한 가지 값으로 채울 수 있다면 해당 값만 파라미터로 보내면 되지만 컬럼마다 초기화해야 하는 값이 다르다면 딕셔너리 형태로 Key는 컬럼명, Value는 Data 값으로 설정하면 위 사진처럼 채워진다.

일을 하다 보면 생각보다 자주 단순 반복작업을 하게 되는 경우가 있습니다.
 
때에 따라서 많은 데이터를 수집해야 할 수도 있고 주기적으로 메일을 보낸다거나 엑셀 파일의 수많은 데이터를 수정해야 할 수도 있습니다.
 
사람이 동시에 할 수 있는 일의 양과 그에 따른 시간은 한정적이기 때문에 단순 반복 작업을 자동화시킨다면 그만큼 낭비되는 시간을 아껴 업무 효율화를 추구할 수 있습니다.
 
마치 공장에서 일련의 프로세스들을 자동화 기계를 통해 비용과 시간 대비 생산량을 극대화시키듯, 정해진 패턴이 있고 비교적 많은 시간을 요구하는 작업이라면 컴퓨터를 통해 빠르고 효과적으로 처리할 수 있습니다.
 
물론 기본적으로 특정 기능을 하는 프로그램이 아니라 직접 프로그래밍을 통해 자신이 원하는 기능을 구현하는 것이기 때문에 Python 혹은 최소한 하나의 프로그래밍 언어에 익숙하고 자신의 생각을 코드로 나타낼 수 있는 역량이 필요합니다.
 
만약 코드를 직접 구현할 자신이 없다면 언어와 관련된 학습은 구글링을 통해 쉽게 집약된 자료를 찾을 수 있고 자신의 생각을 코드로 나타내는 부분은 알고리즘 연습을 통해 충분히 독학 가능하다고 생각합니다.
 
https://kmong.com/knowhow/gig/290286

 
알고리즘 같은 경우, 집약된 자료를 찾기 힘들어 정리할 겸 과외 경험을 살려 최대한 이해하기 쉽게 작성했으며 반응도 좋았기에 충분히 도움 될 것이라 생각합니다.
 
자동화 프로그램을 작성하는데 자신의 상황에 맞게 로직을 구성하고 해당 논리를 그대로 코드로 구현할 수준이면 되기 때문에 굳이 어려운 알고리즘을 학습할 필요가 없어 부담 갖지 않으셔도 됩니다.
 
이를 통해 기본적인 프로그래밍에 대한 역량을 갖췄다면 이젠 실 생활에 적용하여 소위 말하는 "일잘러"로 거듭나는 일만 남았습니다.
 
실제로 저도 취준생 때 재밌을 것 같아 직접 구현해 보고 이를 프로젝트에 적용하여 팀원들에게 좋은 평가를 받았었고 면접에서도 강점으로 어필하였으며 실무에서도 효율적인 업무가 가능했습니다.
 
또한 전자책을 완성한 직후 평가를 위해 지인과 직장 선배들에게 공유했었는데 일관되게 긍정적인 피드백을 받았습니다.
 
아무래도 소비자분들께 판매를 하는 전자책이기 때문에 저 스스로가 완벽하다고 생각하지 않으면 서비스를 올려두지 않습니다.
 
관심 있으신 분들은 아래 링크를 통해 어떤 내용들이 있는지 확인해 보고 고민해 보시는 것을 추천드립니다.
 
https://kmong.com/knowhow/gig/490311

 
만약 구매하신 분들 중에서 날카로운 피드백을 크몽을 통해서나 블로그 댓글로 남겨주신다면 적극 수용, 반영하고 수정된 내용들을 다시 드리도록 하겠습니다.

파이썬은 인터프리터 언어라 컴파일 언어에 비해 비록 느리지만 사용자 친화적으로 쉬운 구문과 광범위한 응용 프로그램에 사용할 수 있단 장점이 있다.

특히 강력한 라이브러리로 데이터 분석, AI, 자동화 등에 강점을 보이는데 이번에는 자동화(매크로)에 자주 쓰이는 Pyautogui에 대해 알아보자.

시작 전에 처음 들어봤거나 확실하게 알지 못하는 사람들을 위해 매크로가 무엇인지 알아보자.

매크로란 컴퓨터 과학 분야에서 정해진 순서에 따라 특정한 입력 시퀀스가 출력 시퀀스를 정의하는 규칙이나 패턴을 말한다. (출처 : 위키백과)

즉, 쉽게 풀어서 말하자면 정해진 반복 작업을 컴퓨터가 수행하는 것이다.

특히 게임이나 티켓팅, 수강신청 등에서 매크로란 단어를 많이 접했을 텐데 이들의 공통점이 정해진 위치를 반복적으로 이동, 클릭, 입력한다는 점이다.

로직만 잘 구성한다면 불필요한 반복 작업을 컴퓨터에게 대신시킬 수 있기 때문에 아주 유용한 스킬이다.

Pyautogui 사용하기

그럼 Pyautogui를 설치해 보자.

필자는 윈도우 환경이며 Visual Studio Code를 사용하기 때문에 터미널에 바로 입력하면 된다.

명령어는 pip install pyautogui이고 위 사진처럼 Successfully installed 로그가 찍힌다면 설치가 완료된 것이다.

이제 Pyautogui를 설치했으니 관련 함수들을 알아보자.

함수들은 크게 마우스, 키보드, 이미지 관련 함수로 나눌 수 있는데 상당히 함수가 많기 때문에 그중에서도 자주 쓰일만한 함수들만 정리했다. 

특히 빨간 표시는 생략 가능한 옵션을 뜻한다.

특히 매크로는 정해진 좌표를 반복 클릭하기 때문에 구현 단계에서 좌표를 얻을 수 있는 mouseInfo()가 상당히 유용한 함수다.

주의해야 할 점은 키보드 관련 함수에서 알파벳키를 입력하고 실제 입력 상황에서 한글로 되어 있다면 상관없지만 write로 직접 한글 입력은 지원하지 않기 때문에 한글 입력을 위해선 편법을 위한 추가 사항이 조금 필요하다.

바로 pyperclip을 설치해서 클립보드에 한글을 복사 후 붙여 넣기 하는 방식이다.

명령어는 pip install pyperclip이며 pyautogui를 설치할 때처럼 동일하게 하면 된다.

import pyperclip, pyautogui

# 클립보드에 한글 문자열 복사
pyperclip.copy('한글 입력 테스트')

# ctrl + v 로 붙여넣기
pyautogui.hotkey('ctrl', 'v')

설치 후 위 코드처럼 작성하면 한글을 입력하는 듯한 효과를 볼 수 있다.

모든 함수를 사용한 예제를 보기엔 너무 방대하므로 간단하게 특정 위치를 반복 클릭하는 매크로와 임시 비밀번호를 생성해서 저장하는 예제를 살펴보자.

반복 클릭 매크로

import pyautogui

# 첫 시작 위치로 이동
pyautogui.moveTo(334, 351)

# 시작 위치에서 마우스가 벗어나면 반복 중지
while pyautogui.position().x == 334 and pyautogui.position().y == 351:
    pyautogui.click()
    pyautogui.moveTo(320, 446)
    pyautogui.click()
    pyautogui.moveTo(334, 351)

위 코드는 특정 위치를 무한 반복 클릭하는 코드다.

이때 주의해야 할 점은 마우스를 다루기 때문에 딜레이나 무한 루프를 탈출할 조건을 사용하지 않을 경우 이도저도 못하는 난감한 상황이 발생할 수 있다.

해당 예제에서는 시작 위치를 정하고 마우스가 위치를 벗어날 경우 프로그램을 종료하도록 작성했다.

위와 같은 로직으로 미리 mouseInfo() 함수를 이용해서 좌표 정보를 얻고 작성하면 빠르게 반복 클릭할 수 있다.

임시 비밀번호 생성 후 저장

import pyautogui, random, time

# 길이가 8인 소문자 임시 비밀번호 생성
def temp_pw():
    pw = ''
    for i in range(8):
        pw += chr(random.randrange(97,123))
    return pw

# 메모장 위치
pyautogui.moveTo(496, 423)
pyautogui.doubleClick()

# 메모장이 켜질때까지 대기
time.sleep(1)

# 메모장에 커서 생성
pyautogui.moveTo(604, 713)
pyautogui.click()

# 5개의 임시 비밀번호 생성
for i in range(5):
    pyautogui.write(temp_pw()+'\n')

# 저장
pyautogui.hotkey('ctrl', 's')

# 메모장 종료
pyautogui.hotkey('alt', 'f4')

필자는 임시 비밀번호를 저장하기 위한 메모장을 생성했었고 해당 위치 좌표로 이동 후 더블 클릭으로 켰다.

너무 속도가 빨라 엉뚱한 곳을 클릭하는 것을 방지하기 위해 메모장이 켜질 때까지 대기하려 time.sleep(1)을 했다.

메모장이 켜지면 커서를 생성하기 위해 한번 클릭을 했고 소문자로 이루어진 8자리 임시 비밀번호를 저장 후 종료하는 로직이다.

이처럼 파이썬의 자동화 도구를 잘 사용하면 불필요한 반복 작업을 컴퓨터에게 시킬 수 있어 상당히 편리하고 개인에게 강력한 무기가 될 수 있다고 생각한다.

필자도 종종 필요한 경우 자동화 코드를 작성해서 편리했고 이를 본 주위 사람들이 신기해했던 경험이 있기 때문이다.

차후에 단순한 마우스, 키보드 자동화 말고도 엑셀 파일처럼 업무 자동화에 대해서도 가능한 자세히 포스팅하도록 하겠다.

https://www.acmicpc.net/problem/4485

문제 풀이

왼쪽 위칸인 [0,0]에서 출발 후 오른쪽 아래칸인 [N-1, N-1]에 도착하는 경로를 생각하는 그래프 탐색 문제였다.

다만 흔히 Queue나 Stack을 이용하여 BFS, DFS로 탐색하는 방법이 아닌 Priority Queue를 사용한 다익스트라 문제였다.

이 문제에서 중요한 점은 거리의 최소가 아니라 비용, 즉 가중치의 최소가 중요하기 때문이다.

상당히 돌아가는 경로라 하더라도 비용이 최소면 해당 경로를 택하기 때문에 가중치의 합을 기준으로 최소 비용 경로를 고려해야 한다.

Priority Queue를 이용한 원리는 다음과 같다.

먼저 시작 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는다.

가중치의 합이 가장 작은 노드를 선택한 뒤 해당 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는 행동을 [N-1, N-1]에 도착할 때까지 반복한다.

[N-1, N-1]에 도착하면 해당 가중치를 저장하고 반복을 종료한다.

한 번은 중간에 이동 가능한 노드인지 체크하는 과정에서 이미 방문한 노드가 최소 가중치의 합을 보장하는지 의문을 품는 질문을 본 적이 있었는데 결론부터 말하자면 각 노드에서 가장 먼저 선택되었을 때의 가중치가 최소다.

Priority Queue를 통해 매번 가장 작은 가중치의 합을 선택하기 때문에 두 번째 방문할 때는 같거나 클 수밖에 없기 때문이다.

이제 전체 코드를 통해 설명하도록 하겠다.

import heapq
inf = float('INF')
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
res_num = 1
while True:
    n = int(input())
    if n == 0:
        break
    else:
        graph = []
        queue = []
        res = [[inf for i in range(n)]for j in range(n)]
        for i in range(n):
            graph.append(list(map(int, input().split())))
        heapq.heappush(queue, (graph[0][0], 0, 0))
        res[0][0] = graph[0][0]
        while len(queue) > 0:
            temp = heapq.heappop(queue)
            if temp[1] == n-1 and temp[2] == n-1:
                break

            for i in range(len(dir)):
                dy = temp[1]+dir[i][0]
                dx = temp[2]+dir[i][1]
                if 0 <= dy < n and 0 <= dx < n and res[dy][dx] > temp[0]+graph[dy][dx]:
                    res[dy][dx] = temp[0]+graph[dy][dx]
                    heapq.heappush(queue, (temp[0]+graph[dy][dx], dy, dx))
        print("Problem %d: %d" %(res_num,res[n-1][n-1]))
        res_num += 1

4번째 줄까지는 Priority Queue를 사용하기 위한 heapq 선언, 방문하지 않은 노드는 무한대 선언, 노드의 방향 선언, 문제 번호 선언이다.

5번째 줄의 while문을 통해 0을 입력받을 때까지 반복적으로 문제를 처리했다.

12번째 줄의 res는 노드의 최솟값을 갱신하는 리스트로 마지막에 res [N-1][N-1]을 출력하면 된다.

15번째 줄은 시작 노드의 가중치와 y좌표, x좌표 순서대로 넣음으로써 자동으로 MinHeap 구조인 heapq에서 최소 가중치를 꺼내도록 하였다.

18번째 줄의 반복문은 Priority Queue가 빌 때까지 계속 원소를 꺼내는 작업을 하는데 도착지점에 도달한다면 탈출하도록 구현하였다.

방향 탐색을 하기 위해 22번째 줄에서 이동 가능한 노드인지 체크한 후 Priority Queue에 넣어주도록 구현하였다.

구현 방법이나 알고리즘 측면에서 어려운 문제는 아니었지만 우선순위 큐를 거의 사용해보지 않았다면 충분히 떠올리기 어려울 수 있다고 생각한다.

필자 또한 다양한 그래프 문제를 경험해봤지만 습관처럼 BFS, DFS를 사용했기에 해당 문제를 보고 바로 Priority Queue를 떠올리진 못했다.

보다 유연하고 다양하게 생각하도록 노력하는 게 중요한 것 같다.

https://www.acmicpc.net/problem/16928

문제 풀이

전형적으로 그래프 탐색 이론인 BFS(너비 우선 탐색)를 이용하면 쉽게 풀리는 문제다.

다만 보편적인 그래프 탐색은 2차원 배열에서 인덱스 접근을 통해 4방 혹은 8방 탐색을 하며 가장 가까운 Target Node를 찾지만 이번 문제는 1번부터 100번까지 각 노드를 번호로 구분할 수 있는 점, 1부터 6까지 적혀있는 주사위를 던져서 옮긴다는 점에 착안하여 1차원 배열에서 6가지 방법을 고려하면 된다는 것을 깨달아야 한다.

이점 외에는 딱히 조심해야 할 부분이 없으므로 바로 코드를 통해 설명하도록 하겠다.

from collections import deque
edge_info=[0 for i in range(101)]
n,m=map(int,input().split())
visited=[0 for i in range(100)]
queue=deque()
for i in range(n+m):
    temp=list(map(int,input().split()))
    edge_info[temp[0]]=temp[1]

             #curr,cnt
queue.append([1,0])
while len(queue)>0:
    curr,cnt=queue.popleft()
    if curr==100:
        print(cnt)
        break
    elif curr>=94:
        print(cnt+1)
        break
    else:
        for i in range(1,7):
            if edge_info[curr+i]==0 and visited[curr+i]==0:
                visited[curr+i]=1
                queue.append([curr+i,cnt+1])
            else:
                if visited[curr+i]==0:
                    visited[curr+i]=1
                    visited[edge_info[curr+i]]=1
                    queue.append([edge_info[curr+i],cnt+1])

1번째 줄은 deque를 사용하기 위해 모듈을 Import 하였다.

물론 이번 문제는 최대 칸이 100개 밖에 없기 때문에 애초에 사이즈가 작아서 시간 복잡도를 줄이기 위해 굳이 deque를 사용할 필요는 없었지만 막상 필요한 상황에서 참고 문서 없이 Import 하려면 까먹기 때문에 잊지 않기 위해서라도 deque를 사용하였다.

만약 deque가 무엇인지 모르는 사람들은 아래 포스팅을 통해 학습하면 될 것이다.

https://khsung0.tistory.com/14

2번째 줄부터 5번째 줄까지는 간선 정보와 방문 체크, 큐 등을 사용하기 위한 초기화 작업이다.

6번째 줄은 반복문을 통해 간선 정보를 저장하였고 11번째 줄은 1번 칸부터 시작해서 BFS를 진행하기 위해 deque에 초기화했다.

12번째 줄부터는 BFS를 구현한 코드이다.

문제에 주어진대로만 구현하면 되기 때문에 딱히 설명할 부분은 없지만 필자는 조금이라도 시간 복잡도 상으로 효율적인 코드를 구현하기 위해 100일 때는 현재 카운트 출력, 94 이상일 때는 주사위를 한 번만 더 돌리면 100이 나오므로 카운트+1 출력, 그 외의 경우에만 다시 deque에 넣도록 구현하였다.

이렇게 구현하면 매번 deque에 넣을 때도 100을 초과하는지 체크하지 않아도 되기 때문이다.

문제는 10X10의 2차원 그래프인 것처럼 나왔지만 1차원 배열로 변환하여 생각하는 게 필요한 문제였다.

https://www.acmicpc.net/problem/13458

문제 풀이

딱히 시간 복잡도나 공간 복잡도를 고려할 필요도 없이 단순한 사칙연산만 하면 충분히 통과 가능한 브론즈 문제인데 생각보다 정답 비율이 엄청 낮아서 포스팅하기로 했다.

브론즈 문제가 약 27%의 낮은 정답률을 보인다는 것은 난이도 설정이 잘못되었거나 문제에 헷갈릴만한 요소가 있어서 잘못된 방향으로 제출하여 많은 오답을 기록하기 때문이라 생각한다.

그래서 필자가 추측컨대 아마 감독관 수의 최솟값을 구해야 하는 문제에서 "총감독관은 오직 1명만 있어야 하고" 란 지문이 오히려 헷갈리게 했을 가능성이 있는 것 같다.

이 말이 총감독관은 2명 이상 있으면 안 된다고 판단하여 "0명도 가능하지 않나?" 란 생각이 들게 할 수 있는 것 같다.

따라서 "총감독관은 반드시 1명 있어야 하고" 로 바뀌었으면 단번에 맞춰서 정답 비율이 더 높진 않았을까 하는 아쉬움이 남았다.

또한 이 문제에 대해 시간 초과가 뜨는 경우가 종종 있던데 시험장의 수와 응시자의 수가 최대 100만이므로 수학 연산으로 답을 도출해야지 반복문을 통해 일일이 빼는 경우엔 절대 2초 안에 연산이 불가능하다는 것을 생각해야 한다.

방향성만 제대로 잡는다면 상당히 쉬운 문제라 서론이 길었는데 전체 코드를 통해 설명하도록 하겠다.

n=int(input())
n_cnt=list(map(int,input().split()))
b,c=map(int,input().split())
res=0
for i in range(n):
    n_cnt[i]-=b
    res+=1
    if n_cnt[i]>0:
        if n_cnt[i]%c==0:
            res+=(n_cnt[i]//c)
        else:
            res+=(n_cnt[i]//c+1)

print(res)

난이도 답게 상당히 짧고 간결한 코드가 나왔다.

4번째 줄까지는 필요한 입력을 받고 정답으로 출력할 변수를 초기화하는 코드다.

5번째 줄에서 for문으로 전체 시험장을 반복하며 반드시 총감독관이 있어야 하기에 총감독관이 감시할 수 있는 응시자 수를 빼고 res 변수를 카운트했다.

그 뒤에 만약 남은 응시자 수가 부감독관이 감시할 수 있는 응시자 수의 배수라면 나눈 몫을 카운트했고 배수가 아니라면 몫과 더불어 1만큼 더 큰 숫자를 카운트했다.

그 뒤에 카운트 한 숫자만큼 출력하면 통과할 수 있다.

단순 사칙연산 문제로 아주 쉬운 편이었지만 헷갈릴 수 있는 부분이 있어 입력과 출력 예제를 유심히 봐야 하는 문제였다.

https://www.acmicpc.net/problem/3425

문제 풀이

단순하게 주어진 기능들을 조건에 맞게 구현만 하면 되는 문제다.

각 기능들을 하나씩 보면 브론즈~실버 수준의 기능 구현이고 딱히 시간 복잡도나 공간 복잡도에 대해 고민할 필요가 없지만 아무래도 10개의 기능을 각 조건에 맞게 정확히 구현하는 부분에서 티어가 높게 측정되고 약 14%의 낮은 정답률을 보이는 것 같다.

실제로 필자도 주석을 통해 미리 구현 내용을 순서대로 적어두고 차근차근 구현하는 습관을 안 들이다 보니 다소 많은 양 때문에 헷갈리는 부분이 있어서 NameError, IndexError, UnboundLocalError 등의 런타임 에러가 났었다. 

이를 계기로 양이 많은 문제를 접하면 미리 주석을 사용해야겠다는 다짐을 하였다.

구현하는 과정에서는 딱히 어려운 부분이 없기에 전체 코드를 하나씩 따라가보며 설명하도록 하겠다.

def NUM_X(array,num):
    return array.append(num)

def POP(array):
    if len(array)==0:
        return "ERROR"
    else:
        array.pop()
        return 1

def INV(array):
    if len(array)==0:
        return "ERROR"
    else:
        temp=array.pop()
        array.append(temp*(-1))
        return 1

def DUP(array):
    if len(array)==0:
        return "ERROR"
    else:
        temp=array.pop()
        array.append(temp)
        array.append(temp)
        return 1

def SWP(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        array.append(temp1)
        array.append(temp2)
        return 1

def ADD(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp1+temp2)>10**9:
            return "ERROR"
        else:
            return array.append(temp1+temp2)

def SUB(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp2-temp1)>10**9:
            return "ERROR"
        else:
            return array.append(temp2-temp1)

def MUL(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp2*temp1)>10**9:
            return "ERROR"
        else:
            return array.append(temp2*temp1)

def DIV(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        op=1
        if temp1==0:
            return "ERROR"
        else:
            if temp1<0:
                temp1=temp1*(-1)
                op=op*(-1)
            if temp2<0:
                op=op*(-1)
                temp2=temp2*(-1)
            return array.append((temp2//temp1)*op)

def MOD(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        op=1
        if temp1==0:
            return "ERROR"
        else:
            if temp2<0:
                op=op*(-1)
                temp2=temp2*(-1)
            return array.append((temp2%abs(temp1))*op)

command="START"
command_array=[]
while command!="QUIT":
    command=input()
    if command=="QUIT":
        pass
    elif command=="END":
        n=int(input())
        for i in range(n):
            res="START"
            stack=[int(input())]
            for j in range(len(command_array)):
                if len(command_array[j].split())==2:
                    temp=command_array[j].split()
                    res=NUM_X(stack,int(temp[1]))
                elif command_array[j]=="POP":
                    res=POP(stack)
                elif command_array[j]=="INV":
                    res=INV(stack)
                elif command_array[j]=="DUP":
                    res=DUP(stack)
                elif command_array[j]=="SWP":
                    res=SWP(stack)
                elif command_array[j]=="ADD":
                    res=ADD(stack)
                elif command_array[j]=="SUB":
                    res=SUB(stack)
                elif command_array[j]=="MUL":
                    res=MUL(stack)
                elif command_array[j]=="DIV":
                    res=DIV(stack)
                else:
                    res=MOD(stack)
                if res=="ERROR":
                    break
            if res=="ERROR" or len(stack)!=1:
                print("ERROR")
            else:
                print(stack[0])
        input()
        print()
        command=="START"
        command_array.clear()
    else:
        command_array.append(command)

딱 봐도 여태 포스팅한 코드들과는 확연히 양에서 차이가 난다.

비록 양은 많지만 어려운 부분은 없기에 미리 겁먹을 필요는 없다.

먼저 전체적인 구성은 각 기능에 해당하는 10개의 함수를 선언하고 메인 함수에서는 입력방식대로 입력을 받은 후 필요한 경우 해당하는 함수를 호출해서 연산 결과를 사용하는 방식으로 구현하였다.

1번째 줄의 NUM_X는 인자로 받은 숫자를 스택의 가장 위에 저장(Push)하는 함수다.

3번째 줄의 POP은 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 가장 위에 있는 숫자를 제거하는 함수다.

11번째 줄의 INV는 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 첫번째 수(가장 위에 있는 수)의 부호를 바꿔서 저장하는 함수다. (이제 보니 굳이 pop 하지 않고 array [len(array)-1]=-1*array [len(array)-1] 이렇게 직접 접근해서 한 줄로 처리 가능할 것 같다.)

19번째 줄의 DUP는 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 가장 위에 있는 숫자를 한번 더 추가하는 함수다.

28번째 줄의 SWP는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자의 위치를 바꾸는 함수다.

38번째 줄의 ADD는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자를 더한다.

이때 문제 조건에서 연산 결과의 절댓값이 10^9를 넘어간다면 프로그램 에러이므로 꼭 이 부분을 처리해줘야 한다.

49번째 줄의 SUB는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자에서 첫 번째 숫자를 빼면서 이때도 마찬가지로 절댓값이 10^9를 넘어가는지 체크해야한다.

60번째 줄의 MUL은 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자를 곱하고 값을 체크한다.

71번째 줄의 DIV는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자를 첫 번째 숫자로 나눈 몫을 저장하는데 이때 0으로 나눠지는지, 부호는 어떻게 되는지 정확히 판단해서 구현해야 한다.

89번째 줄의 MOD는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자를 첫 번째 숫자로 나눈 나머지를 반환하는데 이때도 마찬가지로 부호와 0으로 나눠질 경우를 예외 처리해야 한다.

106번째 줄부터는 QUIT를 입력받기 전까지 반복하면서 명령어에 해당하는 함수를 실행시키면 된다.

이때 END를 입력받기 전까지 일련의 명령어를 입력받고 수행해야 하므로 명령어를 리스트에 저장해서 수행하는 것을 잊으면 안 된다.

다소 구현해야 하는 기능이 많고 예외처리를 해야 되는 부분도 많아서 각각의 구현 난이도는 쉽지만 어렵게 느껴질 수 있는 문제였다.

주석처리를 통해 차례대로 구현해야 하는 기능을 정리하는 습관을 들여야겠다.