빠르게 성장하는 개발자

단순한 BFS 문제였다.처음에 생각을 잘못한 부분은 → NxN 에서 가장 큰 마른모는 N일때 발생한다고 생각했는데,N+1 일때 발생한다는 것이 key 였다. (그것때문에 49/50 개 pass 였다. 😿) 실제로 예시의 사진을 보면, 3x3 배열이 쏙 들어가는건 마름모가 k=4 일때임을 알 수 있다!앞으로 이런 디테일에 더 주의해서 문제를 풀어야 겠다.from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS 함수를 입력 def BFS(i, j, k): global house q = deque() q.append((i, j)) cnt = 1 if homes[i][j] == 1: house += 1 while cnt < k: for ..

1. 문제는 이쪽으로https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do 2. bfs처음에는 수업시간에 배운 다익스트라를 이용해서 풀이해 보려고 했지만,시간복잡도 때문인지 자꾸 시간초과가 나서 bfs를 변형한 방법으로 풀이하였다.from collections import deque di = [-1, 1, 0, 0] dj = [0, 0, -1, 1] def bfs(i, j): # s는 시작지점 q = deque() q.append((i,j)) money[i][j] = 0 # 시작지점의 가격 처리 while q: l = len(q) for _ in range(l): si, sj = q.popleft() for d in range(4): ..

🍨 제목은 귀엽지만 풀이과정은 사악했던 디저트 카페 문제를 데려왔다.https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWudfs 라는 것은 알겠는데 도저히 생각나지 않아서 약간 검색의 힘을 빌렸다. 1. 문제의 특징이동할 수 있는 방향의 순서가 정해져 있다. 직사각형을 이루려면 시계방향 혹은 반시계방향으로 돌면서 탐색이 이뤄저야 한다. 지금 내가 갈 수 있는 방향은 이전의 방향, 그리고 시계방향으로 돌아간 방향 2가지로 제한되어있다는 뜻이다.⇒ 함수의 인자에 방향을 나타내는(d)를 추가하여 기존에 오고 있는 방향으로 이동할 수 있다면 이동하고, 그렇지 않다면 그 다음 방향으로 탐색하는 코드를 ..

1. 완전 탐색의 기본기억하자 for 문을 돌려야 될 수도? → 언제나 for 문에 대한 열린 생각!!2. 기본적인 순열 & back-tracking 문제완전 탐색을 하면 ⇒ 시간초과 에러가 발생하였다!back-tracking을 통해서 중간까지의 합이 현재의 최솟값보다 크면(앞으로는 더해야 하므로 가망이 없기 때문에) 리턴하는 방식으로 가지치기를 진행해주었다.→ 이를 위해서 함수에 tmp 라는 인자를 가지고 다닌다.이 테크닉을 이후에 유용하게 잘 써먹고 있다!# 각 줄에 대해서 하나씩 선택하는 함수를 만든다 def select(i, k, tmp): global min_V if tmp > min_V: return if i == k: min_V = min(min_V, tmp) return else: for ..