Today's keyword : BFS 문제설명https://www.acmicpc.net/problem/18352이 문제는 주어진 도시와 도로의 정보를 바탕으로, 특정 거리 K에 있는 도시를 찾는 문제입니다.입력 첫 번째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 정보 X가 주어집니다. 다음 M개의 줄에는 도로 정보가 주어지며, 각 줄은 두 도시 A와 B를 나타냅니다. 이는 도시 A에서 도시 B로 가는 도로가 있음을 의미합니다.출력 특정 거리 K에 있는 도시의 번호를 오름차순으로 출력합니다. 만약 그러한 도시가 없다면 -1을 출력합니다.📌문제풀이from collections import dequeimport sys input = sys.stdin.readlineN, M, K, ..

Today's keyword : BFS/DFS 📌 문제설명https://www.acmicpc.net/problem/7562이 문제는 체스판에서 나이트가 특정 위치에서 다른 위치로 이동하는 최소 이동 횟수를 구하는 문제입니다. 나이트는 L자 형태로 이동할 수 있으며, 주어진 체스판의 크기와 시작 및 목표 위치가 주어졌을 때, 나이트가 목표 위치에 도달하기 위해 필요한 최소 이동 횟수를 계산해야 합니다.입력 첫 번째 줄에 테스트 케이스 T가 주어집니다각 테스트 케이스마다 체스판의 크기(I), 나이트의 시작 위치, 나이트의 목표 위치가 주어집니다.출력 : 각 테스트 케이스마다 나이트가 목표 위치에 도달하기 위한 최소 이동 횟수를 출력합니다. 📌 문제풀이from collections import dequeT..

Today's keyword : 그래프 이론 (BFS/DFS) 📌 문제설명https://www.acmicpc.net/problem/2644  📌 문제풀이주어진 두 노드 간의 촌수를 계산하는 문제로, 노드 간의 연결 관계를 그래프로 표현하고, 두 노드 간의 최단 경로를 찾는 것이 목표입니다. 이 문제에서 주의해야 할 점은 그래프가 비어 있거나 연결되지 않은 경우를 처리해야 합니다. 이 경우 -1을 출력해야 합니다. BFS import sysfrom collections import dequesys.setrecursionlimit(10 ** 6) # 재귀 깊이 제한 설정n = int(input())start, end = map(int, input().split())m = int(input())# 그래프..

Today's keyword : 그래프이론 문제설명https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr"모음 사전" 문제는 주어진 모음(A, E, I, O, U)으로 만들 수 있는 모든 가능한 단어를 나열된 사전에서 특정 단어의 순서를 찾는 문제입니다. 단어의 길이는 1부터 5까지이며, 중복된 단어는 허용되지 않습니다. 문제풀이문제풀이1. Product 사용 사전을 구성하는 모음이 5개로 많지 않기 때문에 product을 이용해 모든 가능한 단어를 사전으로 만들어 나열한 후, 주어진 단어의 위치를..

Today's keyword : BFS 📌 개념 설명BFS(너비 우선 탐색) BFS는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 인접한 정점들을 먼저 방문한 후, 그 정점의 인접한 정점들을 탐색하는 방식입니다. 즉, "너비"를 우선적으로 탐색합니다.BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 큐는 FIFO(First In First Out) 방식으로 작동하여, 먼저 들어온 정점이 먼저 나가게 됩니다. 📌 문제 설명https://www.acmicpc.net/problem/24444이 문제는 주어진 그래프에서 너비 우선 탐색(BFS)을 수행하고, 각 정점의 방문 순서를 출력하는 문제입니다.입력첫 번째 줄에 정점의 수 n, 간선의 수 m, 시작 정점 r이 주어집니다.다음 m개의 줄에는 간..

