Unfazed❗️🎯

문제 링크https://leetcode.com/problems/invert-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150 문제 입출력입력: 이진 트리의 루트(root) 노드출력: 각 노드의 자식 좌우를 뒤바꾼 이진 트리의 루트 노드모든 노드의 왼쪽 자식과 오른쪽 자식을 서로 교환하면 되는 문제다. 단순하게 모든 노드를 순회하면서 해당 노드의 자식들을 swap하면 되는데, 문제를 푸는 과정에서 재귀적으로 계속 swap해주면 되겠다는 것은 알았지만 재귀 호출 순서를 깊게 상상하면서 구현하는데 삽질을 해서 느낀 바를 정리해보려고 한다. 예시     4   /   \  2     7 / \     / \1   3 6   9 재귀 호..

https://www.acmicpc.net/problem/1083 접근 방법 : 그리디하게 각 위치에서 현재 범위 내 가장 큰 값을 앞으로 이동시킨다.- S의 제한 때문에, 가능한 교환 횟수(j - i  두 원소 교환 과정 :현재 위치 i 에서 i+1부터 i+S범위 내에서 가장 큰 값을 찾는다.해당 값을 i로 이동시키기 위해 인접 원소 간 교환을 반복한다. (버블 소트와 유사)값을 이동 시키는 데 사용한 교환 횟수만큼 S를 감소시킨다.종료 조건 : S가 0이 되거나, 배열을 끝까지 탐색했을 경우 종료 핵심 코드 S 제한 내에서 가장 왼쪽 자리부터 최대 값으로 채워주는 것에 집중한다.매 반복 마다 S-=(maxIndex - i); 로 교환한 횟수만큼 S를 감소시켜준다.private static void s..

https://www.acmicpc.net/problem/2665  접근 방법  이 문제는 다익스트라 알고리즘을 활용하여 풀 수 있다. 여기서는 각 방을 노드로 보고, 검은 방에서 흰 방으로 변경하는 작업을 가중치로 간주해 최소 변경 횟수 경로를 구한다. 최단 경로가 아닌 '최소 변경 횟수'를 찾는다는 점이 일반적인 다익스트라 알고리즘과의 차이다. 시작부터 끝방까지 가는 동안 검은 방(0)을 최소로 지나야 한다.즉 흰 방(1)을 지나갈 때는 비용이 발생하지 않고 검은 방(0)을 거칠 때는 비용이 1 만큼 발생한다고 간주하고, 시작부터 끝방까지 BFS를 진행하여 최소 비용으로 끝방에 도착하는 경우를 구하면 된다. 우선순위 큐(PriorityQueue)를 사용해 현재 변경 횟수가 가장 적은 경로부터 탐색한다..

https://www.acmicpc.net/problem/1461 내 접근 방식예제 입력 3개를 직접 손으로 풀어보았고 예제 출력에 대한 답을 올바르게 구할 수 있어 이를 코드로 구현하였다.손 풀이 접근1. 0의 위치에 책이 모아져 있으므로 0을 기준으로 음수 쪽에 놓아야 될 책들과 양수 쪽에 놓아야 될 책들로 분류됨.2. 이를 위해 우선 주어진 책의 위치를 오름차순으로 정렬.=> 이 부분에서 어떻게 책을 옮기는 방법에 대해 고민했는데,그냥 M씩들어서 놓고 0으로 돌아가는 것을 반복하는 방법은 최소가 아님을 확인했다.  더 효율적인 방법을 생각하다 0에 있는 책을 M개를 들어 바로 옆 위치로 모두 이동시키고, 해당 위치에 놓일 책을 제외하고 다시 M개씩 들어 모두 그 다음 위치로 이동시키는 방식을 생각했..

https://www.acmicpc.net/problem/1253 접근 방법투포인터를 사용하여 두 수의 합을 구하고 그 합이 타겟과 일치하는지를 확인이를 위해 배열의 정렬이 선행되어야 함Arrays.sort(arr);int count = 0;for(int i=0; i 배열 정렬 이후 해당 타겟 넘버가 배열 내의 두수의 합으로 만들 수 있는 수(좋은 수)인지 확인하는 isGoodNumber(int target, int target_idx) 메서드를 호출하고 좋은 수일 경우(true) count++하여 좋은 수의 개수를 구한다. isGoodNumber 메서드 구현단순히 배열 내의 두 수가 배열 내의 타겟 값과 일치하는 지만 확인한다면, 두수의 합이 타겟 값과 같은 경우 return true, 타겟 값 보다 ..

