조이의 개발 다이어리

[Python] 백준 16434 드래곤 앤 던전

1. 문제 - 백준 16434 드래곤 앤 던전https://www.acmicpc.net/problem/16434 💡알고리즘 - 구현, 이분탐색우리는 용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 생명력을 알아내야한다.던전은 총 N개의 방으로 이루어져 있고, i번째 방을 통해서만 i+1 번째 방으로 이동할 수 있으며 몬스터가 있는 경우 반드시 쓰러뜨려야만 다음 방으로 이동할 수 있다. 즉 N만큼의 반복이 이루어지고 N의 범위는 123,456이다.그럼 용을 쓰러트리기 위한 최소의 생명력(H MaxHP)를 알아내려면 기존 완전탐색대로라면 1부터 시작해서 만족하는 값을 만날때 break하겠지만, 용사의 공격력과 몬스터의 공격력 범위 모두 1,000,000 이다.시간초과가 발생할 수 밖에 없다. 이 때..

1. 문제 - 백준 1347 미로 만들기https://www.acmicpc.net/problem/1347 💡알고리즘 - 구현 ✍🏻 막힌, 헷갈린 부분 1) 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다 --> 출발점을 어떻게 잡을까?방향을 틀거나 이동하는 경우가 총 50가지이므로, 넉넉하게 배열의 크기를 100 이상으로 잡고, 중간 지점을 시작점으로 하자 2) 어떻게 홍준이가 이동한 길만 출력할 수 있을까?홍준이가 이동하는 x좌표, y좌표의 최소값, 최대값을 구했을 때 최소값부터 최대값까지가 출력해야 할 범위라고 할 수 있다. ✅ 풀이n = int(input())word = list(input())x, y = 100, 100dx = [1, 0, -1, 0]dy = [0, 1, 0, -1]d =..

1. 문제 - 백준 4991 로봇 청소기https://www.acmicpc.net/problem/4991 💡알고리즘 1️⃣ BFS로봇에서 각 더러운 칸을 방문할 때, 더러운 칸에서 더러운 칸을 방문할 때 소요되는 최단거리를 계산할때 사용한다. 2️⃣ 순열로봇청소기가 현재 위치에서 어떤 더러운 칸을 먼저 방문할지에 따라서 모든 더러운 칸을 청소하는 데 있어 매번 이동 횟수의 최솟값이 달라지기 때문에, permutations(순열) 을 통해 완전탐색하며 이동 횟수의 최소값을 비교해야한다. ✍🏻 막힌, 헷갈린 부분 로봇은 같은 칸을 여러 번 방문할 수 있다.--> visited로 방문처리를 하지 않으면 BFS가 매번 모든 인접한 칸을 그래프 탐색하는거 아닌가?--> BFS는 로봇청소기가 각 더러운 칸을 ..

1. 현재 위치와 함께 MapView 표시하기1️⃣ 위치 권한 요청 후, 현재 위치 받아오기 Info.plist NSLocationAlwaysUsageDescription 위치 기반 맛집 검색을 위해 위치 권한 허용이 필요합니다. NSLocationWhenInUseUsageDescription 위치 기반 맛집 검색을 위해 위치 권한 허용이 필요합니다. NSLocationAlwaysAndWhenInUseUsageDescription 위치 기반 맛집 검색을 위해 위치 권한 허용이 필요합니다. LocationService- 위치 권한 여부를 체크하고, 허용받았을 때 사용자의 위치를 가져오는 Service Class이다.import CoreLocationclass LocationService: NSObject ..

1. 문제 - 프로그래머스 광고 삽입 (2021 카카오 기출)https://school.programmers.co.kr/learn/courses/30/lessons/72414 💡알고리즘 - 누적합, 구간합 알고리즘- 구간별 누적 재생시간을 구해야하는데, logs의 길이가 360,000 이므로 O(n^2)의 시간을 O(n)으로 줄여줄 만한 알고리즘을 사용해야한다.- 이때 누적합의 배열을 구한 뒤, 해당 누적합 배열을 이용해서 구간합을 구함으로써 O(n) 의 시간으로 구간합을 구할 수 있는 알고리즘을 사용한다. ✍🏻 막힌 부분- 처음에 단순히 2중 반복문으로 구간합을 구해서 풀었는데, logs가 10^5가 넘어가니 당연히 시간초과가 걸릴수밖에 없었다. 이부분을 어떻게 최적화할 수 있을지에서 막혔다. ✅ ..

