•알고리즘(Algorithm )/알고리즘 팁

[알고리즘] BFS를 이용하여 최단거리를 출력해야할때 with predecesso(프로시져)

# 발단 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS문제는 간선에 가중치가 없는 경우 그래프적으로 해석하면 최단거리를 구할 수 있다. 왜냐하면 노드의 방문을 큐로 관리하기 때문에 넓이우선탐색을 하고 이 넓이는 하나의 turn이 될 수 있다. 그 turn에서 목표지점을 발견했다면 그것이 최단거리이다. 몇몇 BFS문제를 풀었을때, 이러한 최단거리까지 총 몇번의 거쳐서 가는가를 구하는 응용 문제들( ex. 며칠이 걸리나? like 토마토 )은 프로시져를 활용하여 풀었다. 즉 큐에 방문할 당시..

[알고리즘] queue 보다는 deque를 사용하자

# 발단 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [백준7569] 토마토라는 문제를 풀었다. BFS를 이용하여 탐색과 동시에 가장 빠르게 탐색을 완료하는 시점(단계)를 구하는 문제였다. 3차원이 주어진다는 것 외에는 그렇게 특별한 문제가 아니였기에, 매번 풀던방법과 같이 queue(큐)를 사용하여 문제를 풀었다. DFS는 스택, BFS는 큐를 사용하는 것이 나에게 있어서는 정석과도 같은 방법이었기 때문이다. 그런데 시간초과가 발생했다. 파이썬은 그럴 수 있기에 PyPy로 제출해봤..

[백준풀때 유용한 파이썬 팁] itertools을 이용해 조합(combinations)과 순열(permutations), 중복순열(product) 사용하기

# 발단 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수문제이다. dp나 재귀를 이용해서 풀 수 있을 테지만, 파이썬 itertools는 조합과 순열기능을 지원해준다. # 사용법 from itertools import combinations, permutations arr = ["A","B","C"] # 조합 combi = combinations(arr, 2) # 순열 permu = permutations(arr,2) (리스트, 뽑을 개수)와 같이 지정해준다면 쉽게 사용할 수 있다. ## 출력 출력을 하고 싶다면 list로 이터레이터를 변환시켜준다. print(f"조합 : {l..

[백준풀때 유용한 파이썬 팁] zfill(), rjust(), ljust() 이용하여 빈 곳을 0으로 채우기

# 발단 [백준 10250번 - ACM호텔] 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 위 문제를 파이썬을 활용해서 풀고 있었다. 아주 옛날에 C++를 이용해서 풀었던 기억이 있다. 문제의 풀이는 어렵지 않다. 그러나 최종 출력값은 방의 호수를 나타내는데 이걸 처리하는게 꽤 까다로웠던 기억이 있다. 이 문제를 풀다보면 층수 4, 호수 2를 얻어 최종 방 호수가 402의 출력을 만들어야 하는 순간이 온다. 0을 끼워 넣어야 한다는 것이다. 막상 코드로 옮기려니 꽤 번거롭다. 그러나 파이썬의 내장..