Today's keyword : DFS  DFS(깊이 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 가능한 깊게 노드를 탐색한 후, 더 이상 갈 수 없게 되면 마지막 분기점으로 돌아가서 다른 경로를 탐색하는 방식입니다. DFS는 스택을 사용하여 구현할 수 있으며, 재귀적으로도 구현할 수 있습니다. 문제 설명https://www.acmicpc.net/problem/24479백준의 "DFS와 BFS" 문제(문제 번호: 24479)는 그래프 탐색 알고리즘 중 깊이 우선 탐색(DFS)을 구현하는 문제입니다. 주어진 그래프에서 특정 시작 정점으로부터의 방문 순서를 출력하는 것이 목표입니다.입력첫 번째 줄에 정점의 수 n, 간선의 수 m, 시작 정점 r이 주어집니다.다음 m개의 줄에는 간선 정보가 주어지며, 각 ..

Today's keyword : 이진탐색 문제설명특정 수의 심사관이 대기자들을 처리할 수 있는 최소 처리 시간을 찾는 문제입니다. 각 심사관마다 한 사람을 처리하는 데 걸리는 시간이 다릅니다. https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제풀이이 문제에서 이진탐색을 위한 조건은 대기자 수를 기준으로 합니다. 주어진 정보가 대기자 수이고, 구해야 하는 값은 모든 대기자 수를 처리하는 시간으로 ' 대기자 수'라는 기준에 맞춰 주어진 mid와 times를 이용해..

Today's keyword : 이진탐색  문제설명주어진 징검다리의 개수에 따라 건너야 하는 수를 최적화하는 문제로, 주어진 징검다리의 개수 n이 있을 때, 1부터 n까지의 수 중에서 가장 많이 건널 수 있는 수를 찾는 것이 목표https://www.acmicpc.net/problem/11561문제풀이이 문제에서 포인트는 두 번째 점프부터는 이전의 점프한 거리보다  1 이상 긴 거리를 뛰어야 한다는 것이다. 최대 징검다리 수를 출력한다고 하면 가장 이상적인 점프 방식은 처음에 한 칸 뛰고, 그 다음 두 칸 뛰고, 그 다음 세 칸 뛰는 식으로 점프하는 거리를 한 칸씩 늘리는 것이다. 징검다리를 건너기 위한 최소한의 수는 한 칸씩 점프 이동거리를 늘린 거리의 합이기 때문에 수식으로 작성하면 N*(N+1)/2..

Today's keyword : 이진탐색 이진탐색이란?   정렬된 배열에서 특정 값을 찾기 위해 반으로 나누면서 탐색해 나가는 알고리즘입니다. 이 방법은 배열이 정렬되어 있어야 사용 가능합니다. 이진탐색 작동원리 1. 초기 설정 : 배열의 시작과 끝 인덱스를 설정 2. 중간 인덱스 계산 : 시작 인덱스와 중간 인덱스 계산 3. 비교 중간 인덱스의 값이 찾고자 하는 값과 같으면 탐색 종료 중간 인덱스의 값이 찾고자 하는 값보다 크면, 끝 인덱스를 중간 인덱스 - 1로 설정하여 왼쪽 절반을 탐색중간 인덱스의 값이 찾고자 하는 값보다 작으면, 시작 인덱스를 중간 인덱스 + 1로 설정하여 오른쪽 절반을 탐색4. 반복 : 절반으로 나누면서 시작 인덱스가 끝 인덱스 초과할 때까지 반복 문제설명 형택이가 게임을 몇 ..

이번에 소개해드릴 내용은 시계열이나 신호 데이터에서 변화를 찾는 기법인 Change point detection입니다. 진행했던 프로젝트에서 공정 과정에서 유의미한 피처를 도출하기 위한 하나의 작업으로 Segmentation을 진행했고, Segmentation을 하기 위해 Change point detection 기법을 활용했습니다. 최종 목표는 유의미한 피처 도출이었고, 데이터의 변화가 발생한 구간을 나눠 보다 유의미한 피처를 도출하고자 하였습니다. 해당 글에서는 Change point detection 이 무엇인지, 어떻게 활용되는지, 알고리즘에는 어떤 것들이 있는지 간단한 실습과 함께 설명하고자 합니다. 1. CPD 개요  CPD(Change Point Detection)이란 시계열 데이터의 특성(..