0과 1의 쉼터

문제https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  풀이그래프의 간선이 2차원 배열로 주어졌을 때, 독립된 정점 그룹의 수를 세는 문제다.정점의 수는 최대 200이므로 완전 탐색을 하기에 시간이 충분하다.BFS를 하며 연결된 정점들을 전부 탐색 후 그룹의 수를 증가시키는 방식으로 해결했다.def solution(n, computers): visited = [False] * n cnt = 0 for i in range(n): if n..

문제https://leetcode.com/problems/rising-temperature/description/풀이이전 날짜보다 현재 날짜의 temperature 가 더 높아진 행의 id 를 출력하는 문제다.결과에는 id만 나와야 하므로, LAG 대신 조건을 만족하는 행을 조인해주는 방식으로 해결했다.또한, 이전 날짜와 현재 날짜의 차이는 하루여야 하므로 DATEDIFF의 결과가 1인 행에 대해서만 계산했다.SELECT w1.id FROM Weather w1 JOIN Weather w2 ON DATEDIFF(w1.recordDate, w2.recordDate) = 1 and w1.temperature > w2.temperature;소스코드https://github.co..

문제https://www.acmicpc.net/problem/1405 풀이로봇이 확률에 따라 상하좌우로 움직인다고 한다.이동 가능한 모든 경로에 대해, 방문하지 않은 곳을 방문하는 비율을 구하는 문제로 재해석할 수 있다.주어진 상하좌우로 움직이는 확률을 방향 좌표와 함께 묶어주자.문제에서 주어진 N은 14이기 때문에 -14 ~ 14를 고려해 보드의 크기는 29면 충분하다.if __name__ == '__main__': visited = [[False] * 29 for _ in range(29)] # Input N, *D = map(int, input().split()) D = [(*point, d * 0.01) for point, d in zip([(0, 1), (0, -1)..

문제https://www.acmicpc.net/problem/2178 풀이주어진 보드의 (0, 0)에서 (N - 1, M - 1)에 도달하기 위해 움직인 최소 횟수를 구하는 문제다.BFS로 탐색을 진행했다.if __name__ == '__main__': # Input N, M = map(int, input().split()) board = [[*map(int, input().rstrip())] for _ in range(N)] # Solve & Output print(bfs(N - 1, M - 1))큐에는 현재 위치 (x, y)를 담았으며, 따로 방문 횟수를 기록해도 되지만 주어진 board를 활용했다.빈 공간은 1로, 이동하면서 기존 위치의 값 + 1으로 채웠다.이미 방문한 ..

문제https://www.acmicpc.net/problem/1697 풀이0 이상 10만 이하의 N과 K에 대해 다음 연산을 통해 N이 K가 되는 가장 빠른 연산 횟수를 구하는 문제다.BFS를 통해 (연산 결과, 연산 횟수) 쌍을 큐에 담아줬다.from collections import dequefrom sys import stdininput = stdin.readlinedef bfs(start, end): queue = deque([(start, 0)]) visited = [False] * 100_001 visited[start] = True요소를 하나씩 제거하며 연산 결과가 K가 될 때 까지 반복했으며,새로운 N은 0 ~ 100,000을 벗어나지 않고, 계산해본 적 없는 수에 대해서만..