![]()
https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답코드 # 2023-06-30 # 2023-07-12 # 복습 횟수:1, 00:30:00, 복습필요:*(세 달 뒤 쯤 복습하면 될듯 - 그때도 맞으면 끝) def solution(targets: list): answer = 0 targets.sort(key=lambda x: x[1]) end = 0 for target in targets: if target[0] >= end: answer +=..
![]()
문제 https://www.acmicpc.net/submit/1504/61065431 로그인 www.acmicpc.net Algorithm 다익스트라 알고리즘을 이용한다. 시작점이 정점 1인 경우에서 다익스트라 알고리즘을 수행했을 때와 시작점이 각각 정점 v_1, v_2인 경우에서 다익스트라 알고리즘을 수행했을 때의 결괏값 3개를 구한다. 이 결괏값을 각각 d_0, d_1, d_2이라 하면 이 결괏값들은 모두 리스트이다. 경로가 "정점 1->정점 v_1->정점 v_2->정점 N"일 때와 "정점 1->정점 v_2->정점 v_1->정점 N"일 때 중에서 길이가 더 짧은 경로의 길이를 출력한다. 다시 말해 d_{k-1}의 i번째 원소는(1
![]()
풀이 A -> B로 가는데 드는 최소비용을 구하는 문제이다 각 버스의 출발 도시와 도착 도시, 버스 비용을 그래프에 추가한다. 같은 출발 도시에서 여러 개의 버스가 있을 수 있으므로, 출발 도시를 인덱스로 하는 벡터에 도착 도시와 비용을 추가한다. 우선순위 큐를 사용하여 탐색할 도시와 그 도시까지의 비용을 저장하고, 시작 도시의 거리는 0으로 설정하고 큐에 추가한다. 큐에서 도시를 하나씩 꺼내면서 인접한 도시들을 탐색한다. 구간 출발점에서 도착점까지의 최소 비용인 distance[B]를 출력한다. 코드 #include #include #include #include using namespace std; const int INF = numeric_limits::max(); struct Edge { int ..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해결 1. n번의 마을에 사는 학생 1명이 x번 마을로 가는 최단 경로 값을 구해야한다. 즉, 1-2-3-4-...-n번 마을에 해당하는 학생이 x 마을에 가는 최단경로의 모든 값을 구해야한다. 2. n번 마을에서 x번 마을로 갔다가 돌아오는 왕복값을 계산해주어야 한다. 이때 도로가 단방향이므로 갈 때의 최단 경로와 돌아올 때의 최단 경로는 다르기 때문에 각각에..
![]()
23033번: 집에 빨리 가고 싶어! (acmicpc.net) 23033번: 집에 빨리 가고 싶어! 첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요 www.acmicpc.net 코드 해석 역의 수 N, 노선 M을 입력 받음 a,b,t,w를 입력 받고 graph의 a행에 (b, t, w) 저장 시작 역부터 해당 역까지의 최소 시간을 저장하는 dist 리스트 생성 생성 직후 출발역에서는 0, 이외의 역에서는 INF(무한) 최소 시간이 작은 역부터 처리하기 위해 우선순위 큐인 q 사용 생성 직후 출발역인 0에서는 [0,1]..
![]()
https://www.acmicpc.net/problem/14497 문제 분석 난이도 골드 4 분류 그래프, 0-1 BFS 또는 다익스트라 문제 문제 풀이 풀이 주난이가 점프를 뛸 때마다 주난이와 이어진 0 주변의 1들이 사라진다고 생각하면 된다. 이것만 보고는 백준의 다른 너비우선탐색 문제들과 했갈릴 수 있지만 더 효율적으로 푸는 방법은 다익스트라이다. 그 이유는 0으로 된 부분을 이동하는데 가중치가 0이고, 1을 0으로 바꾸는데 가중치가 1이 들어가는 그래프로 생각하고 풀어줄 수 있기 때문이다. 위의 설명처럼 가중치가 0또는 1만 존재하기 때문에 0-1 BFS로도 해결이 가능한 문제이다. 다익스트라는 O(ElogV)의 시간복잡도, 0-1 BFS는 O(E+V)의 시간복잡도를 갖는다. 소스코드 다익스트라..
문제링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 코드 import sys import heapq input = sys.stdin.readline def dijkstra(x,y): q = [] distance[x][y] = 0 heapq.heappush(q,(0,x,y)) while q: dist,x,y = heapq.heappop(q) for i in range(4): nx = x + dx[i] ny = y + d..
https://www.acmicpc.net/problem/2644 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람..
![]()
1. 문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2. 코드 n = int(input()) # 노드 개수 size = int(input()) # n번 노드에 연결된 노드 graph = [[] for _ in range(n+1)] # 방문한 노드는 1, 방문하지 않은 노드는 0 visited =[0]*(n+1) for i in range(size): a,b = map(int,input().split()) # 그래프 넣어주기 ~ graph[a]+=[b] graph[b]+=[a] def dfs(v): # 방문한..
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net Algorithm 1. 배열 A를 입력받을 때 상하좌우를 탐색하기 편하게 하기 위해 가장자리의 바깥부분에 1을 추가한다. 2. 선언된 A 중에서 A[i][j] == 0인 (i, j)에 대한 집합 Z를 생성한다. 3. A를 복사한 B에 대해 Z 중 3개를 골라 그 (i, j)에 해당하는 B의 값을 1로 바꾼다. 4. dfs로 상하좌우에 0인 부분을 찾아서 그 부분을 2로 바꿔가며 2로 바뀐 0의 개수 x를..
문제링크 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 코드 from collections import deque from copy import deepcopy def bfs_water(graph,water_idx): q = deque() for x,y in water_idx: q.append((x,y)) time[x][y] = 0 while q: x,y = q.popleft() for i in range(4): nx = x + dx[i] ny = y +..
![]()
풀이 각 정점에서 연결된 정점들을 번호순으로 처리하기 위해 정렬한다. DFS 함수에서는 현재 정점을 방문하고, 방문했다는 표시를 한 뒤, 현재 정점에 연결된 정점들을 재귀적으로 방문한다. BFS 탐색은 큐를 이용하여 구현한다. DFS 함수와 BFS 함수에서 visited 배열을 공유하지 않도록 주의하면서 구현하면 된다. 코드 #include #include #include #include using namespace std; vector graph[1001]; bool visited[1001]; void dfs(int node) { visited[node] = true; cout m >> v; for(int i = 0; i > a >> b; graph[a]..
