조이의 개발 다이어리

[Python] 백준 16954 움직이는 미로 탈출

1. 문제 - 백준 16954 움직이는 미로 탈출https://www.acmicpc.net/problem/16954 💡알고리즘 - BFS시작점(7,0)이 있고 도착점(0,7)이 있고 그래프 탐색이라는 점에서 DFS, BFS를 활용할 수 있다. 필자는 BFS가 더 편해서 BFS 사용✅ 풀이from collections import dequedx = [-1, 1, 0, 0, -1, -1, 1, 1, 0]dy = [0, 0, -1, 1, -1, 1, -1, 1, 0] # 인접한 한칸 혹은 대각선 방향, 현재 위치에 서있을 수 있음board = []for _ in range(8): board.append(list(input()))# board에서 벽 아래로 이동하는 함수 하나 필요def move_wall(..

1. 문제 - 백준 16139 인간-컴퓨터 상호작용https://www.acmicpc.net/problem/16139 💡알고리즘 - 구간합 알고리즘문자열의 구간 별 알파벳의 등장 횟수를 구해야하나, 문자열의 길이가 200,000자 인데 질문의 갯수인 q도 200,000개이다.매번 반복문을 통해 알파벳의 등장 횟수를 구하면 시간초과가 발생한다.구간 문제의 해답을 구할 때 O(N^2)의 시간복잡도를 O(N)의 시간복잡도로 해답을 구할 수 있도록 해주는 알고리즘이 구간합 알고리즘이다.구간합 알고리즘이란? i ~ j 구간합을 구할 때 누적합을 구해두고 -> arr[i] - arr[j-1] 의 공식을 통해 구간합을 구하는 방식이다.✅ 풀이import sysinput = sys.stdin.readlineexamp..

1. 문제 - 백준 17141 연구소 2https://www.acmicpc.net/problem/17141 💡알고리즘 - BFS, 브루트포스바이러스를 놓을 수 있는 위치에 m개의 바이러스를 넣은 모든 경우의 수 중 바이러스를 퍼뜨릴 수 있는 최소 시간을 반환한다 -> 브루트포스상하좌우 인접한 빈칸으로 복제되며, 바이러스를 퍼뜨리는 최소 시간 -> BFSfrom collections import dequefrom itertools import combinationsimport copy# 모든 빈 칸에 바이러스를 퍼뜨리는 최소시간 -> BFS# 바이러스를 놓을 수 있는 칸들에 m개의 바이러스를 놓기 -> 조합, 완전탐색n, m = map(int, input().split())board = []dx = [-..

1. 문제 - 백준 1759 암호 만들기https://www.acmicpc.net/problem/1759 💡알고리즘 - 백트래킹특정 조건(최소 한 개의 모음, 최소 2개의 자음, c개 문자들 중 길이가 l인 문자열)을 만족하는 집합을 모두 구한다는 점에서가지치기 -> 백트래킹을 유추할 수 있다.l, c = map(int, input().split())arr = sorted(list(input().split()))visited = [False] * cdef count_moeum_zaeum(str): # 최소 한 개의 모음과 2개의 자음으로 구성되어있는지 확인하기 위한 함수 moeums = ["a", "e", "i", "o", "u"] moeum = 0 zaeum = 0 for s in st..

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 = {} ..