본문 바로가기

분류 전체보기

 (224)
[python] 백준 1629번 - 곱셈 1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 자체는 어렵지 않았다. 물론 이해하는 데만 어렵지 않았다. 분할정복을 이용해 풀어야 했기 때문에 대체 어떻게 접근해야 하는 것인지 모르겠어서 애를 먹었고 결국 다른 풀이를 참고하여 이해할 수 있었다. 지수법칙만 알면 간단하게 풀 수 있다. 문제의 예제인 [10, 11, 12]를 예로 들자면 10**11%12는 10**5*10**6%12와 같이 나눌 수 있다. 마찬가지로 계속해서 지수법칙을 사용하여 나누면 계산해야 할 횟수가 줄어든다. a,b,c = map(int, input()...
[python] 백준 11660번 - 구간 합 구하기 5 11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 백준 단계별 알고리즘의 누적합 카테고리에 있는 문제이다. 처음에는 누적합을 쓰는 것이 익숙하지 않았는데 이젠 나름 잘 적용하는 것 같다. 표의 크기와 수가 주어지면 구간합을 구하는 문제인데 처음에는 문제를 잘못 이해해서 테스트 케이스는 통과하였으나 오답처리되었다. 예를들어 4*4인 표에서 (2,2)부터 (3,4)까지의 구간합을 구한다고 친다면 (2,2), (2,3..
[python] 백준 2559번 - 수열 2559번: 수열 (acmicpc.net) 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 누적 합 문제이다. 처음에 for문을 두번 돌려서 답은 나왔는데 계속 시간제한이 걸렸다. 첫 인덱스부터 더해가며 누적 합을 구하는 것도 아니었기 때문에 어떻게 누적합 리스트를 만들 수 있을까 고민하였지만.. 결국 다른 해설을 보고 이해했다. 다시 해결한 방법은 다음과 같다. import sys input = sys.stdin.readline n,k = map(int, input().split()) lst=[..
[TIL] 최단 경로 알고리즘 - 다익스트라 최단 경로란? 두 노드를 잇는 가장 짧은 경로를 찾는 것 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로 특정 노드에서 출발하여 또 다른 특정노드에 도착하는 가장 짧은 경로를 찾음 그래프 내의 특정 노드에 대해 다른 모든 노드 각각에 대한 가장 짧은 경로를 찾음 ex) 다익스트라 그래프 내의 모든 쌍에 대한 최단 경로를 찾음 다익스트라 알고리즘 최단 경로 알고리즘 중 하나로 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 알고리즘 인접한 정점들의 거리를 계산하여 최단 거리로 갱신 BFS와 비슷 다익스트라 알고리즘 이해 우선순위 큐를 사용 (최소힙) -> 가장 낮은 우선순위를 가진 노드를 pop 각 정점까지의 거리를 계산하는 배열과 인접노드와 그 거리를 비교하는 우선순위 ..
[python] 백준 5430 - AC 5430번: AC (acmicpc.net) 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 파이썬의 deque를 활용하는 문제였다. 그런데 처음에 계속 시간초과가 나서 코드를 수정하였고 이후로는 답이 틀렸다고 나와서 또 코드를 수정하였다. 간과한 점이 있었는데 문제를 꼼꼼하게 고민해보는 습관을 좀 길러야 할 것 같다. 이 문제를 풀면서 주의해야 할 점은 1. R이 두번 나올 경우 역순의 역순 즉, 원래 상태와 비슷하기 때문에 R의 개수를 세어서 짝수인 경우는 굳이 역순으로 바꿔줄 필요가 없다. 2. D를 수행할 때 배열에 아무것도 들어가 있지 않는다면 error를 ..
[TIL] 탐욕 알고리즘 - Greedy Algorithm 탐욕 알고리즘 최적의 해에 가까운 값을 구함 매 순간 최적이라고 생각되는 경우 근사치 추정에 활용 -> 반드시 최적의 해를 구하는 것은 아님 관련 문제 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 식을 입력받아 괄호를 적절히 사용하여 값을 최소로 만드는 문제이다. 이 문제에서는 최소의 값을 구하는 것이 최적의 해를 구하는 것이므로 그리디 알고리즘을 사용하여 해결한다. 문제를 분석해보았을 때 - 다음 + 연산이 나올 경우 괄호를 사용하면 최소값을 구할..
[python] Set() 집합 연산 Set은 수학에서 배웠던 집합과 같은 개념이다. 순서와 중복이 가능한 리스트와는 다르게 순서도 없고 중복을 허용하지 않는다. 수학의 연산과 같이 합집합, 교집합, 차집합 연산 기능을 각각 수행할 수 있다. 1. 합집합 - 합집합은 | 연산자와 union 함수를 이용한다. - 두개의 집합에서 중복되는 요소를 삭제한 후 새로운 집합을 반환한다. s1={1,2,3} s2={3,4,5} print(s1|s2)# {1,2,3,4,5} print(s2.union(s1))# {1,2,3,4,5} 2. 교집합 - 교집합은 & 연산자와 intersection 함수를 이용한다. - 두개의 집합에서 공통요소만을 포함해 새로운 집합을 반환한다. s1={1,2,3} s2={3,4,5} print(s1&s2)# {3} print..
[python] deque from collections import deque 그냥 리스트를 사용하는 것보다 deque를 사용하면 속도가 훨씬 빠르다. (O(1)) 리스트 함수와 거의 비슷하지만 deque에서 기억해야 할 함수를 보자면 다음과 같다. - appendleft() - extendleft() - popleft() - rotate() *양수값은 오른쪽으로 음수값은 왼쪽으로 회전 2164번: 카드2 (acmicpc.net) 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net
728x90

티스토리툴바