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

[백준] 14938 서강그라운드 (python 파이썬)

2022.09.10

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 조건만 잘 생각하면 되는 착한 문제. 아이디어 1. 다익스트라 출발지로 부터 최단거리를 계산해서 수색 범위안에 들어가는지 확인하면 된다. 수색 범위안에 들어오면 아이템 개수를 더해주면 된다. 1 ~ n까지 for문으로 출발지를 바꾸면서 탐색하면 된다. 2. 플로이드 워셜 지역의 개수(100)가 적으므로 플로이드 워셜로 풀어도 시간초과에 걸리지 않는다. 전체 코드 다익스트라 import heapq imp..

🧩 Problem Solving/[백준]

[백준]11660 구간 합 구하기 5 (python 파이썬)

2022.08.19

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 구간 합 구하기 2차원 버전 아이디어 1. 누적 합 사용 구간 합 구하기 4와 유사하게 풀었다 먼저 (0 ,0)에서 (x , y)까지의 합을 arr [x][y]에 저장한다. 그럼 아래와 같은 리스트를 만들 수 있다. 이걸 사용해서 구간 합을 구하면 된다. 예를 들어 (1, 1)에서 (2, 3)까지 구하려면(문제에서는 2,2 ~ 3,4) arr [2][3]..

🧩 Problem Solving/[백준]

[백준] 10942 팰린드롬? (python 파이썬)

2022.08.17

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 배열에서 i부터 j까지가 팰린드롬인지 아닌지 여러 번 확인하는 문제. 아이디어 1. dp 간단하게 리스트 슬라이싱으로는 시간 초과가 나서 dp를 사용 i번째부터 j까지의 수가 팰린드롬인지 확인한 결과를 저장하기 위해 이차원 리스트를 사용하기로 결정했다. 2. 점화식 먼저 무조건 팰린드롬인 i부터 i까지의 수는 1로 저장해둔다. 그리고 i번째 수와 i + 1번째 수가 같으면 팰린드롬이니까 이것도 1로 저장. 점화식은 이미 팰린드롬인 수 ..

🧩 Problem Solving/[백준]

[백준] 1647 도시 분할 계획 (python 파이썬)

2022.08.01

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 난이도에 비해 매우 간결한 문제다. 대신 크루스칼 알고리즘과 유니온 파인드에 대해 알고 있어야 한다. 아이디어 1. 마을을 두 개로 분리하는 방법 크루스칼 알고리즘에 대해 잘 기억하고 있다면 쉽게 떠올릴 수 있다. 크루스칼 알고리즘으로 최소 스패닝 트리를 만들고 여기서 비용이 가장 큰 간선을 잘라주면 된다. 최소 스패닝 트리에서는 사이클이 존재하지 않는다. 그..

🧩 Problem Solving/[백준]

[백준] 1644 소수의 연속합 (python 파이썬)

2022.07.31

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 저번에 푼 부분합 문제의 소수 버전. 비슷한 문제여서 금방 해결 가능했다. 아이디어 1. 소수 찾기 시간 복잡도가 빠른 에라토스테네스의 체 방법으로 소수를 찾았다. 2. 소수의 연속합 부분합 문제와 유사하게 투 포인터를 사용해서 경우의 수를 찾았다. 전체 코드 import math n = int(input()) if n == 1: print(0) exit(0) arr = [True] * (n + 1) arr[0] = False arr[1] = False for i in range(2, int(math.sqrt(n)+..

🧩 Problem Solving/[백준]

[백준] 9466 텀 프로젝트 (python 파이썬)

2022.07.31

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간제한 3초로 매우 길지만 너무 복잡하지 않은 문제. 아마 테스트 케이스가 여러 개라서 시간제한을 널널하게 둔 거 같다. 아이디어 1. 그래프 일단 보자마자 그래프를 써야 한다고 생각했다. 문제 조건에서 팀이 되려면 서로가 꼬리를 물듯 사이클이 생겨야 한다. 그럼 이 문제는 그래프에서 '사이클을 어떻게 찾고 판별하냐'에 대해서 생각하면 된다. 2. dfs 방문 유무를 통해 사이클이 생겼는지 안 생겼는..

🧩 Problem Solving/[백준]

[백준] 1806 부분합 (python 파이썬)

2022.07.29

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 아이디어 1. 부분합 사용 부분합에 대해 간단히 얘기해보면 0 ~ N까지의 합을 미리 구해두고 합의 차((0 ~ b까지 합) - (0 ~ a까지 합))를 통해 a부터 b까지 수의 합을 빠르게 구하는 방법이다. 그래서 for문을 사용해서 길이가 1일 때, 2일 때... N일 때 부분합의 값을 구해보며 S값이 넘는 순간 프로그램을 종료하도록 코드를 짰다. 당연하게도 시간 초과가 떴다. ..

🧩 Problem Solving/[백준]

[백준] 1504 특정한 최단 경로 (python 파이썬)

2022.07.28

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 아이디어 1. 가중치가 있는 그래프 다익스트라 아니면 플로이드 두 개를 생각했다. 두정점 v1, v2를 지나는 최단경로는 각각의 최단경로들을 더한 것과 같으므로 다익스트라를 여러 번 사용하면 된다. '1 -> N' = '1 -> v1' + 'v1 -> v2' + 'v2 ->N' 같이 계산해서 두 정점을 지나는 최단경로를 구한다. 루트는 1 -> v1 -..

티스토리툴바