빠르고 꾸준하게

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 징검다리

https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 이 문제를 읽고 이분 탐색인걸 알긴 알았지만 이분 탐색 카테고리에 있는 문제라 처음부터 이분 탐색으로 접근했었습니다. 이분 탐색에서 가장 중요한 부분은 어떤 값을 기준으로 왔다 갔다 이분 탐색할지 정해야 합니다. 이 문제는 구해야 하는 최댓값을 이분 탐색 기준 값(mid)으로 뒀습니다. 먼저 0과 마지막 지점인 distance(25)를 가지고 가운데..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1405(파이썬) - 미친 로봇

https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 최근 푼 문제들 유형이 그래프가 많다 보니 이 문제도 보자마자 그래프로 풀어야겠다 싶었습니다. 하지만 문제에서는 좌표가 주어지지 않았는데요, 주어지지 않으면 만들어서 풀면 됩니다! 시작점을 중심으로 동, 서, 남, 북으로 움직여서 주어진 횟수를 모두 사용해서 도달한 곳이 자신이 한 번도 방문하지 않은 좌표일 때, 확률을 더해서 구해주면 됩니다. 처음에는 '로봇의 이동 경로가 단순할 확률을 출력..

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 알고리즘을 최근 3일정도 풀지 않았더니 감이 슬슬 떨어지고 있는 것 같아 기본적인 dfs/bfs 문제를 풀어봤습니다. '가장 짧은 변환 과정' 이라는 조건을 보고 BFS를 써야된다고 생각했고, 자세한 설명은 주석을 참고해주시면 감사하겠습니다. from collections import deque # 한 번에 한개의 알파..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 2589(파이썬) - 보물섬

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 이 문제를 처음읽고 든 생각은 bfs인데 어떻게 지점간의 거리를 구하고 그 거리가 최대일 때를 구해야할까? 였습니다. 조건이 보통은 1000, 1000을 주는데 50,50 으로 준 걸 보니 완전탐색을 이용해서 각 좌표마다 bfs를 실행해주면 되겠다 라는 생각을 했고, 문제를 풀었습니다. 이 문제에서 핵심은 cnt 를 다음 bfs 좌표로 넘어갈 때, +1 씩 해줘서 현재 지점에서 bfs를 마쳤을 때 가..