'🧩 Problem Solving/[백준]' 카테고리의 글 목록 (8 Page)

[백준] 11404 플로이드 (python 파이썬)

2022.06.18

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-와샬 알고리즘을 쓰는 문제. 모든 노드 쌍의 최단 거리를 구할 수 있다. 시간 복잡도는 O(N^3) 풀이과정 cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, N + 1): if i == j: cost[i][j] = 0 for i in range(m): a..

🧩 Problem Solving/[백준]

[백준] 17070 파이프 옮기기 1 (python 파이썬)

2022.06.16

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이썬이라 억까당함. 난이도는 낮지만 시간 초과로 고생했다. 맨 처음 bfs로 풀었을때 시간 초과가 채점 70%에서 자꾸 걸리길래 방법이 틀린 줄 알았다. 아마 파이썬이 아니였으면 맞았을 거 같다. from collections import deque import sys count = 0 N = int(input()) home = [] for _ in range(N): h..

🧩 Problem Solving/[백준]

[백준] 10026 적록색약(python 파이썬)

2022.06.15

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 구역의 수를 찾는 문제 근데 이제 색약을 곁들인 dfs나 bfs 중 하나를 택해 문제를 해결하면 된다. 해결하는 방법이 정말 다양하지만 그중 하나만 작성함. 문제 풀이 이 문제는 색약일때와 색약이 아닐 때 각각 어떻게 처리하냐에 풀이가 다를 것이다. 나는 배열을 복사해서 색약일 때(R == G) 따로 함수를 만들어 탐색하도록 만들었다. 다른 방법으로는 색약이 아닌 경우 탐색을 해주고 원래 ..

🧩 Problem Solving/[백준]

[백준] 1655 가운데를말해요 (python 파이썬)

2022.06.14

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 어린이에겐 매우 어려운 게임이다. 시간제한이 0.1초 인걸 보니 기존 정렬 방식으로는 해결이 힘들 거 같다. 사실문제 풀기 전에 우선순위 큐 문제 인걸 알고 있어서 이걸 어떻게 적용할지 생각하면 되는 문제다. 우선순위 큐 문제는 내가 정한 우선순위가 높은 데이터가 가장 먼저 pop 되는 큐다. 근데 예제 출력 부분을 보면 1 1 2 2 같이 중복된 값이 여러 번 출력된다. 따라서 ..

🧩 Problem Solving/[백준]

[백준] 7569 토마토 (python 파이썬)

2022.06.14

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 과정 저번에 푼 토마토 문제와 거의 유사하다. 차이점은 z축이 생김. 문제에서 M,N,H 최대값이 모두 100으로 큰수가 아니여서 그냥 3차원 배열을 사용하기로 했다. 따라서 z축 관련된 부분만 이전 문제에 추가하면 된다. 이전 문제 풀이에 대한 정보는 7576-토마토 참조 import sys from collections import deque input = sys...

🧩 Problem Solving/[백준]

[백준] 13549 숨바꼭질3 (python 파이썬)

2022.06.13

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 과정 1697 - 숨바꼭질 문제와 비슷하다. 차이점은 숨바꼭질 3 문제는 순간이동할 때 0초 소요된다. 숨바꼭질 문제를 예전에 풀어서 날로 먹으려 순간이동 부분만 코드를 수정했는데 틀렸다. 다시 짜야하나 싶었는데 조금만 수정하니까 해결됐다. bfs로 해결함. from collections import deque N , K = map(int,input().sp..

🧩 Problem Solving/[백준]

[백준] 2252 줄세우기 (python 파이썬)

2022.06.11

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 과정 입력값은 키를 비교한 학생 A와 B의 순서가 M개만큼 주어진다. 바로 이전에 풀었던 ACMCraft와 비슷한 유형인 거 같아 같은 방법으로 해결했다. 위상 정렬만 알면 간단하게 해결 가능하다. from collections import deque import sys input = sys.stdin.readline N, M = map(int,in..

🧩 Problem Solving/[백준]

[백준] 11718 그대로 출력하기 (python 파이썬)

2022.06.10

https://www.acmicpc.net/problem/11718 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net 풀이과정 문제 내용은 간단하다. 입력된 물자열을 그대로 출력해주면 된다. 하지만 입력에 끝을 알려주는 정보가 하나도 없다. 몇 줄이 입력되는지도 모르고 마지막에 개행이나 -1같은 입력값도 없다. 해결 방법은 두가지가 있다. 1. try except 구문 사용 2. sys.stdin.readlines() 사용 이문제에 대한 테스트는 직접 타이핑하다가 ctrl - D를 입력해 EOF..

티스토리툴바