hibiscus

다익스트라로 풀었음! 각자의 집에서 -> X번 집(생일파티집) => 각자의 집 X번 -> 각자의 집은 다익스트라 한 번 돌리면 되지만, 각자의 집에서 X번집의 최단거리들을 구하려면 여러번 돌아야 한다. 그래서 그래프를 만들때 각자의 집 -> X번 집을 쉽게 구하기 위해서 X 번집을 기준으로 두고, 각자의 집으로 가는 (반대방향) 으로 그래프를 만들어 다익스트를 2번만 돌리면 되도록 했다! from collections import deque INF = int(1e9) def dijkstra(start, graph): D = [INF] * (n + 1) D[start] = 0 Q = deque() Q.append(start) while Q: node = Q.popleft() for n_node, w in ..

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 하지만, 위의 경우는 오른쪽 대각선만 알 수 있으므로 왼쪽 대각선도 따로 구해야 한다. 왼..

처음엔 어떻게 접근해야 할까 고민했는데, 힌트?를 얻고나니 문제가 아주 간단해졌다. 🎈 해당 달까지의 최소비용을 계산해 사용한다 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를 사용..

SWEA 1216. 회문 2 def find_palindrome(N, arr): ans = '' for n in range(100): # 돌아가는 갯수 늘리기 for s in range(n+1): # 탐색 위치 바꾸기 for r in range(N): # 한줄씩 바꾸기 flag = True M = N - n #가로 for idx1 in range(M // 2): # 앞뒤 비교하는것 start = s + idx1 end = s + M - 1 - idx1 if arr[r][start] != arr[r][end]: flag = False break if flag: return len(arr[r][s:s + M]) #세로 flag = True for idx2 in range(M // 2): # 앞뒤 비교하는것 ..

SWEA 1223 계산기2 스택을 이용하여 계산기 기능을 구현하는 것이다. 처음 후위표기식을 볼땐 이게 뭐야;; 싶었는데 보면 볼수록 어떻게 이런 생각을 했나 싶다..ㅎㅎ 그리고 그냥 연산하면 되는데 왜 굳이 할까? 라는 의문이 들어 찾아보니 괄호 없이 연산자의 우선 순위를 판단할 수 있다는 장점을 가져 소프트웨어로 구현되는 계산기들은 후위표기법을 사용한다고 한다. 🎈 3가지로 나눠서 구현했다. 1) 우선순위 판별 2) 중위표기식 -> 후위표기식 3) 후위표기식을 계산 # 우선순위 def priority(char): if char == '*': return 3 if char == '+': return 2 else: return 1 # 중위 -> 후위 def make_postfix(): stack = []..

SWEA 4861 회문 🎮 문제 접근 방법 - N-M+1 만큼 돌면서 한줄씩 건너뛰며 가로에서 먼저 패턴을 찾고 없으면 세로에서 패턴을 찾는다. - 회문 1개만 찾으면 되니, 회문을 찾으면 BREAK 🎈 문자열을 뒤집는 4가지 방법 - 거꾸로 읽어오는 것 - swap해서 가져오는 것 - reverse 함수를 사용하는 것 - slicing 해서 거꾸로 가져오는것 이 문제는 뒤집진 않아도 되서 swap해서 값을 가져오진 않았지만, swap을 응요한 앞과 뒤를 비교하는 방법을 활용했습니다. 그리고 flag 말고도, for else 혹은 elif 를 활용해서 작성 가능합니다! T = int(input()) for tc in range(1, T+1): N, M = map(int, input().split()) a..

SWEA 4836 문제의 저작권은 SW Expert Academy에 있습니다 T = int(input()) for tc in range(1, T+1): N = int(input()) arr = [[0] * 10 for i in range(10)] for i in range(N): sketch = list(map(int, input().split())) for i in range(sketch[0], sketch[2]+1): for j in range(sketch[1], sketch[3]+1): arr[i][j] += sketch[4] count = 0 for i in range(10): for j in range(10): if arr[i][j] == 3: count += 1 print(f'#{tc} {co..

SWEA 문제 4839. 이진탐색 문제의 저작권은 SW Expert Academy에 있습니다. 🎈 이진탐색은 범위의 중간값과 비교하며 범위를 줄여나가는 탐색으로 for문을 돌면서 하나씩 찾는 것보다 훨씬 빠릅니다! 시간복잡도는 log N입니다. 다만, 이진탐색은 정렬이 되어 있어야 가능하단 것!! 정렬되지 않은 경우에는 정렬하는 시간+ 이진탐색 시간 이렇게 함께 생각해줘야 합니다! # 이진탐색 구현 함수 def binary_search(page, P): start = 1 end = page middle = 0 count = 1 while P != middle: middle = int((start + end) / 2) if middle > P: end = middle else: start = middle ..

💻 문제 풀이 접근 방법 1) 앞뒤에 2개씩 가지는 새로운 리스트를 만들고 2) 리스트 정렬시키고 3) 리스트의 맨 뒤의 숫자가 같은경우(즉, 해당 빌딩이 최댓값인 경우)에 그보다 작은 값 중의 최대인 값(list[-2])을 빼면 남은 세대들은 조망권을 가진다. 🎈 정렬시키지 않고 최댓값, 최솟값을 바로 추출하는 풀이로 하면 더 빠릅니다! 저는 강의시간에 배운 버블 정렬을 활용하여 풀어보았습니다:) for tc in range(1, 11): num = input() arr = list(map(int, input().split())) houses = [] ans = 0 for i in range(2, len(arr)-2): houses = [] houses = arr[i-2:i+3] # 정렬시키는 반복문 ..