ayeongjin 님의 블로그

벨만-포드 알고리즘 (Bellman-Ford Algorithm) 1. 벨만-포드 알고리즘이란? 벨만-포드 알고리즘(Bellman-Ford Algorithm) 은 하나의 시작 정점(source) 으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘이다.다익스트라 알고리즘과 비슷한 목적을 가지지만, 다익스트라에서는 불가능한 음수 가중치(negative weight) 를 허용한다.따라서, 음의 간선(negative edge) 이 존재하는 그래프에서 최단 경로를 구할 때 매우 유용하다. 2. 알고리즘의 핵심 아이디어 벨만-포드는 모든 간선을 반복적으로 완화(Relaxation) 하는 알고리즘이다.Relaxation (완화):어떤 경로를 통해 더 짧은 거리로 도달할 수 있다면, 그 거리 값을 갱신하는 과정 즉,..

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 조건1. A의 이동경로 : s -> b, B의 이동경로 : s -> b2. 두 사람의 경유지가 같을 경우 같은 택시를 타며, 요금은 한 번만 지불3. 두 사람의 총 택시 요금의 최소값 출력 접근 방식일단 A와 B의 공통 경유지를 생각하자마자 플로이드 워셜로 풀어야겠다고 생각했다. 플로이드 워셜 코드 구현1. 그래프 초기화dist = [[float('inf')] * (n + 1) for _ in range(n + 1)]for i in range(1,..

https://www.acmicpc.net/problem/1406 문제 조건명령어와 커서 위치에 따라 문자열 편집L : 커서 왼쪽으로 한 칸 옮기기D : 커서 오른쪽으로 한 칸 옮기기B : 커서 왼쪽에 있는 문자 삭제P $ : 커서 왼쪽에 문자 $ 추가모든 명령어는 불가능할 경우 무시 접근 방식시간 제한이 0.3초라 무조건 시간초과가 날 거 같았지만 일단 쌩으로 구현해보고 생각해보기로했다.pop과 insert를 사용해서 먼저 구현하고, 그 후에 rotate를 사용해서 구현했다.결론은 둘 다 시간초과가 나고, 도저히 생각이 안나서 다른 블로그를 참고했다. 내가 처음에 실패한 코드는 커서를 인덱스 번호로 생각하고 실제로 해당 값을 추가하거나 삭제하는 방식으로 구현했다.블로그에서 참고한 코드는 커서를 기준으..

https://www.acmicpc.net/problem/20061 처음에 문제 이해가 안돼서 한참 다시 읽었다. 문제 조건 1. 빨간색 보드에 블록을 놓으면, 초록색 보드와 파란색 보드로 블록 이동 1-1. 초록색 보드- 열 고정된 상태로 아래방향으로 블록 떨어짐- 가로 줄이 모두 차면 제거, 위에 있는 블록은 아래로 이동- 0, 1번 행 중 블록이 있으면, 가장 아래 행부터 차례로 한 줄씩 삭제, 비원진 만큼 위에서 밀어내림 1-2. 파란색 보드- 행 고정된 상태로 오른쪽방향으로 블록 떨어짐- 세로 줄이 모두 차면 제거, 왼쪽에 있는 블록은 오른쪽으로 이동- 0, 1번 열 중 블록이 있으면, 가장 오른쪽 열부터 차례로 한 줄씩 삭제, 비워진 만큼 왼쪽에서 밀어내림 2. 주어진 사이클만큼 블록 이동..

https://www.acmicpc.net/problem/9466 문제 조건1. 사이클이 생기는 학생들만 팀 완성2. 사이클이 생기지 않는 학생은 팀 생성 불가능 접근 방법1. 1번 학생부터 시작해서 n번 학생까지 dfs를 한다 (visited 배열로 방문표시)2. 탐색 도중 이미 방문한 학생이 있을 경우, 사이클 발생2-1. 이때 사이클이 발생한 학생을 다시 찾는다2-2. ex. 1 > 2> 3> 2 로 탐색할 경우, 2번과 3번 학생 사이클 발생, 1번은 팀 이루어지지 못함 (finished 배열로 dfs가 완료되었는지 표시) 구현 1. 입력 및 결과n = int(input())students = list(map(lambda x: int(x) - 1, input().split()))visite..

https://www.acmicpc.net/problem/16946 문제 조건1. 0 : 이동 가능, 1 : 이동 불가능 (벽)2. 벽을 부수고 이동할 수 있는 곳으로 변경3. 그 위치에서 이동할 수 있는 칸의 개수 세기 정리하면 벽이 나타날때마다 그 벽을 포함해서 연결된 빈공간의 크기를 구하면 된다 접근 방법 방법 1)각각의 칸마다 bfs 실행 -> 시간초과 O((N * M) * (N * M)) = O((N*M)^2)전부 다 조건대로 구하면 되지만 그렇게 풀이하면 시간초과 난다. 방법 2)1. 처음에 한번의 bfs 전체 순회하며 각 칸의 크기 측정 (2667번 단지번호 붙이기 문제처럼 각 방의 고유번호를 측정, 고유번호는 0부터 시작)2. 방의 고유번호를 다 붙였으면 그 붙인 크기를 리스트에 추..

https://www.acmicpc.net/problem/24042 횡단보도 프로젝트를 진행하면서 이런식으로 알고리즘을 짜면 좋겠다 싶은 생각을 했는데 비슷한 문제가 있어서 풀어봤다. 문제 조건1. 교차로의 구역 : N개2. 주어진 횡단보도의 전체 주기 : M분 (M개의 연결 노드, 1분간격으로 바뀜)3. 0분에 출발해서 1번 구역에서 N번 구역까지 이동하는 최소 시간 구하기 접근 방식일단 다른 다익스트라랑 똑같이 풀되, 가중치 계산이 따로 필요하다고 생각했다.현재 시간, 현재 노드에서 이동할 수 있는 다른 연결 노드 중, 언제 출발할 수 있는지 (신호등이 언제 켜지는지) 계산이 필요했다. 알아야할 값1. 연결된 노드 중 신호등이 켜지는 시간 (기다리는 시간)2. 1에서 구한 기다리는 시간에서 현재시간..

https://www.acmicpc.net/problem/7511 리팩토링 이유알고리즘 문제를 풀면서 여러 테스트 케이스가 반복되는 문제를 풀 때 특히 가독성과 유지보수 측면, 재사용성 관점에서 코드를 클래스화하면 더 깔끔하고 독립적인 코드가 될 수 있다고 생각했다.그래서 이번에는 유니온파인드 문제를 풀이하면서 클래스로 변경해봤다. 1. 초기 구현 – 전역 변수와 함수 기반 처음에는 단순히 문제를 푸는 데 집중해서 parent, rank, find, union 전부 전역에 두고 구현했다.import sysinput = sys.stdin.readlineT = int(input())for t in range(T): print(f'Scenario {t+1}:') n = int(input()) # ..

https://www.acmicpc.net/problem/1726 문제 조건 1. 전진 명령 : 1~3칸 전진 가능2. 회전 명령 : 오른쪽 또는 왼쪽으로 90도 회전 가능3. 시작위치와 시작방향, 도착 위치와 도착 방향이 주어진다4. 몇번의 명령으로 도착지점에 도착할 수 있는지 출력 접근 방법일단 방향까지 필요한 문제이기 때문에 [세로][가로][방향]을 가지는 3차원 visited 배열을 만들어야한다.그리고 1. 전진 명령을 할 경우와 2. 회전 명령을 할 경우를 나눠서 명령시행을 반복한다.최종 도착과 맞는 위치와 방향일 경우 break 구현 1. 전진 명령# 전진for k in range(1, 4): nr, nc = cr + direction[cd][0] * k, cc + direction..

https://www.acmicpc.net/problem/17472 문제 조건1. 다리의 방향은 가로 또는 세로로만 연결 가능하다2. 방향이 가로인 다리는 다리의 양 끝이 가로방향으로 섬과 인접, 세로도 마찬가지3. 다리의 길이는 2 이상4. 다리 교차 가능5. 모든 섬이 연결하는 다리 길이의 최솟값 구하기 접근 방법 1. 섬 위치 체크BFS를 이용해 하나의 섬마다 고유 번호를 부여하고, 바다와 맞닿아 있는 가장자리 좌표를 따로 저장했다.여기까지는 다리만들기1이랑 거의 비슷하게 풀었다. 2. 섬의 가장자리만 모아둔 배열에서 다른 섬까지 한 방향으로 다리 만들어 나가기가장자리 좌표에서 상하좌우 한 방향으로 쭉 탐색하고, 다른 섬에 도달 가능한 경우 다리 후보로 저장한다.이때 다리 길이가 2 이상을 체크해..