ayeongjin 님의 블로그

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()))..

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 + dir..

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

최소 스패닝 트리 (MST)란?최소 스패닝 트리(MST, Minimum Spanning Tree)는 그래프 이론에서 중요한 개념 중 하나로, 주어진 그래프에서 모든 정점을 연결하는 트리 중에서 가중치의 합이 최소인 트리를 의미한다.간단히 말해, 각 정점들이 연결되어 있으며, 연결된 모든 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제✅ 최소 스패닝 트리의 특징트리 구조:MST는 반드시 트리 형태 (트리 : 사이클이 없는 연결된 그래프)트리의 특성상, N개의 정점이 있을 경우, 간선의 수는 항상 N-1최소 가중치:MST는 모든 간선의 가중치 합이 최소가 되어야 한다. (ex. 가중치가 의미하는 것 : 도로의 비용, 네트워크 연결의 비용 등)그래프 연결:MST는 그래프에 있는 모든 정점들을 연결해야 하므..

https://www.acmicpc.net/problem/13460 ✅ 문제 조건 1. 보드 상하좌우로 욺직여서 구슬 이동2, 빨간구슬만 빼내기3. 각 단계마다 네방향으로 기울이며 두 구슬을 동시에 이동3-1. 파란구슬이 구멍에 빠지면 실패3-2. 빨간구슬이 구멍에 빠지면 성공4. 10회 반복 후, 성공 못하면 -1 ✅ 접근 방법 # 문제 1먼저 상하좌우로 이동하며 그때마다 턴을 반복해야한다는 건 이해했지만, 두 개의 구슬이 같은 위치에 겹치면 어떻게 처리해야할지 생각하는 데 오래걸렸다.그래서 구슬의 위치와 현재 방향을 바탕으로 어떤 구슬이 먼저 움직어야하는지 계산할까 생각했지만 너무 복잡해서 포기했다.위의 방법을 고민하던 중, 어떤 구슬이 먼저 움직어야하는지 계산을 하지 말고 일단 그냥 두 개의 구슬..