BOJ

[문제] https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net [풀이] 그리디 문제! 최종 결과는 신경쓰지 않고 일단 현재 가장 이익이 될 것을 선택한다. 여기서 현재 가장 이익이 될 것 = 거스름돈이 제일 작을 것 시간이 긴 버튼을 누르는 게 이익이 되기 때문에 5분부터 차례대로 답을 찾아간다. [코드] import sys T = int(sys.stdin.readline()) A, B, C = 300, 60, 10 if T % C != 0..

[문제] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [풀이] 지역의 높이 정보를 set 으로 모아 어떤 높이의 건물이 있는지 비가 얼마나 오는 지 모르기 때문에 0부터 건물 최고 높이까지 비를 내리게 한다. 건물의 높이는 지역의 높이 정보를 set 으로 모아 확인한다. 건물 높이보가 현재 내리는 비 높이보다 크고 아직 그 건물을 방문한 적이 없으면 count 를 하나 올리고 bfs 함수로 들어간다. 현재 기준이 되는 건물의 상하좌우 에 있는 건물..

[문제] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [풀이] 2022.08.25 - [문제풀이/BOJ] - [Python] BOJ/백준 2458번 키 순서 [Python] BOJ/백준 2458번 키 순서 [문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명..

[문제] https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [풀이] 2022.08.23 - [문제풀이/BOJ] - [Python] BOJ/백준 11404번 플로이드 [Python] BOJ/백준 11404번 플로이드 [문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m..

[문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [풀이] 두 학생 a, b를 a가 b를 향하는 방향 그래프로 나타내면 키의 크고 작음을 표시할 수 있다. 플로이드-와샬 알고리즘을 통해 한 정점에서부터 모든 정점으로의 연결 상태를 알아내어 그래프를 갱신한다. 왼쪽 리스트는 예제 2번 문제를 플로이드-와샬 알고리즘을 통해 그래프를 갱신한 상태이다. 위 그림의 1번 노드는 다른 정점을 통해 모든 정점으로 연결될 수 있기 때문에 리스트[0] 은..

[문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net [풀이] 문제에도 플로이드라고 나왔지만 모든 정점에서 다른 모든 정점으로의 최단 경로를 구해야 하기 때문에 플로이드 와샬로 풀었다. + 처음에는 INF 로 안풀고 문제에 비용의 최댓값이 100,000 이라 나와있어 리스트를 100001로 초기화하고 풀었는데 틀렸다.. 이유는 모르겠음 그냥 앞으로 저런 문제 나오면 int(1e9)로 풀어야지 [코드] from sys import stdin ..

[문제] https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 그래프 최단 거리 문제 다익스트라 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 플로이드 와샬 거쳐가는 정점을 하나씩 다 설정을 하여 해당 정점을 기준으로 최단 거리를 구하도록 구성 → 모든 쌍 간의 최단 거리를 구할 수 있음 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘  [코드] import sys N = int(sys.stdin.readline()) graph = ..

[문제] https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [풀이] 우와 탐욕법인가 했는데.. 이게··· BFS 문제라니.. 충격과 공포 그자체였음 그렇지만!.... 탐색 문제인걸 알기만 하면 문제 푸는건 쉽다 하하 사다리와 뱀 dictionary를 만들어 key와 value로 저장한다. deque로 선언한 큐에 처음 출발지인 1을 넣는다. 주사위 숫자인 1부터 6까지 반복문을 돈다. 이동할 칸이 1..

[문제] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [풀이] 딱봐도 탐색문제..~ 내가 계속 BFS로 풀어서 DFS로도 한번 풀어봤다 계속 까먹어서 적어두는데 BFS는 deque를 이용해 풀고 DFS는 재귀 호출을 이용해 푼다. 공통점은 둘 다 visited를 이용해서 해당 칸 방문 여부를 검사했다. [BFS 코드] import sys from collections import deque n = int(sys.stdin.readli..