Redddy's Devlog

🧩문제 해석 F = 스타트링크 건물 층의 총 계수 S = 현재 강호의 위치 G = 스타트링크의 위치 U = 위로 올라가는 엘레베이터 층의 간격 D = 아래로 내려가는 엘레베이터 층의 간격 위 사항들이 주어졌을 때, 현재 강호의 위치에서 스타트링크의 위치로 엘레베이터로 가려 할 때, 누른 버튼의 최소값을 출력하는 문제이다. 만약 도달할 수 없다면, 계단 이용하라는 문장을 출력한다. 모든 층을 돌아다닐 필요가 없고 목표층에 도달하면 엘레베이터를 멈추면 되니까 BFS가 효율적이다. 📕 풀이 BFS로 풀었다. 이동할 수 있는 층은 [현재 위치 + U, 현재 위치 -D] 를 통해 유추하였고, 이 데이터가 F 안에 있고, 방문한 적이 없다면, 그 층으로 방문하였다. 💻 코드 from collections impor..

🧩문제 해석 체스 판의 크기와 현재 나이트의 위치 그리고 목표 위치가 주어졌을 때 최소 이동 횟수를 출력하는 프로그램! 📕 풀이 나이트의 이동 가능 경로는 다음과 아래의 그림과 같다. 최소 이동 횟수를 구하려면 이전에 방문 했던 곳은 지양한다. 그리고 체스판에서 벗어나는 위치도 제외한다. 이 두가지를 지키면서 BFS 탐색을 하였다. 칸을 모두 방문하는 것이 아니라 목표 위치에 도달하면 탐색을 멈출 것이기에 DFS 보다 BFS가 더 효율적이다. 💻 코드 import sys from collections import deque input = sys.stdin.readline # 나이트 이동 경로 dx = [-2,-1,1,2,2,1,-1,-2] dy = [1,2,2,1,-1,-2,-2,-1] def bfs()..

🧩문제 해석 이제 이런 문제들을 딱 보면 그래프 관련 문제라는 걸 바로 알아차릴 수 있게 되었다. '빙산 한 덩이가 주어졌을 때'가 조건에 들어가있으니, 무조건 빙산은 주어진다. 그러면 이제 빙산에서 얼음의 위치와 그 얼음 주위 환경을 살피면 된다. 그리고 빙산이 쪼개졌는지 BFS를 통해 확인한다. 🔉 풀이 전 잡담 앞서 말한 문제 해석을 알고리즘으로 구현해내는데에는 성공했다. 첫번째 제출에는 런타임 에러(RecursionError)가 발생했다. 이는 재귀함수가 너무 깊이 들어갈 경우 발생한다. 이땐 당황하지 말고 sys 모듈을 불러와 sys.setrecursionlimit(n) 을 적어주면 된다. 여기서 n은 최대 깊이를 의미한다. sys.setrecursionlimit(10**4) 을 넣어줌으로써 런..

🧩문제 해석 떡 하나 주면 안잡아 먹지!~ 에서 아이디어를 얻은 문제 같다 ㅋㅎㅎ 문제가 재밌었다. 호랑이가 오늘 먹을 떡의 갯수는 1일전하고 2일전에 얻은 떡을 더한 갯수이다. 이 글을 보면 바로 피보나치 수열이라는 것을 눈치챘을 것이다. n번째 날 먹은 떡에 갯수 k가 주어졌을 때 첫째날하고 둘째날에 먹은 떡에 갯수를 출력하는 문제이다. 📕 풀이 피보나치라는 것을 파악하자 문제 풀기는 쉬워졌다. 첫째날에 먹은 떡의 갯수가 a, 둘째날에 먹은 떡의 갯수를 b라고 할 때 아래의 표를 살펴보자. 날짜 1 2 3 4 5 6 떡의 갯수 a b a+b a+2b 2a+3b 3a+5b 첫째날에는 a개, 둘째날에는 b개, 셋째날에는 첫째날과 둘째날을 더한 a+b개를 먹었다. 그리고 네째날에는 둘째날과 셋째날을 더한 ..

