언어/Python (16) 썸네일형 리스트형 [파이썬] 백준 1260번: DFS와 BFS www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그대로 DFS와 BFS에 관한 문제이다. 코드는 아래와 같다. [파이썬] 백준 11399번: ATM www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제를 보게 되면 N명의 사람이 있고 사람마다 돈 뽑는 시간을 주어지게 된다. 그리고 모두가 돈을 뽑았을 때 걸리는 시간의 최소를 구하는 문제임을 알 수 있다. 알고리즘을 다음과 같이 생각해 볼 수 있었다. 1. N명의 사람의 걸리는 시간을 리스트에 저장해 줌. 2. 리스트를 정렬함으로 작은 수 부터 놔둔다 3. for문을 두번째 인덱스부터 마지막까지 돌리면서 리스트를 업데이트 한다. 3 - 1. 자신의 앞의 값을 더한 값으로 업데이트해준다.. [파이썬] 백준 1916번: 최소비용 구하기 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이 문제는 제목에 나와있는 것과 같이 최소비용 구하기라고 할 수 있다. 그 중 다익스트라 알고리즘을 사용해 보았다. 📌 다익스트라 알고리즘(Dijkstra algorithm) - 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 노드간의 최단 경로를 찾는 알고리즘. - 두 도시 사이의 최단 경로, 네트워크 라우팅 프로토콜의 경우 등에서 사용된다. - 원래는 큐를 사용하여 O(.. [파이썬] 백준 7576번: 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 처음 이 문제를 보고 이거도 너무나 당연한 BFS, DFS문제라고 생각했다. 그러고 제출을 했는데 허무하게도 "시간초과"가 떠버렸다. 왜 시간초과가 떴을까? 몇 가지 추측을 해보았다. 1. 입력을 생으로 for문으로 받고 bfs를 돌릴때도 하나하나 다 돌렸기 때문일 수 도 있을 것이다. --> 해당 문제를 해결하기 위해 입력을 받으면서 1일 경우 큐에 넣어주는 작업까지 처리를 해 주었다. 2. .. [파이썬] 백준 2667번: 단지번호붙이기 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제는 전형적인 BFS, DFS로 풀 수 있는 문제이다. 조건에 맞게 변수와 조건을 넣어주면 쉽게 풀 수 있다. 주의점은 입력을 어떻게 받느냐에 따라 1을 체크할 것인지 '1'을 체크할 것인지 정해야하고 단지 사이즈를 오름차순으로 정렬해 출력해야한다는 것이다. 코드는 아래와 같다. [파이썬] 백준 2178번: 미로 탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제를 보고 전형적인 그래프 탐색 문제라고 생각을 하였다. BFS나 DFS로 풀 수 있을 것이라고 생각을 하고 코드를 짜보았는데 시간초과가 많이 발생하였다. 처음에는 입력을 받을 때 string으로 받은 것을 또 for문을 반복하여 list에 넣어 줘서 시간 초과가 뜬 것이라고 생각한다. 2. 여기서 왜 시간 초과가 났는지를 잘 모르겠지만 추측하건데, 처음에는 visited를 만들어 변경해 주어도 보았고 아래와 같이 해 보았는데 이번 문제에서.. [파이썬] 백준 2075번: N번째 큰 수 www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 처음 문제를 봤을 때 손쉽게 해결 될 문제라고 생각했다. - 반복문을 돌리면서 N*N 갯수만큼 리스트에 넣은 다음 정렬해 N번째 수를 뽑아낸다. => 메모리 초과로 실패 다음으로 생각한 것이 N까지만 있으면 되니까 N까지의 수만 넣고 다음 수 부터는 리스트에서 최소값과 비교해 바꿔주는 형식으로 코드를 짜 보았다. => 시간 초과로 실패 메모리 초과와 시간 초과를 해결하기 위해서 어떤 방법이 있을까? 메모리 초과는 N의.. [파이썬] 백준 14681번: 사분면 고르기 Pythonwww.acmicpc.net/problem/14681 14681번: 사분면 고르기 점 (x, y)의 사분면 번호(1, 2, 3, 4 중 하나)를 출력한다. www.acmicpc.net 조건문을 사용하는 문제이다. 이전 1 2 다음
