Backjoon

[python] 백준 - 7569. 토마토

🤔문제 해결 1. BFS | silver1 2. 익은토마토(값이 1)를 찾아서 리스트에 담는다. 3. 3번의 리스트를 BFS를 실행한다. 4. 4번을 다 하고 나면 아직 익지 않은 토마토(0)가 있는 확인하고 있으면 -1을 답으로 출력 5. 없으면 가장 큰 값에서 -1한 값을 답으로 출력 💨 3차원 배열이라서 헷갈릴 수 있는 문제. 하지만 단순히 BFS로 풀면 된다. 💻소스 코드 from _collections import deque dx, dy, dz = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1] # 아래층 윗층 앞 뒤 좌 우 # BFS로 주변 토마토 익히기 def ripen(): while q: x, y, z = q.popleft()..

[python] 백준 - 10799. 쇠막대기

문제 해결 1. 스택을 활용한 문제. S3 2. '(' 가 나오면 막대기의 시작점이라 생각하고 stack 에 쌓는다. 3. ')' 이 나왔을 때 두가지의 경우 (1) 이전에 '(' 가 나온 경우: 쇠막대기가 아니라 레이저 이므로 잘라준다. (2) 이전에 ')' 가 나온 경우: 쇠막대기의 끝 부분 이다. 4. 레이저로 자른경우는 stack 에 쌓여있는 막대기만큼 count를 더해준다. 5. 쇠막대기의 끝부분이 나온경우 막대히 하나만큼 count를 더해준다. 🚗 소스 코드 bars = input() stack = [] cnt = 0 # '('를 막대기의 시작점으로 주고 '()' 이렇게 여는괄호와 닫는괄호가 연속으로 나오면 레이저로 취급한다. for i in range(len(bars)): if bars[i]..

[python] 백준 - 2941. 크로아티아 알파벳

문제 해결 1. 단순 인덱싱 문제?. S5 2. 크로아티아 알파벳을 배열로 만든다. 3. 크로아티아 알파벳은 두글자 혹은 세글자 이므로 (1) 두글자일 때 한번 (2) 세글자일 때 한번 체크 해준다. (3) (1), (2)가 크로아티아 알파벳이 아니라면 한글자만 알파벳으로 체크하고 다음을 진행한다. ⛅ 소스 코드 word = input() croatia = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] idx = 0 cnt = 0 while True: if word[idx:idx+2] in croatia: idx += 2 cnt += 1 elif word[idx:idx+3] in croatia: idx += 3 cnt += 1 else: idx += 1 cnt ..

[python] 백준 - 11399. ATM

문제 해결 1. 그리디 알고리즘. S3 2. 단순하게 정렬을 이용해서 문제를 해결했다. 3. 각각의 사람들이 기다리는 시간은 수학적으로 계산을 했다. ⛅ 생각보다 단순하고 쉬운 문제였다. 소스 코드 n = int(input()) people = list(map(int, input().split())) # 오름차순으로 정렬 people.sort() result = 0 # i번 째 사람이 인출 할 경우 i번 부터 i+n까지의 사람들은 *n시간 기다려야 한다. # 그러므로 n을 곱해서 더해준다. for i in range(len(people)): result += people[i] * (len(people) - i) print(result) 출처: BACKJOON ONLINE JUDGE 문제: https://..

[python] 백준 - 11047. 동전 0

문제 해결 1. 그리디 알고리즘. S1 2. 큰 동전부터 순차적으로 for문을 돌리며 (1) 목표값 k 보다 작은 동전이 나왔을 때 그 동전의 값을 뺄 수 있는 만큼 빼준다. ex) 45원이 남았을 때 10원짜리 동전이 나왔다면 계산을 통해 10원을 4번 빼주고 카운트를 4 올려준다. (2) 빼준 값만큼 k값을 줄여가며 동전을 0원으로 만든다. (3) 누적된 cnt 값을 출력해주면 끝 🌞 탐색알고리즘을 해결할 땐 시간을 최적화 하는게 중요한 것 같다. ❓처음 해결방법: 동전값을 찾았을 때 while문으로 동전을 하나씩 빼줬는데 시간 초과가 났다. ❓두번째 해결방법: k값이 0이 됐음에도 불구하고 나머지 for문을 돈다고 생각하여 break문을 추가했다. 이것도 시간 초과. 사실 별로 도움이 안된거 같다...

[python] 백준 - 1697. 숨바꼭질

문제 해결 1. BFS 기본 문제. S1 2. 주어진 범위 100,000까지의 배열을 만든다. 3. BFS를 활용해 현재위치와 다음위치를 배열에 넣고 while문을 돌린다 (1) 각 지점에 도달하기 까지의 최소 시간으로 업데이트 해준다. (2) 이렇게 코드를 짜는 경우 시간초과가 생길 수 있으므로 deque()를 사용하고 (3) 한번도 방문한 적이 없거나, 최소시간으로 방문할 때만 다음 지점으로 나아갈 수 있게 한다. 4. 현재 위치가 목표 지점에 도달하면 break로 while문을 빠져나와 답을 출력한다. 🌞 처음에 범위를 100001까지 잡았더니 인덱스가 마지막이 될 경우에 런타임에러가 발생한다. 그래서 100002로 바꿔줬더니 해결했다. 재귀로 풀어 봤지만 maximum recursion depth..