https://school.programmers.co.kr/learn/courses/30/lessons/77486 문제 개요다단계 판매 조직에서 각 판매원의 이익을 계산하는 알고리즘을 구현하는 것이 목표였다.주요 규칙은 아래와 같다.판매원이 발생시킨 이익의 10%를 추천인에게 분배(1원 미만은 분배하지 않음)나머지는 자신이 가짐이 과정이 재귀적으로 상위 추천인에게도 적용됨처음 시도한 방법class Node { String name; Node parent; int income; }처음에는 트리 구조를 구현하기 위해 Node 클래스를 만들어 문제해결을 시도해보았다.각 판매원을 노드로 생성하고 포인터로 연결하는 구조를 생각했지만판매원 검색과 수익 갱신 과정에 있어서 성능이 좋지 않다는 것을..

https://www.acmicpc.net/problem/1240  이 문제는 트리에서 두 노드 간의 거리를 구하는 문제로, BFS(너비 우선 탐색)를 활용하여 해결할 수 있었다.  접근 방식인접 리스트를 사용하여 트리를 표현양방향 간선으로 처리 (트리는 양쪽으로 이동 가능)Edge 클래스를 정의하여 목적지 노드와 가중치 정보를 함께 저장static class Edge { int to; int weight; public Edge(int to, int weight) { this.to = to; this.weight = weight; }} BFS를 이용한 거리 계산 시작 노드부터 BFS를 수행하여 각 노드까지의 거리를 계산distance 배열을 사용하여 각 노드..

https://www.acmicpc.net/problem/2458 접근 방법 첫접근(실패)문제 유형을 보지 않고 풀어보았을 때 일차원 테이블을 만들고관계가 주어질 때, a > b인 경우, 배열에서 b보다 큰 학생 수를 a의 위치에 누적하여 기록만약 이미 누적된 값이 크다면 해당 관계는 무시함배열의 최종 값이 유일(unique)하다면, 해당 학생의 순위를 알 수 있다.하지만 이 방법은 간접 관계 확인 불가 등의 이유로 실제 순위를 보장하기 충분하지 않았다. 첫번째 방법(플로이드-워셜) 문제 유형이 플로이드-워셜인 것을 확인한 뒤 풀어보았다.처음엔 int[] 배열로 풀이했다가 자신보다 큰 사람을 true로 체크하는 boolean[] 배열로 바꾸어서 코드를 더 간결하게 바꿀 수 있었다.int N = Integ..

https://www.acmicpc.net/problem/2457 접근 방법 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어있어야 하므로 꽃 피는 날짜 중 하나는 3월 1일 이하, 지는 날짜 중 하나는 무조건 12월 이상이어야 한다.3월 1일 이하 날짜에 피는 꽃들 중 어떤 꽃을 골라야 될지 생각해보면, 그 중에서는 무조건 가장 늦게 지는 꽃을 고르는 것이 꽃들의 수를 가능한 적게 하는 조건을 만족시키기 유리하다. 그렇게 처음 선택할 꽃을 선정했다면, 그 선택된 꽃의 지는 날짜를 기준으로 다음 선택될 꽃을 선정하면 될 것이다.구간을 겹칠 수 있게 뽑되, 지는 날짜가 긴 꽃을 선택. 과정을 반복하며 카운트를 하고, 지는 날짜가 12월 이상인 꽃을 선택했을 때 반복을 종료하고 카운트를 출력한다..

https://www.acmicpc.net/problem/1865 이번 문제는 알고리즘 분류 힌트를 보고 벨만-포드 알고리즘을 추가적으로 학습한 뒤에 풀어보았다. 아직 어렵게 느껴지는 문제여서 내가 풀면서 놓치고 있었거나 새롭게 알게 된 포인트들을 간단히 정리해 보려고 한다. 양방향 도로 처리처음 내 코드에서는 도로를 단방향으로만 처리하고 있었다. 도로는 양방향이기 때문에 도로를 추가할 땐, 양쪽 방향 모두 추가해야 한다.for (int i = 0; i  일반적인 벨만-포드에서 INF를 사용하는 이유Arrays.fill(dist, INF);dist[start] = 0;보통 "특정 시작점으로부터의 최단 거리"를 구할 때 매우 큰 값(INF)을 dist 배열에 넣고 사용한다.시작점으로부터 아직 방문하지 않은..