여태 프로젝트를 진행하면서도 DB만 사용했었는데 최대한 다양한 Data를 사용하도록 파일도 얻고 Python의 자동화 도구를 이용한 웹 크롤링도 해봤지만, Data를 넣는데 많은 시간이 걸리고 파일을 얻기 위해 찾아다녀야 한다는 단점들 때문에 API를 활용하는 게 좋아 보인다.
다만 SSAFY에서 강의를 듣는데 API 사용을 어려워하기도 했고 API를 활용하면 코드로 필요한 Data를 얻어서 다양하게 활용할 수 있으므로 나중을 위해 정리하는 겸 API에 대해 알아보자.
Web을 기준으로 대표적 비동기 통신 방식인 AJAX를 사용하여 정리하도록 하겠다.
API란?
API란 Application Programming Interface의 약자로 일종의 소프트웨어 인터페이스이며 다른 소프트웨어에 서비스를 제공하는 것이다.
보다 이해하기 쉽게 말하자면 엄청나게 많은 Data를 저장한 DB에서 개발자가 코드를 이용하여 필요한 Data를 불러오는 것을 뜻한다.
물론 아무나 접근할 수는 없게 회원 가입한 유저에게 유일한 서비스 키(Service Key)를 제공하여 인증된 사용자에게만 필요한 Data를 제공한다.
또한 개발자마다 코드 스타일이 다르고 각기 다른 코드에 동일한 결과를 제공하는 것은 불가능하기에 API를 제공하는 곳에서 요청(Request) 방식과 응답(Response) 방식을 구체적으로 명세해놓고 있다.
하지만 필자처럼 API를 처음 접하는 경우엔 해당 문서가 아무리 친절하고 세세하게 설명해놓았다 하더라도 코드를 복붙 하는 수준이 아니라면 어떻게 구현해야 하는지 감이 잡히지 않을 수 있다.
실제로 카카오 지도 API는 주석과 샘플 코드, 실제 작동방식 등을 Javascript, Javascript+HTML까지 구분하면서 아주 쉽게 이용할 수 있도록 해놨지만 같은 카카오의 개발 가이드에서 주소 검색하기 API는 Request에 대한 정보와 설명을 해놨기에 필요한 부분을 생각해서 조합하는 것은 예상외로 막힐 수 있기 때문이다.
다만 보편적인 그래프 탐색은 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를 사용하였다.
2번째 줄부터 5번째 줄까지는 간선 정보와 방문 체크, 큐 등을 사용하기 위한 초기화 작업이다.
6번째 줄은 반복문을 통해 간선 정보를 저장하였고 11번째 줄은 1번 칸부터 시작해서 BFS를 진행하기 위해 deque에 초기화했다.
12번째 줄부터는 BFS를 구현한 코드이다.
문제에 주어진대로만 구현하면 되기 때문에 딱히 설명할 부분은 없지만 필자는 조금이라도 시간 복잡도 상으로 효율적인 코드를 구현하기 위해 100일 때는 현재 카운트 출력, 94 이상일 때는 주사위를 한 번만 더 돌리면 100이 나오므로 카운트+1 출력, 그 외의 경우에만 다시 deque에 넣도록 구현하였다.
이렇게 구현하면 매번 deque에 넣을 때도 100을 초과하는지 체크하지 않아도 되기 때문이다.
결과 화면
문제는 10X10의 2차원 그래프인 것처럼 나왔지만 1차원 배열로 변환하여 생각하는 게 필요한 문제였다.
딱히 시간 복잡도나 공간 복잡도를 고려할 필요도 없이 단순한 사칙연산만 하면 충분히 통과 가능한 브론즈 문제인데 생각보다 정답 비율이 엄청 낮아서 포스팅하기로 했다.
브론즈 문제가 약 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만큼 더 큰 숫자를 카운트했다.
그 뒤에 카운트 한 숫자만큼 출력하면 통과할 수 있다.
결과 화면
단순 사칙연산 문제로 아주 쉬운 편이었지만 헷갈릴 수 있는 부분이 있어 입력과 출력 예제를 유심히 봐야 하는 문제였다.
각 기능들을 하나씩 보면 브론즈~실버 수준의 기능 구현이고 딱히 시간 복잡도나 공간 복잡도에 대해 고민할 필요가 없지만 아무래도 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를 입력받기 전까지 일련의 명령어를 입력받고 수행해야 하므로 명령어를 리스트에 저장해서 수행하는 것을 잊으면 안 된다.
결과 화면
다소 구현해야 하는 기능이 많고 예외처리를 해야 되는 부분도 많아서 각각의 구현 난이도는 쉽지만 어렵게 느껴질 수 있는 문제였다.
테트리스와 비슷하지만 뿌요뿌요는 같은 색의 슬라임들이 4개 이상 연결되어있으면 터지고 빈 공간을 채운다는 점이 조금 다르다.
따라서 만약 테트리스였다면 행을 기준으로 탐색을 했겠지만 뿌요뿌요는 전체 탐색을 하면서 빈 공간이 아닐 때는 4개 이상 연결되었는지 BFS를 통해 체크하며 4개 이상인 모든 부분들을 빈 공간으로 치환하고 다시 바닥으로 정렬하는 과정을 반복해야 한다.
이때 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터지고 한 번의 연쇄가 추가된다고 하니 연쇄를 추가하는 부분을 정렬하는 과정에 위치시키면 적절할 것이다.
사실 12X6 크기의 행렬이라 상당히 크기가 작아 시간이나 공간에 대한 효율성을 따질 필요성까진 없지만 구현하는 과정에서 다소 헷갈리거나 복잡한 부분이 있었기에 문제를 세분화하여 주석을 통해 구현해야 할 기능들을 구분해놓고 구현하는 것이 도움 될 것 같다.
코드가 짧은 편은 아니라서 한눈에 들어오긴 힘들겠지만 한 줄씩 따라가다 보면 이해할 수 있을 것이다.
graph=[]
dir=[[-1,0],[1,0],[0,-1],[0,1]]
queue=[]
for i in range(12):
graph.append(list(input()))
res=0
while True:
check=True #터졌는지 체크하는 변수
visited=[[0 for i in range(6)]for j in range(12)]
changed_col=[]
del_queue=[]
for i in range(12):
for j in range(6):
#뿌요가 존재하는 칸인 경우
if graph[i][j]!="." and visited[i][j]==0:
curr_char=graph[i][j] #현재 뿌요 저장
temp_cnt=0
queue.append([i,j])
visited[i][j]=1
#현재뿌요와 연결되어있는 뿌요 탐색
while len(queue)>0:
curr=queue.pop(0)
temp_cnt+=1
for k in range(len(dir)):
dy=dir[k][0]+curr[0]
dx=dir[k][1]+curr[1]
if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char and visited[dy][dx]==0:
queue.append([dy,dx])
visited[dy][dx]=1
#연결된 뿌요가 4개 이상일 경우
if temp_cnt>=4:
check=False
changed_col.append(j)
del_queue.append([i,j])
while len(del_queue)>0:
temp=del_queue.pop(0)
graph[i][j]="."
for k in range(len(dir)):
dy=dir[k][0]+temp[0]
dx=dir[k][1]+temp[1]
if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char:
del_queue.append([dy,dx])
graph[dy][dx]="."
if dx not in changed_col:
changed_col.append(dx)
if check:
break
else:
res+=1
#빈칸없게 위에 있는 뿌요들을 정렬
for i in range(len(changed_col)):
for j in range(10,-1,-1):
if graph[j][changed_col[i]]!=".":
curr=j
while curr<=10 and graph[curr+1][changed_col[i]]==".":
graph[curr+1][changed_col[i]],graph[curr][changed_col[i]]=graph[curr][changed_col[i]],graph[curr+1][changed_col[i]]
curr+=1
print(res)
6번째 줄까지는 그래프를 입력받고 방향 리스트, 사용할 큐 초기화, 결과 변수를 선언했다.
8번째 줄의 while문은 더 이상 터진 뿌요들이 없을 때까지 터뜨리고 빈칸을 정렬하는 과정을 반복하는 부분이다.
check변수를 통해 터진 뿌요가 없을 경우 반복문을 탈출하고 매번 방문했는지 체크하는 visited 리스트를 초기화하도록 구현하였다.
13번째 줄부터는 전체 리스트를 반복하면서 뿌요가 존재할 경우 현재 뿌요를 저장하고 근접한 동일 뿌요들의 개수를 세서 4개 이상이라면 해당하는 뿌요들을 빈칸으로 초기화하였다.
이때 뿌요는 5종류가 있지만 변수에 현재 위치한 뿌요를 저장함으로써 종류에 대한 고려를 하지 않도록 했고 47번째 줄의 changed_col은 삭제된 뿌요가 존재하는 열을 추가하여 이후에 뿌요들을 정렬할 때 불필요한 탐색을 줄이는 방식으로 구현하였다.
53번째 줄에서 res+=1을 통해 카운트를 증가시키는데 문제에서 터질 수 있는 뿌요가 여러 그룹이라면 동시에 터지며 한 번의 연쇄가 추가되므로 다 터지고 난 뒤에 추가하도록 증가시키는 위치를 주의해야 한다.
터진 뿌요가 없다면 50번째 줄에서 반복문을 탈출하겠지만 터진 뿌요가 존재한다면 빈칸보다 위에 뿌요가 존재하지 않도록 정렬시킨 후 다시 반복문으로 돌아가면 된다.
그래프의 행을 기준으로 리스트 시작은 위, 끝은 바닥을 뜻하므로 끝부터 시작까지 역으로 오면서 뿌요를 최대한 리스트의 끝까지 정렬하는 것에 주의해야 한다.
해당 반복문이 끝나면 결과 변수인 res를 출력하면 끝이다.
결과 화면
그래프의 크기도 작고 특별한 알고리즘도 없이 흔한 그래프 이론으로 푸는 구현 문제였지만 구현 과정이 다소 길어지다 보니 충분히 헷갈릴 수도 있는 문제였다.
따라서 구현해야 하는 부분과 과정을 간략하게 주석으로 써놓고 차근차근 작성해 나가는 것이 실수를 방지하기 위해 중요한 것 같다.
