hibiscus

처음엔 BFS를 사용하여 A에서 B로 가는 최소횟수를 구했다. 그런데 찾아보니 이런 경우는 B에서 A로 가는 것을 구하면 훨씬 빠르다!! from collections import deque def BFS(): ans = 1 while Q: size = len(Q) for i in range(size): num = Q.popleft() if num > b : continue if num == b: return ans if num * 2 a: ans += 1 if b % 10 == 1: b //= 10 elif b % 2 == 0: b //= 2 else: print(-1) break else: if b < a: print(-1) else: print(ans)

처음엔 DFS로 접근할 수 있을 것 같아 DFS로 풀었는데, 시간이 너무 오래걸려 시간초과가 떴다. 최단거리엔 역시 BFS이구나를 깨닫고 다 지우고 BFS로 접근했다. 아래처럼 범위를 설정하지 않으면 visited때문에 런타임에러가 뜬다. " if num > 100000 or 0 > num: continue " from collections import deque def BFS(n): cnt = 0 Q.append(n) while Q: for _ in range(len(Q)): num = Q.popleft() if num == k: return cnt if num > 100000 or 0 > num: continue if visited[num] == 1: continue visited[num] = 1 i..

🎈 숫자를 문자열로 바꾸지 않고 정렬해 오류가 떴다. 1, 2, 3, 4 정렬할 때는 문자나 숫자나 차이가 없지만, 100, 10, 110 같은 경우는 문자와 숫자의 정렬이 달라짐을 간과했었다. 주로 list를 사용해와서 이번에도 set을 사용할때 list로 넣어준다음 중복제거를 위해 set을 사용했는데, 'unhashable type' 이라는 에러가 발생했다. 찾아보니 list 말고 tuple에는 해시 값이 있어 tuple을 사용하니 잘 통과됐다. 정렬하고 -> 중복값제거하고 -> 다시 정렬하는게 비효율적이라고 느껴져 다른 풀이를 찾아봤었다. t라는 값을 두어 이전의 값을 저장한 뒤 새로운 조합을 만들때 값을 비교하는 풀이가 신박했다. from sys import stdin n, m = map(int,..

중복되지 않는 조합을 찾는 문제라 재귀를 사용하여 풀었다. 자음과 모음의 개수도 암호를 만드는 데 필요한 조건이라 추가적으로 자음과 모음의 개수도 함께 인자로 전달했다! 조합이 익숙해지니, 이런 문제는 오히려 고마워졌다..ㅎㅎ import sys # 중복되지 않는 조합, 정렬하기 def make_password(idx, start, vowels, consonants): if idx == l: if vowels >= 1 and consonants >= 2: print("".join(map(str, password))) return for i in range(start, c): password[idx] = chars[i] if chars[i] in ['a', 'e', 'i', 'o', 'u']: vowels..

육지 "L"인 지점을 찾아서 BFS를 사용하여 최장 거리를 저장하는 방식으로 풀었다. 처음에는 모든 L의 지점을 다 찾아서 돌리니 시간초과가 걸려 시작지점을 줄이는 방법이 없을까 고민을 했다. 생각해보니 L들에게 둘러쌓여 있는 지점은 최장거리가 될 수 없다는 것을 깨달아, 인접한 L이 2개 이하일 때만 시작지점을 넣어서 돌리니 통과했다. 이 때 인접한 L이 1이하라고 조건을 바꾸면 안될까? 라는 생각도 했었는데 W가 없는 지도일 경우, L의 인접지점은 최소 2가 된다. 반례 3 2 LL LL LL import sys from collections import deque n, m = map(int, (sys.stdin.readline().split())) map = [] ans = 0 for _ in ra..

첫번째는 풀이는 단계를 나눠 1) 높이의 최댓값, 최솟값을 구하고, 2) (최솟값부터 최댓값까지 하나씩 대입하여) 회색 영역을 찾고, 3) 잠기지 않는 부분을 count 해 최댓값을 저장 이렇게 풀었다. 그런데 다 풀고 나서 리팩토링하기 위해 다시 보니 굳이 회색영역을 찾지 않아도 됨을 알게 되었다. 그래서 높이값과 방문표시를 사용하여 회색영역을 찾는 부분을 없앴더니 조금 속도가 빨라졌다. import sys N = int(sys.stdin.readline()) areas = [] safe = 0 gray_area = [[0]* N for _ in range(N)] safe_area = [[0]* N for _ in range(N)] delta = [(1, 0), (-1, 0), (0, 1), (0, -..

이 문제는 좌표로 되어 있었서 조금 헷갈렸다. 그렇지만 영역을 구하는 문제이기 때문에 직사각형이 상하나 좌우로 뒤집어도 영역의 갯수는 변하지 않기 때문에 다루기 편하게 상하로 뒤집은 다음 사용해서 영역을 구했다. M, N, K = map(int, input().split()) arr = [[0] * N for i in range(M)] areas = [] delta = [(1, 0), (-1, 0), (0, 1), (0, -1)] def DFS(i, j): stack = [(i, j)] arr[i][j] = 1 cnt = 1 while stack: r, c = stack.pop() for dt in range(4): nr = r + delta[dt][0] nc = c + delta[dt][1] if 0

3차원 배열로 풀어야 했고, 방향은 위, 아래 / 앞, 뒤 / 왼쪽, 오른쪽 해서 총 6방향이었다. 기존에 2차원 배열과 4방향을 사용해서 푼 걸 응용해서 풀었더니 어렵지 않게 풀었다. 1) 익은 토마토를 찾아서 Q 에 넣어주고 2) Q를 사용하여 인접한 토마토가 다 익는데 걸리는 날을 측정해 답을 구함. 3) 안익은 토마토가 있을 경우, 답을 -1로 바꿈. 처음부터 안익은 토마토가 없는 경우가 존재하는데, 아래 코드에서는 이를 따로 처리해주지 않았다. 날짜를 셀때 -1로 시작하기에 안익은 토마토가 없는 경우에는 기존의 있던 토마토가 한번씩 pop되서 돌아서 cnt 값이 0으로 바뀌기 때문이다. from collections import deque def find_riped_tomatoes(): for ..

주어진 배열이 2차배열이라 check도 2차배열로 사용하려 했는데, idx와 check의 r행이 같이 가므로 check의 인덱스를 idx로 바꿀 수 있어 더 간편하게 코드를 짤 수 있었다. def get_max(idx, cur_sum): global max_sum if idx == 11: if cur_sum > max_sum: max_sum = cur_sum return for j in range(11): if check[j]: continue if sportsman[idx][j]: check[j] = 1 get_max(idx+1, cur_sum+sportsman[idx][j]) check[j] = 0 T = int(input()) for _ in range(T): sportsman = [] check ..

6개의 로또 숫자를 뽑는 것이므로 조합이고, 중복되는 값이 있으면 안된다. 그래서 start로 범위를 이전보다 다음에서 시작하게 만들어 풀었다. def lotto(idx, start): if idx == 6: print(" ".join(select)) return for i in range(start, k): select[idx] = S[i] lotto(idx+1, i+1) select = [0] * 6 while True: nums = list(input().split()) k, S = int(nums[0]), nums[1:] if k == 0: break lotto(0, 0) print() 풀다보니 이제는 자동적으로 if idx == M : 이런식으로 코드를 작성하게 된다.. 조합과 순열은 결국 많이..