알고리즘
-
[BOJ 1541, Python 3] 잃어버린 괄호알고리즘/BOJ 2021. 8. 4. 14:13
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 처음 - 부호가 나오기 전까지는 더해주다가 -가 나온 이후에는 계속 빼주면 됩니다. 왜냐하면 ㅁ + ㅁ - ㅁ + ㅁ + ㅁ + ㅁ + ㅁ 이렇게 마이너스가 하나만 있는 식이 있다고 하면 ㅁ + ㅁ - (ㅁ + ㅁ + ㅁ - ㅁ + ㅁ) 이렇게 괄호를 해주면 되고 ㅁ + ㅁ - ㅁ + ㅁ - ㅁ + ㅁ - ㅁ 같이 마이너스가 여러 개 있는 식이 있다고 하면 ㅁ + ㅁ - (ㅁ + ㅁ) ..
-
[BOJ 1080, Python 3] 행렬알고리즘/BOJ 2021. 8. 4. 14:09
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 풀이 어느쪽 모서리이든 (0, 0), (0, m-1), (n-1, 0), (n-1, m-1) 어느쪽으로 출발해도 상관은 없는데 가장 대중적인 (0, 0)을 기준으로 말하겠습니다. 먼저 정답부터 말하고 풀이를 설명드리겠습니다. 처음 행렬을 s, 정답 행렬을 answer라고 가정합시다. 문제에서 3by3행렬을 뒤집는다고 합니다. 그러면 n - 2개의 행과 m - 2개의 열을 확인하여 s[i][j]의 값이 anwer..
-
[BOJ 19941, Python 3] 햄버거 분배알고리즘/BOJ 2021. 8. 4. 13:50
https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 풀이 컵홀더 문제랑 비슷한데, 컵홀더는 K = 1일때만 가능한 문제이고 이건 K가 아무런 값이 주어졌을 때도 풀 수 있는 좀 더 업그레이드된 문제입니다. 저는 큐를 불러오면 코드가 길어지기 때문에 그냥 ←방향으로 스택을 이용해서 풀었습니다. 풀이는 간단합니다. 일단 큐나 스택을 2개 만들어서 햄버거의 좌표, 사람의 좌표를 따로따로 넣어줍니다. 그다음 → 방향이든, ← 방향이든 햄버거를 먹을 수 ..
-
[BOJ 18310, Python 3] 안테나알고리즘/BOJ 2021. 8. 3. 15:59
https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 풀이 y = | x - x1 | + | x - x2 | + | x - x3 | + .... + | x - xn | 로 그래프를 그려보면 대충 아래와 같은 모양이 나옵니다. 같은 거리의 집도 있으니 좀 찌그러진 2차함수 모양이겠네요. 여기서 n이 홀수이면 최소값이 딱 하나 나옵니다. n이 짝수이면 최소값이 두 개 나옵니다. 그림은 y축이 살짝 다르지만 (n - 1)/2 값과 n / 2 값이 같다고 생각해주세요. 그래서 n..
-
[BOJ 11508, Python 3] 2+1 세일알고리즘/BOJ 2021. 8. 3. 15:49
https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 풀이 최솟값을 지불하는 방법을 도출하라고 합니다. 이 말을 살짝 비틀어서 무료로 받을 수 있는 상품의 금액을 최대화한다고 생각해봅시다. 무료로 받는 상품의 금액을 최대화해야하니 최대한 큰 값을 무료로 받으면 좋은 것은 당연합니다. 그러면 내림차순으로 정렬해봅시다. 첫번째 값과 두번째 값은 무조건 사야하고, 세번째로 비싼 상품은 무료로 받을 수 있습니다. 이렇게 1+2, 3무료, 4+5,..
-
[BOJ 11501, C++, Python 3] 주식알고리즘/BOJ 2021. 8. 3. 15:44
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 풀이가 O(N+N)과 O(N) 2가지가 존재합니다. 하지만 파이썬은 O(N)만 통과합니다. C++ 풀이 O(N+N) 문제를 보자마자 대부분의 사람들이 왼쪽에서 오른쪽으로 확인하는 방법을 찾아볼 것 입니다. 그래서 → 방향으로 확인하는 방법은 주가의 값(arr[i])을 받고, pair(arr[i], i)로 묶어서 정렬하는 방법입니다. 이 정렬하는 벡터를 max_val이라고 하고, ..
-
[BOJ 11399, Python 3] ATM알고리즘/BOJ 2021. 8. 2. 13:08
https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 더하는 방법이 (이전까지의 사람들이 돈을 인출하는데 걸린 시간의 합) + (현재 뽑고 있는 사람이 돈을 인출하는데 걸리는 시간)으로 나눌 수 있습니다. (현재 뽑고 있는 사람이 돈을 인출하는데 걸리는 시간)은 값은 입력값으로 주어지는 것이라서 값이 고정되어 있는데, (이전까지의 사람들이 돈을 인출하는데 걸린 시간의 합)은 배치에 따라 값이 달라질 수 있습니다. 그래서 (이전까지의 사람들이 돈을 인출하는데 걸린 시간의 합)..
-
[BOJ 2012, Python 3] 등수 매기기알고리즘/BOJ 2021. 8. 2. 13:04
https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 풀이 오름차순으로 정렬하여 답을 구하면 됩니다. 파이썬은 단순 input으로 하면 시간초과가 나와서 fast input을 사용해야 합니다. 코드 1 2 3 4 5 6 7 8 input = __import__('sys').stdin.readline n = int(input()) arr = sorted(int(input()) for i in range(n)) ans = 0 for i in range(n): ..