본문 바로가기

전체 글214

[백준] 2437 저울 (Python/파이썬) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 그리디 문제로 정답코드를 보면 매우 단순한데 아이디어를 떠올리기까지가 매우 힘들다. 핵심 아이디어는 다음과 같다. 현재까지 측정 가능한 무게의 최댓값을 ans라고 하면 (1 - ans)의 값들을 측정할 수 있다. 오름차순으로 정렬된 무게추들 중에서 하나의 무게추(weight)을 선택한다. weight ans + 1라면 ans + 1의 값은 측정 불가능하므로 해당 값이 정답이 된다. 단 1, 1, 1, 1 혹.. 2022. 10. 3.

[백준] 20056 마법사 상어와 파이어볼 (Python/파이썬) https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 특별한 알고리즘을 필요로 하지 않는 구현 문제이다. 어떤 자료구조형을 어떻게 사용해서 파이어볼의 정보와 위치 등을 나타낼 것인가가 생각하기 좀 까다롭다 구현해야할 요소는 크게 파이어볼의 이동 / 파이어볼의 병합과 분산이다. 먼저 파이어볼의 이동이다. 파이어어볼의 이동은 리스트에 담은 파이어볼의 정보를 하나씩 꺼내서 빈 리스트를 원소로 가진 N x N 배열(리.. 2022. 10. 3.

[백준] 14621 나만 안되는 연애 (Python/파이썬) https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 1. 기본적인 MST 문제이다. 2. 대학교 남초/여초 여부를 딕셔너리 형태로 저장해서 크루스칼 알고리즘에서 다음 간선 선택 시 다른 종류의 대학교일 경우만 선택하도록 했다. 3. 그 외에는 조건을 만족하는 mst가 없을 경우 -1을 출력하도록 해야된다. import sys, os, io, atexit input = lambda: sys.stdin.read.. 2022. 10. 2.

[백준] 16724 피리 부는 사나이 (Python/파이썬) https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 0. DFS / BFS (+ 유니온파인드) 문제이다. 유니온 파인드에 괄호를 친 이유는 아래 설명하겠지만 유니온 파인드를 안 쓰고 bfs만으로 풀이 하는 방법도 있기 때문이다. (아래 설명) 1. 유니온 파인드 풀이 주어진 그래프에서 dfs를 통해서 사이클을 확인하고 해당 사이클을 하나의 safezone 그룹으로 묶는 과정을 반복해야하는데 이 과정에서 유니온 파.. 2022. 10. 2.

[백준] 2146 다리 만들기 (Python/파이썬) https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 기본 접근은 각각의 섬에 다른 번호를 부여하고 각각의 섬에 대해서 bfs를 통해서 다리의 최소 길이를 구하는 것이다. 2. 다만 메모리초과가 나기 쉬워서 visited배열을 잘 활용해야 한다. 나 같은 경우는 다리 건설하는 bfs 함수 안에 visited배열을 하나 만들고, 섬의 번호에 대한 visited배열을 하나 더 만들어서 한 번 탐색한 섬에 대해서 다시 탐색하지 않도록 했다. 3. 다리를 .. 2022. 10. 1.

[알고리즘] 다익스트라 (Dijkstra) 다익스트라 (Dijkstra) 다익스트라 알고리즘이란 ✔ 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 다익스트라 알고리즘의 원리 * P[a][b]: a와 b 사이의 거리 출발점으로부터 최단거리를 저장할 배열 distance[v]을 만들고 출발 노드는 0, 나머지 노드들은 충분히 큰 값으로 초기화 한다. 현재 노드 Current를 출발 노드의 번호로 설정한다. Current로부터 갈 수 있는 임의의 노드 Next에 대해 distance[Current] + P[Current][Next](A를 거쳐서 B로 가는 최단거리)와 distance[Next](현재까지 알려진 B의 최단 거리)의 값을 비교해서 짧은 값(짧은 경로)로 갱신한다. Current의 모든 이웃노드 N.. 2022. 10. 1.

이전 1 ··· 30 31 32 33 34 35 36 다음

티스토리툴바