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

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 배열이 주어진 후 한 지점부터 특정 지점까지의 합을 구하는 문제이다. 아이디어 (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 이라는 조건이 있기 때문에 무턱대고 반복문을 이용해 합을 구하면 시간초과가 난다. 따라서 구간합을 이용해서 효율적으로 계산해야한다. x1,y1 부터 x2,y2까지의 구간합은 다음과 위와 같이 구할 수 있다. 따라서 모든 구간에서의 누적합을 구해놓은 후 필요한 영역의 구간합을 ..

• format_list_bulleted 알고리즘
• · 2023. 11. 13.
• textsms

[백준 파이썬] 18110 solved.ac

18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 문제 난이도가 주어진 후 주어진 난이도의 개수에 앞 뒤 15%의 개수는 자른 후 평균을 구하는 문제이다. 아이디어 15%를 자른 후 소수점은 반올림해야 하므로 간단하게 round함수를 사용하면 되겠다고 생각했다. 하지만 round함수를 사용하면 문제를 틀리게 된다! 그 이유는 파이썬 round함수의 사사오입 특성 때문이다. 사사오입은 5에서 반올림 할때, 앞자리 숫자가 홀수면 올림, 짝수면 내림을 한다. 즉 print(round(1..

• format_list_bulleted 알고리즘
• · 2023. 11. 10.
• textsms

[백준 파이썬] 1238 파티

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 아이디어 그래프의 최단 경로를 구하여 코스트를 계산하는 문제이므로 다익스트라 알고리즘을 사용하였다. 풀이 heapq를 이용해 다익스트라를 구현하였다. def dijkstra(start): q = [] distance = [sys.maxsize] * (N + 1) heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if d..

• format_list_bulleted 알고리즘
• · 2023. 11. 8.
• textsms

[백준 파이썬] 1167 트리의 지름

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 트리의 정보가 주어지고 트리의 지름을 구하는 문제이다. 아이디어 트리의 지름은 가장 먼 거리의 두 정점 사이의 거리이다. 따라서 가장 멀리 떨어져 있는 두 정점을 구한 후 거리를 계산하면 된다. 가장 먼 거리에 있는 두 정점을 얻는 방법은 떠올리지 못해 구글링을 통하여 방법을 알아내었다. 방법은 다음과 같다. 1. 임의의 정점에서 가장 먼 거리에 있는 정점을 구한다. 2. 구한 정점에서 또 다시 가장 먼 거리에 있는 정점을 구한다. 3...

• format_list_bulleted 알고리즘
• · 2023. 11. 6.
• textsms

[백준 파이썬] 2096 내려가기

2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 3열로 이루어진 줄에서 주어진 N의 크기의 행으로 이루어져 있다. 각각의 칸 마다 숫자가 부여되고 위에서부터 칸을 내려갈 때 최대값과 최소값을 구하는 문제이다. 이 때 내려갈 수 있는 조건은 자기자신과 인접해있는 2칸이내의 칸으로만 내려갈 수 있다. 즉 가장 측면의 칸일경우 바로 아래칸과 가운데 칸으로 이동할 수 있고 가운데 칸의 경우 모든 칸으로 내려갈 수 있다. 알고리즘 전체적인 아이디어는 이전에 풀었던 1149번 RGB거리와 유사하다. 따라서 Dp로 풀어야겠다고 생..

• format_list_bulleted 알고리즘
• · 2023. 11. 1.
• textsms

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

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 방향성이 없는 그래프가 주어지고 지나야하는 두 정점이 주어진다. 해당 정점을 모두 지나면서 가장 빠르게 갈 수 있는 길이를 출력하는 문제이다. 알고리즘 그래프경로의 최소값을 구해야 하고 가중치가 주어졌으므로 "다익스트라"알고리즘을 사용해야겠다고 생각했다. 1. 다익스트라 알고리즘 다익스트라 알고리즘을 구현하기 위한 순서는 다음과같다. 1. 자기 자신의 거리(0)를 우선순위 큐에 넣고 다른 노드의 거리를 무한으로..

• format_list_bulleted 알고리즘
• · 2023. 10. 29.
• textsms