hibiscus

💻 문제 풀이 방법 1. 가능한 경우의 수(조합) 구하기 (재귀 + 백트래킹 사용) 2. 1의 정보를 바탕으로 그룹을 나누고 3. 나눈 그룹 각각 DFS로 방문할 수 있는지 체크, 방문하지 못하는 노드가 있을 경우 제외 처음에는 인접정보를 판단하면서 경우의 수를 구하기 위해, 그래프를 사용하며 방문표시를 했는데, 경우의 수에서 제외되는 경우가 있어 정답을 구할 수 없었다. 경우의 수는 역시 완전 탐색을 하는 게 확실하다... 아래 주소는 문제 풀면서 참고했던 반례들인데 유용했다! https://www.acmicpc.net/board/view/54133 반례들 # DFS def check_areas(check): for i in range(1, N+1): if check[i] == 0: start = i ..

SWEA 1795 인수의 생일파티와 유사한 문제이다. 각자의 집 -> 파티하는 집 -> 각자의 집으로 가는 최단경로를 구해야 한다. 한 점에서 여러 점 갈 때는 다익스트라를 한 번 돌리면 되지만, 여러 점에서 한 점으로 갈 때는 각 시작점마다 다익스트라를 돌려야 한다. 불필요하게 다익스트라로 구하는 것을 방지하고자 아예 경로를 여러 점에서 한점으로 가는 것 -> 한 점에서 여러 점을 방문하도록 그래프를 추가했다. 그래서 가는 방향 경로 GO, 오는 방향 경로 COME을 나눠서 다익스트라르 2번 돌려 구했다. from heapq import heappush, heappop INF = 0xffffffffffffffffff # 어떤 시작점에서 모든 정점까지의 최단거리 def dijkstra(start, gra..

처음에는 그래프로 만들어서 풀어봤는데, 그래프로 만들다 보니 가지 않는 정점까지 찾아서 다 돌리다보니 시간초과가 났다. 그래서 그냥 큐로 돌리고 방문표시를 통해 되돌아가는 일이 없게 하니 통과했다! from collections import deque def hamming(): visited[s] = 1 Q = deque() Q.append((s, str(s))) while Q: num, code = Q.popleft() if num == e : return code for i in range(1, N+1): cnt = 0 if visited[i]: continue for j in range(K): if arr[num][j] != arr[i][j]: cnt += 1 if cnt > 1: break if ..

N-queen 문제 처음에 N-Queen 문제를 봤을 땐 어떻게 접근해야할 지 몰랐고, 이해가 가는 풀이가 없었다. 그런데 아래 풀이를 통해 이해에 도움을 받아 정리해둔다!! 첫번째는 가로, 세로(i, cols) + 대각선(diagonal) 을 검사했다. 대각선의 경우에는 이전에 입력된 좌표의 값과 입력할 좌표의 값의 차이가 똑같다는 것을 이용해 푸는 것이다. 두번째는 4 * 4 배열일 경우, row와 col을 더하면 아래와 같이 나타나진다. 이런 경우, 대각선끼리 숫자가 같게 되므로 동일한 숫자를 가진 좌표들이 동일 대각선에 위치함을 이용해 푸는 것이다!! 0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6 하지만, 위의 경우는 오른쪽 대각선만 알 수 있으므로 왼쪽 대각선도 따로 구해야 한다. 왼..

다른 사람들 풀이 방법 참고해가며 푼 문제...!! 처음에는 DFS로 돌리면 찾을 수 있을 것 같아 DFS로 짰지만, 십자배열 모양은 DFS 특성상 찾아지지 않아 실패했다. 그래서 다른 분들의 접근방법을 참고해봤더니, 1) 5*5 배열의 각 자리수를 카운트해서 이를 인덱스를 활용함을 배웠다. 예를 들어, 왼쪽부터 0, 1, 2, 3, 4 .... 이라고 센다면 1,0은 5가 된다. 그리고 5를 5로 나누면 몫은 1, 나머지는 0 으로 5번째의 행과 열을 구할 수 있게 된다. 새로운 접근 방법이라 생각하지 못했는데, 다른 문제 풀때도 활용할 수 있을 것 같으므로 기억해놓자. 2) 백트래킹할 때 주의하기 코드 논리나 다른 거는 다 맞은 것 같은데 계속 실패가 나왔다. 크게 2가지로 코드를 나눴는데, 25개 ..

처음엔 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)

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 ..

처음엔 어떻게 접근해야 할까 고민했는데, 힌트?를 얻고나니 문제가 아주 간단해졌다. 🎈 해당 달까지의 최소비용을 계산해 사용한다 1월 2월 3월 4월 5월 6월 7월 8월 9월 10월 11월 12월 0 0 2 9 1 5 0 0 0 0 0 0 0 0 20 60 70 110 110 110 110 110 110 110 첫번째 행은 사용일수 두번째 행은 누적된 최소비용 T = int(input()) for tc in range(1, T+1): price = list(map(int, input().split())) plan = [0] + list(map(int, input().split())) expense = [0 for _ in range(13)] for i in range(1, 13): # 하루, 한달 비교..

DFS 문제가 점차 익숙해지나 했더니 조금의 심화가 나오면 헤매게 된다. 아직 배운지 얼마 안됐고, 요새 장고를 배우느라.. 바빠져서 알고리즘 문제를 풀지 못하고 있다ㅠ 조급해하지 않기...ㅎㅎ 1일 1알을 목표로..!! 이전에 풀었던 DFS의 문제는 좌표 한개로부터 다른 좌표로 가는 거라 고려해야할 사항이 많지 않았다. 그런데 등산로 문제는 일단 시작하는 좌표가 여러개이고 언제끝날지 모른다. 그래서 끝나는 지점에서 1) 몇번 왔는지 체크해줘야 하며, 또한, 등산로를 한번 허용하는 길이만큼 줄일 때 줄인 것을 반영하되, 다른 등산로들에게는 영향을 주지 않아야 한다. 그래서 등산로 길이를 줄여야하는 상황에서는 등산로 길이를 줄인다음 temp 변수를 사용해 원상복구 시켜주었다. 처음에 deepcopy를 사용..