1. 문제 - 백준 19238 스타트 택시https://www.acmicpc.net/problem/16562 💡알고리즘 - BFS + 시뮬레이션- 그래프가 나오고, 택시는 손님을 태우러가든 손님을 태우고 목적지에 가든 항상 최단거리로 이동하므로 BFS를 통해 탐색한다. ✅ 풀이from collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]n, m, e = map(int, input().split()) # e: 초기 연료의 양, 연료는 무한히 담을 수 있음board = []for i in range(n): # 0은 빈칸, 1은 벽 board.append(list(map(int, input().split())))customers = {} ..

1. 백준 2504 괄호의 값https://www.acmicpc.net/problem/2504 💡 알고리즘 - 구현, 스택- 보통 올바른 괄호 같이 앞의 원소와 짝지어서 올바른 조합인지 확인하는 문제는 스택을 쓴다. 여는 괄호 (, [는 append, 닫는 괄호 ), ]를 pop 해서 올바른 괄호인지 확인하는 방식이다. ✅ 풀이stack = []answer = 0str = input()flag = Falsetemp = 1for i, w in enumerate(str): if w == "(": stack.append(w) temp *= 2 elif w == "[": stack.append(w) temp *= 3 elif w == ")": if not stack or sta..

1. Combine이란?공식문서: https://developer.apple.com/documentation/combineCustomize handling of asynchronous events by combining event-processing operators이벤트 처리 연산자를 결합하여, 비동기 이벤트 처리를 커스터마이징할 수 있는 프레임워크 즉, Apple에서 만든 RxSwift 와 같은 프레임워크라고 할 수 있고, 더 간결하고 다양한 연산자를 활용해 더 다양한 비동기 처리를 할 수 있도록 도와주는 프레임워크이다. 필자는 기존에 RxSwift를 활용하여 비동기 처리를 하는 데 익숙했기에 RxSwift와 비교하여 그 특징을 정리하고, 사용법을 간단하게 정리해보고자 한다. 2. Combine의 3..

1. 문제 - 백준 16562 친구비https://www.acmicpc.net/problem/16562 💡알고리즘 - DFS or 유니온파인드- "친구의 친구는 친구다" 즉, 친구 무리를 짓는다는 점에서 DFS 혹은 유니온파인드를 이용할 수 있다.- 각 친구 무리 별로 친구비가 가장 적은 친구비를 합쳐 준석이가 가진 비용과 비교한다. ✅ DFS 풀이import syssys.setrecursionlimit(10**8)n, m, k = map(int, input().split())money = [0] + list(map(int, input().split()))graph = [[] for _ in range(n+1)]for _ in range(m): v, w = map(int, input().split()..

1. 문제 - 프로그래머스 퍼즐 게임 챌린지 (PCCP 기출 문제)https://school.programmers.co.kr/learn/courses/30/lessons/340212 💡알고리즘 - 파라메트릭 서치(이분 탐색을 이용한 조건에 맞는 값 찾기)- for문으로 1부터 시작하여 문제 조건에 맞는 숙련도(level)을 찾게 도면, diffs 와 times의 길이는 최대 300,000이고diffs는 최대 100,000 이기 때문에 시간복잡도 O(n^2)에 의해 시간초과가 발생한다.- 이럴때 탐색에 있어 시간을 줄여줄 방법론들을 생각해봐야한다. 이분탐색? 투포인터?- 문제에서 diffs[0]는 1로 고정되어있다. 즉, diffs의 최소, 최대값이 명확하며 특정 조건을 만족하는 level의 최소값을 찾..