Algorithm

[백준] 14890. 경사로 - 파이썬

[Gold III] https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 골드 3짜리 빡구현 문제.. 한 줄(행/열) 마다 돌려가며 check. 모든 칸에 대해 돌려봐도 100x100 = 10,000 이므로, Brute-Force로 접근 가능. 한 줄의 모든 칸에 대해, 다음 칸과 1 이상 차이나면 break처리. 다음 칸과 숫자가 동일하면 패스. 다음 칸보다 더 작다면, 그 이전 L개의 칸이 동일한 지 확인. 다음 칸보다 더 크다면, 그 이후 L개의 칸이 동일한 지..

[백준] 1360. 되돌리기 - 파이썬

[Gold V] https://www.acmicpc.net/problem/1360 1360번: 되돌리기 첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 명령과 수행한 시간이 주어진다. 항상 시간이 오름차순으로 주어지고, type c에서 c는 알파벳 소문자, undo t에서 t는 1보다 크거나 같 www.acmicpc.net 풀이 N < 50 이라는 조건에 집중할 필요가 있다. undo t 에서 1 < t < 10^9 이지만, N < 50 이므로, 특별한 알고리즘을 사용하지 않고, 바로 구현할 수 있는 빡구현 문제라는 것을 알 수 있다..! Dictionary (Hash Table) 형태에 입력 시간을 key값으로 하여 모든 정보를 저장하고, 입력 시간 역순으로 작업을 수행, undo 할 ..

[백준] 2812. 크게 만들기 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 한 달여만에 다시 잡은 알고리즘... BFS 풀다 때려치고 Greedy로 도망침. 모든 숫자를 받아놓고.. 앞에서부터 하나씩, Stack에 넣어 가며, K가 남아있는 한 앞에 있는 더 작은 숫자를 greedy하게 모두 pop하는 식으로 진행하면 complete. from collections import deque N, K = map(int, input().split()) num = deque(list(input())) res = deque() fo..

[백준] 1744. 수 묶기 - C++

[Gold IV] https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 발상 자체는 어렵지 않은 Greedy 문제. 그러나 자잘한 case들을 모두 처리해 줘야 해서 실수할 수 있는 부분이 많았다. #include #include #include #define init cin.tie(0)->ios_base::sync_with_stdio(0); using namespace std; typedef long long ll; int main() { ..

[백준] 28297. 차량 모듈 제작 - C++

[UCPC 2023 예선 C번] [Gold I] https://www.acmicpc.net/problem/28297 28297번: 차량 모듈 제작 현대모비스는 한국 외에도 유럽, 중국, 미국, 인도 등 여러 곳에 연구소를 두고 자율주행, 전동화, 커넥티비티 등의 미래기술은 물론 기존 기계 부품(제동, 조향, 현가, 안전, 램프 등)에도 ICT 기 www.acmicpc.net 풀이 수학적 지식과, MST(Minimum Spanning Tree)를 이용해 풀 수 있었던 문제. 대회 당일에는, 시간을 얼마 안 남겨놓고 풀이를 시작해서, 조급하게 Union-Find로 접근하다 O(N^3)으로 TLE를 냈는데, 끝나고 다시 보니 MST로 풀이하면 된다는 것을 깨달았다...! 우선, 두 점 사이의 유클리드 거리는 ..

[백준] 1339. 단어 수학 - 파이썬

[Gold IV] https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 딱 봐도 파이썬으로 풀면 편하겠다 싶어서 파이썬으로 조진(?) 문제. 단어를 받아오고, 자릿수에 따른 가중치(?)를 계산 후 내림차순으로 정렬하여 Greedy하게 숫자를 배정해 주었다. AC. N = int(input()) A = dict() words = [] for _ in range(N): word = list(input()) words.append(word) w..

[백준] 2169. 로봇 조종하기 - C++

[Gold II] https://www.acmicpc.net/problem/2169 풀이 일반적인 Bottom-Up 형식으로 풀어낸 DP 문제. 아래, 오른쪽으로만 갈 수 있는 것이 아닌, 왼쪽으로도 갈 수 있기 때문에 이를 고려해줘야 했으나, "한 번 방문한 곳은 다시 방문하지 않는다" 라는 조건이 있기 때문에, 각 줄에서, 왼쪽부터 DP 배열을 갱신하고 (line 43~45), 또 오른쪽부터 다른 DP배열을 갱신한 후 (line 47~49), 둘 중 더 큰 것(최댓값)을 택하여 DP 배열을 최종적으로 갱신해주는 식으로 모든 줄을 반복하면 된다. 다만 주의할 것은, DP 배열을 초기화할 때, 음수 value값이 있으므로, 최댓값을 구하기 위해서는 0으로 초기화하지 않고, 나올 수 있는 가장 작은 값(-..

[백준] 1520. 내리막 길 - C++

[Gold III] https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 1 Bottom-Up 방식의 DP. 오른쪽 아래부터 왼쪽 위까지 채워나가는 방식으로 구현했다. 오른쪽과 아래로만 갈 수 있는 줄 알았는데, 위와 왼쪽으로도 갈 수 있어서 WA. #include #include #include #define init cin.tie(0)->ios_base::sync_with_stdio(0); typedef long long ll; using nam..