genie0000 님의 블로그

💻 프로그래머스 - 게임 맵 최단거리 👉 문제 보러 가기 🧩 문제 설명 🧩문제 요약2차원 게임 맵에서 (0, 0) 위치에서 출발하여 (n-1, m-1) 목표 지점으로 이동해야 합니다.이동은 상하좌우 네 방향으로만 가능하며,1: 이동할 수 있는 칸0: 벽이어서 이동할 수 없는 칸입니다.이때, 캐릭터가 최단 거리로 목표 지점까지 도달할 수 있는 거리를 반환해야 하며,도달할 수 없는 경우에는 -1을 반환합니다.출발 지점: (0, 0)도착 지점: (n-1, m-1)맵 크기: n x m이동 방향: 상, 하, 좌, 우갈 수 있는 칸: 1벽: 0최단 거리 반환 (못 가면 -1) 🔍 BFS (너비 우선 탐색) 풀이from collections import dequedef solution(maps): ..

💻 프로그래머스 - 여행경로 문제 👉 문제 보러 가기 🧩 문제 접근 방식이 문제는 다음 조건을 만족하는 경로를 찾는 그래프 탐색 문제입니다.항상 "ICN" 공항에서 출발해야 한다.주어진 항공권을 모두 사용해야 한다.가능한 경로가 여러 개일 경우, 알파벳 순으로 가장 앞선 경로를 반환해야 한다. → 따라서 모든 가능한 경로를 탐색하고, 사전 순 정렬이 필요합니다. 🔍 DFS (깊이 우선 탐색)def solution(tickets): answer = [] tickets.sort() # 티켓이 사용됐는지를 나타내는 리스트 used = [False] * len(tickets) # DFS함수로 현재 경로(route)와 사용한 티켓 수(depth)를 인자로 받는다. d..

💻 프로그래머스 - [카카오 인턴] 보석 쇼핑 문제 👉 문제 보러 가기 🧩 문제 접근 방식이 문제는 모든 보석 종류를 포함하는 가장 짧은 구간을 찾는 것이 핵심입니다.이를 효율적으로 해결하기 위해 슬라이딩 윈도우와 투 포인터라는 알고리즘 개념을 사용했습니다. 🔸 슬라이딩 윈도우 란?연속된 구간을 다루는 문제에서 효율적으로 접근하기 위한 기법입니다.구간의 시작과 끝을 조절하며(한 포인터는 구간 확장, 다른 포인터는 구간 축소) 탐색합니다.이 방식은 구간의 크기를 유동적으로 변경할 수 있어, 반복되는 부분을 최소화하고 효율적으로 문제를 해결할 수 있습니다.🔸 투 포인터 란?정렬된 배열이나 부분 구간 문제에서 주로 활용되는 방식입니다.서로 다른 위치에서 시작하는 두 포인터가 조건에 맞게 이동하면서 ..

💻 프로그래머스 - 단어 변환 문제 👉 문제 보러 가기 🧩 문제 접근 방식두 단어가 서로 한 글자만 다른 경우에만 변환이 가능하다는 조건이 주어져 있기 때문에 단어 간 연결 관계를 그래프로 보고, 시작 단어에서 목표 단어까지의 경로를 탐색하는 문제로 해석할 수 있습니다.이러한 경로 탐색 문제를 해결하기 위해 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 방식으로 접근했습니다. 🔍 DFS (깊이 우선 탐색)DFS는 한 방향으로 계속 깊게 탐색하다가 더 이상 갈 곳이 없으면 되돌아가서 다른 경로를 탐색하는 방식입니다.보통 재귀 함수를 통해 구현되며, 모든 경우의 수를 확인할 때 유용하게 사용이 됩니다.def solution(begin, target, words): # min_steps는 ..