Algorithm Problem

[python] 백준 - 18428. 감시 피하기

🤔문제 해결 S1 | 완전탐색 N의 범위가 매우 작으므로 완전탐색을 하는 문제이다. 벽을 세울 수 있는 빈 공간을 리스트로 구하고, 콤비네이션(3)을 한다. ( 벽을 3개 세워야 하므로 ) 벽을 세우면 감시를 시작한다. 선생님리스트도 만들어서 상하좌우 감시를 한다. 감시를 하던 도중 끝까지 가거나 벽을 만나면 해당 방향의 감시는 멈추고 학생을 만나면 감시에 성공하므로 그 벽은 다시 철거하고 다른 벽을 세운다. 선생님이 모든 방향에 대해서 감시에 실패할 때까지 반복한다. 💻소스 코드 from itertools import combinations as cb def watch(): for teacher in teacher_list: x, y = teacher # 상 nx, ny = x, y while nx >..

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라 정말 기본적인 다익스트라 문제! 따로 키 리스트를 설정하지 않아도 쉽게 풀 수 있다. 💻소스 코드 import sys import heapq input = sys.stdin.readline def dijkstra(s, e): pq = [] heapq.heappush(pq, (0, s)) # 출발지로 가는데 0원의 비용 visited = [0] * (N + 1) while pq: cost, w = heapq.heappop(pq) if w == e: return cost if visited[w]: continue visited[w] = 1 for newt_w, next_cost in adj[w]: if not visited[newt_w]: heapq.heappush(pq, (..

[python] 백준 - 2573. 빙산

🤔문제 해결 G4 | DFS, 구현 9개월전에 풀어봤던 문제였는데, 그 때는 시간초과를 해결하지 못해서 겨우 pypy로 제출해서 통과했다. 이번에 스터디를 하다보니 다시 풀게 돼서 효율적으로 코드를 작성해 python으로도 통과를 했다. 녹이는 빙산 찾기 2차원 배열 하나씩 돌기 -> 빙산을 따로 리스트로 만들어 두기 와 DFS 빙하 덩어리가 하나인지 여러개인지 판별 DFS -> 빙산 리스트의 길이와 녹일 때 선택한 빙산의 수의 차이로 바로 계산 💻소스 코드 import sys from _collections import defaultdict input = sys.stdin.readline def melt(): melting_area = {} # 녹일 곳 dx, dy = [-1, 1, 0, 0], [0,..

[python] 백준 - 2493. 탑

🤔문제 해결 G4 | 자료구조, 스택 문제를 푼 뒤 문제 유형을 봤는데 스택이라고 되어있었다. 하지만 내 풀이는 스택을 사용하지 않았다. 그런데 다른 사람보다 효율이 좋게 나왔다. 메모리는 평균인듯. 풀이 방법 1번탑부터 마지막탑 순으로 탐색했다. 현재탑과 이전탑과 같을 때 현재탑의 레이저 신호를 수신하는 탑은 이전탑의 레이저 신호를 수신하는 탑과 같다. 현재탑이 이전탑보다 낮을 때 현재탑의 레이저 신호를 수신하는 탑은 이전탑이다. 현재탑이 이전탑보다 높을 때 🐱‍🐉 이전탑의 레이저 신호를 수신한 탑으로 건너 뛴다. 그 탑을 위의 3가지 방법으로 체크한다. 아직 현재탑이 높은 상태라면 또 그 탑의 레이저 신호를 수신한 탑으로 건너 뛴다. 이렇게 3가지로 분리했다. 💻소스 코드 if __name__ == ..

[python] SWEA - 5986. 새샘이와 세 소수

🤔문제 해결 D3 | 소수, 완전탐색 💨 미리 소수를 구해놓는다. 💨 3중 포문으로 소수 3개를 더해서 N 이 나오면 True 💻소스 코드 prime = [] for i in range(2, 1000): for j in range(2, i): if i % j == 0: break else: prime.append(i) for tc in range(int(input())): N = int(input()) M = len(prime) cnt = 0 for i in range(M): if prime[i] > N: break for j in range(i, M): if prime[j] > N: break for k in range(j, M): if prime[k] > N: break if prime[i] + pr..

[python] 백준 - 13458. 시험 감독 (삼성 SW 역량 테스트 기출 문제)

🤔문제 해결 B2 | 수학 간단한 수학문제이다. ( 진짜 기출문제 맞나? ) 한 반에 감독관은 무조건 1명있어야한다. 한 반의 응시생이 감독관이 감시할 수 있는 응시생보다 많다면 부감독관을 투입한다. 감독관이 감시할 수 있는 응시생을 뺀 나머지 응시생을 부감독관들이 감시할 수 있게 한다. 💻소스 코드 import sys import math input = sys.stdin.readline if __name__ == '__main__': N = int(input()) # 시험장의 개수 A = list(map(int, input().split())) # 각 시험장의 응시자 수 B, C = map(int, input().split()) # B: 감독관이 감시할 수 있는 응시자 수, C: 부감독관이 감시할 수 ..