정렬 (Sorting) 정렬은 데이터를 특정한 기준에 따라서 순차적으로 나열하는 것이다. 흔히 사용하는 내림차순이나 오름차순 역시 이 정렬을 통해 이루어진다. 이진탐색이라는 탐색기법은 정렬과정을 거친 후에만 사용이 가능하다. 정렬알고리즘은 Comparison Sorting Algorithm(비교방식 알고리즘)과 non - Comparison Sorting Algorithm 이렇게 크게 두가지로 나눌 수 있다. 비교방식 알고리즘에는 선택정렬, 삽입정렬, 퀵정렬 등이 있고, non-비교방식 알고리즘에는 계수 정렬이 있다. 선택 정렬 (Seletion Sort) 선택 정렬은 배열에서 가장 작은 데이터를 선택하여 다른 데이터와 자리를 바꾸는 알고리즘이다. 일반적으로 쉽게 떠올릴 수 있다. 정렬되지 않은 배열에서..

🧩문제 해석 갖고 랜선들을 k개의 같은 길이의 랜선으로 자르되, 자른 랜선쪼가리들은 다시 사용할 수 없다. 이때 만들 수 있는 최대 길이의 랜선을 구하는 문제이다. 📕 풀이 숫자 범위가 심상치 않다. 갖고 있는 랜선의 수가 백만개이고, 랜선이 길이는 2^31-1 보다 작은 자연수이다.ㅎ 일반적으로 접근했다가는 시간초과날 것이 분명하다. 이 문제는 이분탐색으로 풀어야 한다. 첫번째 아이디어! 가지고 있는 랜선중 최소값을 찾는다. 최소값 랜선을 end 값에 두고 이분탐색을 한다. 탐색 값들을 리스트에 저장하고, 최종적으로 그 리스트의 최대값을 출력한다. 최소값랜선을 end 값에 둔 이유는 최대값랜선을 end 값에 둔다 하여도 결국에는 최소값랜선에 올 것이라고 생각했다. 물론 맞는 말이긴 하다. 그러나 생각하..

🧩문제 해석 채팅방에서 사용한 임티갯수를 출력하면 되는 문제였다. 사람들은 새로운 사람이 들어왔을 때 임티를 사용하고 그 다음은 일반 대화를 이어나간다. 즉, 새로운 들어왔을 때 사용한 임티 갯수를 전부 더해주면 되는 문제이다. 📕 풀이 dict() 자료형을 사용하여 문제를 풀었다. 새로운 사람이 들어오면 dict()의 값들을 리셋해주었다. 💻 코드 import sys input = sys.stdin.readline cnt = 0 # 임티갯수 변수 user = {} # 이름과 임티사용을 확인할 변수 for i in range(int(input().rstrip())): # 채팅방의 기록수만큼 for문을 돌린다 # 채팅내용입력받음 s = input().rstrip() # 새로운 사람이 들어왔을때 if s =..

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다. DFS DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다. DFS의 탐색과정은 다음과 같다. 탐색 시작 노드를 스택에 넣고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복..

그래프 : Graph DFS나 BFS는 모두 그래프 순회 알고리즘, 그래프 탐색 알고리즘이다. 그렇다면 그래프에 대해서 자세히 짚고 넘어가자. 우선 알고리즘에서의 그래프는 우리가 흔히 사용했던 막대그래프나 주식그래프 같은 형태가 아니다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 노드와 노드가 간선으로 연결되어 있다면 두 노드는 인접해있다고 한다. 그래프 탐색은 하나의 노드를 시작으로 인접한 노드를 방문하는 것을 말한다. 그래프를 표현하는 방법은 크게 두가지가 있다. 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하..

😀 서론 DFS를 제대로 다뤄보지 못하여 오늘부터 DFS, BFS 문제 하나씩은 풀 예정이다! 그래서 도전해본 문제는 "바이러스" 전에 스터디때 도전하였다가 실패한 문제이다. 그때는 DFS와 BFS의 개념을 잘 몰랐기에 실패하였으나, 이제는 다르다!ㅎㅎ 📕 풀이 주어진 컴퓨터의 수로 리스트 컴프리헨션으로 그래프를 만들고 그 후에 주어지는 인풋 값을 각자 위치에 넣어준 뒤 DFS를 돌렸다. 💻 코드 import sys input = sys.stdin.readline # dfs 정의 def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited) com = int(input().rs..