[백준] 어드벤처 게임

https://www.acmicpc.net/problem/2310 백준 2310번: 어드벤처 게임파이썬문제를 풀었던 방법DFS를 사용해서 풀었습니다. 방문처리에 대해서들렀던 곳을 또 들려야 최소가 되는 경우를 고려했었기 때문에 처음에는 방문처리를 하지 않았습니다.. 사진과 같은 경우에 빈방에서의 소지금이 0원이라면 그냥 일반적인 방문처리로는 트롤방으로 바로 가는 경우가 없습니다.하지만 방문처리를 하지 않는다면 빈방(소지금:0) → 레프(소지금:20) → 빈방(소지금:20) → 트롤방(소지금:10) 이런식으로 갈 수 있어서 이걸 고려했습니다. 하지만 아예 방문처리를 안하니까 당연히 시간초과가 났고, 이걸 해결하기 위해 방문처리를 할때 방문 처리 배열에 현재 가지고 있는 소지금을 저장했습니다.→그래서 다시 ..

• format_list_bulleted 알고리즘/문제풀이
• · 2025. 3. 24.
• textsms

[백준] 좋다

https://www.acmicpc.net/problem/1253 백준 1253번: 좋다  풀었던 방법→ 두 숫자를 더해서 하나의 숫자를 찾는거니까 투포인터를 썼습니다. 숫자를 크기 순서대로 정렬하고3번째 숫자부터 마지막 숫자까지 하나씩 확인을 합니다포인터를 배열의 가장 처음에 하나, 마지막에 하나를 두고 각 합이 확인중인 숫자랑 같은지를 확인합니다확인중인 숫자 > 합이라면 처음 포인터를 뒤로 밀고,확인중인 숫자  생겼던 문제처음에는 숫자들이 모두 자연수인줄알고 투포인터를 이용해서 찾을때 탐색하는 범위를 탐색중인 숫자의 앞 배열만을 사용했습니다.1, 2, 3, 4, 5, 6, 7예를 들어, 이 방법일 때 5를 확인중이라면p1 = 1로 두고, p2 = 4로 둬서 확인을 했습니다.하지만 배열이 모두 자연수가..

• format_list_bulleted 알고리즘/문제풀이
• · 2025. 3. 24.
• textsms

[백준] 14658번 하늘에서 별똥별이 빗발친다

백준 14658번 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 브루트포스, 라고는 나와있는데 구글링 했을 때랑 다르게 풀었음 K의 갯수가 100개 이하이므로 K기준으로 진행 12 10 4 7 2 4 7 3 3 1 5 6 4 7 12 10 8 6 해당 예제에서 별의 위치를 받고, 얘네를 우선 x기준으로 정렬을 해준다. [(2, 4), (3, 1), (4, 7), (5, 6), (7, 3), (8, 6), (12, 10)] 이런식으로 ..

• format_list_bulleted 알고리즘/문제풀이
• · 2024. 2. 20.
• textsms

[백준] 4485번, 녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 이름이 젤다길래 풀어봤는데 젤다는 안나오고 뭔 강도가... 문제 젤다가 (0, 0)의 위치에서 (N - 1, N - 1) 위치로 이동하는데 맵에는 강도가 있어서 강도가 있는 위치로 지나가면 일정 금액을 뜯긴다.... 그래서 최대한 덜 뜯기고 갔을 때, 잃은 돈을 출력해주기 풀이 다익스트라의 정석같은 문제였음.. 맵과 같은 크기의 리스트를 만든 후, 엄청 큰 값(inf)을 넣어둠 ..

• format_list_bulleted 알고리즘/문제풀이
• · 2023. 10. 13.
• textsms

[백준] 1326번, 폴짝폴짝

# BFS https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 문제 개구리가 징검다리를 건너는데, 다리에는 각각 숫자가 써져있음 그 숫자의 배수만큼은 그냥 갈 수 있다. 출발지와 목적지가 주어졌을 때, 목적지까지 가는데 얼마나 걸리는지 구하기 ▶ 내가 지금 밟은 칸이 1이 되면 다 갈 수 있음 → 시간 무조건 1 ▶ 배수 만큼은 갈 수 있다고 했으니까 뒤로도 가능함 BFS방식으로 풀었다 풀이 from collections import ..

• format_list_bulleted 알고리즘/문제풀이
• · 2023. 10. 6.
• textsms

[알고리즘] 알고리즘과 시간 복잡도

알고리즘이란? 문제 해결을 위한 절차나 방법 좋은 알고리즘이란 무엇인가 정확성: 얼마나 정확한지 작업량: 얼마나 적은 연산으로 결과를 내는지 메모리 사용량: 얼마나 적은 메모리를 사용하는지 단순성: 얼마나 단순한지 최적성: 개선할 여지가 없는지 시간 복잡도 실제 걸리는 시간을 측정, 실행되는 명령문의 개수를 계산해서 얻어낼 수 있음 빅 - 오 표기법 시간 복잡도 함수 중에서 가장 큰 영향을 주는 n에 대한 항만을 표시한 것 계수는 생략함 예: O(n) = O(3n)

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