ayeongjin 님의 블로그

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에서 구한 기다리는 시간에서 ..

📚 자바스크립트의 Map과 Object알고리즘 문제를 풀이하다 Map과 Object의 차이에 대해 궁금해져서 둘을 비교하고, 언제 어떤 걸 써야 할지 정리해봤다. ✅ 1. 키(Key)의 타입 구분ObjectMap허용되는 키 타입문자열(String), 심볼(Symbol)모든 값 (숫자, 객체, 함수 등 포함) const map = new Map();map.set(1, "number");map.set("1", "string");console.log(map.get(1)); // "number"console.log(map.get("1")); // "string"const obj = {};obj[1] = "number";obj["1"] = "string";console.log(obj[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..

👩‍🏭 게시물 리스트 무한 스크롤 (throttle 적용) 1. 작업 배경 프로젝트에서 피드 리스트(FeedList)를 무한 스크롤 방식으로 구현하고 있었다.사용자가 스크롤을 내리면 마지막 요소를 감지해 fetchNextPage를 호출하고, 새로운 데이터를 불러오는 구조였다.하지만 개발 과정 중 테스트를 하면서 스크롤을 빠르게 내릴 때 API 요청이 과도하게 중복 호출되는 현상을 발견했다.이는불필요한 서버 트래픽 증가클라이언트 성능 저하UX 부드러움 감소등 여러 문제를 초래할 수 있음을 인지하게 됐다.특히 모바일 환경처럼 빠른 스크롤이 빈번한 상황에서는 이 문제가 더욱 두드러질 수 있었다.이 문제를 해결하기 위해 IntersectionObserver + fetchNextPage 호출을 제어할 수 있는..

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는 그래프에 있는 모든 정점들을 연결해야 하므..