BOJ

문제 나무 위의 벌레 트리의 지름 개념 트리에서 가장 멀리 떨어진 정점 사이의 거리는 임의의 점 x, x에서 가장 먼 거리에 있는 정점 y, y와 가장 먼 거리에 있는 정점 z라 할 때 y와 z사이의 거리와 같다. 증명 트리 내에서 거리가 가장 먼 두 정점을 u와 v, 임의의 정점 x에서 가장 멀리 떨어진 점을 y라 할 때 가능한 경우는 아래와 같다....

문제 가장 긴 증가하는 부분 수열 4 알고리즘 각 인덱스까지 이어지는 수열의 최장길이(LIS)를 저장하는 DP를 생성 LIS를 기준으로 DP를 역추적해 수열(stack)을 생성

문제 색상환 알고리즘 N개의 색 중 K개를 선택하는 DP선택하는 색를 완성하는 걸 목표로 한다. 선택하는 색의 수가 N 미만인 경우(i<N, j<=K) 2-1. i번 째 색을 선택하지 않는 경우, 인접한 색을 선택한 경우의 수와 동일 (DPi-1) 2-2. i번 째 색을 선택하는 경우, 인접한 색을 선택하지 않고 j-1개의 색을 선택한 경우의 수와 동일(...

문제 빙산 알고리즘 BFS로 iceMap 탐색, iceMap 전체를 탐색할 때마다 age를 +1 높이가 0인 좌표는 age, 이외는 age+1로 방문 표시 높이가 0보다 큰 좌표(ice)를 iceberg에 저장 0과 이웃한 좌표를 녹이는 과정에서 0이 된 좌표의 수(melted)를 기록 iceberg의 크기와 melted로 빙산의 전체 크기를 계산 (i...

문제 구슬 탈출 2 알고리즘 붉은색 공과 푸른색 공의 이동을 방향별 BFS로 탐색 길을 제외한 모든 요소(벽, 공, 홀)에 막히는 로직으로 이동거리 보정 4차원 배열(intNN)로 두 공의 방문을 한 번에 기록 (비트마스크랑 비슷) 현재 공의 위치는 다음 시도에 영향을 주기에, 보드를 매 시도마다 이전 상태로 초기화 코드 후기 로직 자체는 복잡한 점...

2048(EASY)블록들이 특정 방향으로 보드의 끝까지 이동하는 함수를 구현 (void flow)방향에 맞춰 인덱스를 조절해 상하좌우 움직임과 블록의 병합 구현 (void slide)DFS로 5회까지 이동하는 모든 경우의 수를 탐색 (void play)5회 이동을 마친

Flood Fill이란? > > 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘 > 주로 그림 프로그램에서 특정 영역에 "채우기" 도구에 사용 > DFS(재귀함수) 혹은 BFS(Queue)를 활용해 구현 > from. wiki 알고리즘 >1. x 또는 y가 범

백조의 호수백조의 움직임과 얼음의 상태 변화 로직을 분리 (moveSwan, melting)moveSwan()2-1. 백조 중 하나의 좌표를 swim(queue)에 삽입2-2. 물의 좌표를 swim에 삽입하며 BFS 진행2-3. 얼음을 만나면 nextSwim(queue

보석 도둑보석과 가방을 오름차순으로 정렬가방을 기준으로 탐색을 진행priority_queue에 보석을 넣으며 가방 별로 넣을 수 있는 가장 높은 밸류를 구함3에서 구한 값들을 더함처음으로 막혔던 그리디 문제.가방과 보석을 구분해서 탐색하는 발상까지는 도달했지만그 기준점

소수의 연속합소수를 찾는 빠르고 쉬운 방법고대 그리스의 수학자 에라토스테네스가 발견2부터 소수를 구하고자 하는 구간의 모든 수를 나열나열한 수를 순차적으로 탐색하며 자신을 제외한 배수를 모두 지움2의 과정에서 탐색된 수는 더이상 탐색 x2~3 과정을 반복하면 소수만 남