빠르고 꾸준하게

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

[백준] 22116(파이썬) - 창영이와 퇴근

https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 이 문제를 보고 처음 든 생각은 '이분 탐색을 사용해야 하고, 그래프를 사용해야겠다'였습니다. 이분 탐색을 어떻게 구현해야 할지 생각하다가 일단 mid, 기준값을 문제에서 요구하는 최대 경사의 최솟값으로 정하고 문제를 풀었습니다. 처음에 DFS라고 생각하고 풀다가 오히려 시간이 더 오래걸릴 것 같아서 BFS로 풀었고, BFS개념에 이분탐색을 실행하면서 구하는 기준값, mid를 적용시켜주기만 하면 됩니다. *수정 : dfs로 구현을 성공했으나 제출했을 때 1000 * 1000 메모리 초과가 발생합니다. 친구의 설명을..

자료구조 & 알고리즘/프로그래머스(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 # 한 번에 한개의 알파..