Unfazed❗️🎯

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 배열에 넣고 사용한다.시작점으로부터 아직 방문하지 않은..

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다.다양한 문제 상황 - 한 지점에서 다른 한 지점까지의 최단 경로 - 한 지점에서 다른 모든 지점까지의 최단 경로 - 모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현지점 간 연결된 도로는 그래프에서 간선으로 표현 다양한 문제 상황 중 한 지점에서 다른 모든 지점까지의 최단 경로를 계산하는 상황은 다익스트라 최단 경로 알고리즘을 적용하여 해결할 수 있다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. - 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않기 때문에 이러한 상황에 다익스트라 알고리즘을 적용해 볼 수 있다.다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. - ..

https://www.acmicpc.net/problem/2660 접근 방식 :"다른 회원들과 가까우 정도", "친구의 친구" 등의 부분을 읽었을 때, 스터디 1, 2일차에 학습했던 플로이드워셜 알고리즘을 적용해야 된다는 것이 바로 느껴졌다. 어느 회원의 점수가 n점이면 다른모든 회원이 친구이거나, ... , [친구의]*(n-1) 친구임을 말한다고 이해했고, 즉 n점이면 최적의 관계를 구했을 때 해당 회원으로 부터 가장 멀리 떨어져 있는 회원은 n-1개의 다른 친구(노드들)을 거쳐서 연결된다는 의미로 해석했다. 각 노드에서 다른 노드들로의 최적의 경로를 구한뒤,각 노드에서 가장 멀리 떨어져있는 노드와의 간선 수가 그 노드의 점수가 된다. 이렇게 문제를 해석하니 백준 1389 케빈 베이컨의 6단계 법칙과 ..

https://www.acmicpc.net/problem/1389 첫 접근 방식(실패)플로이드 워셜 알고리즘을 적용할 수 있을 것 같은 느낌이 들었지만 이를 구현하기 막막해 브루트포스 방식으로 풀어보았고 결과는 역시 실패였다. 대략 아래와 같은 방식으로 접근했었다. 1. 모든 가능한 노드 쌍 (i, j)에 대해 반복하며 연결 찾기2. searchMin 함수를 통한 탐색3. 각 연결되지 않은 노드 쌍에 대해 searchMin 함수를 호출하여 중간 노드 찾기4. 모든 가능한 경로를 탐색하고 최소값을 갱신 예제 입력과 출력은 올바르게 나올 수 있었지만 시간 초과 등의 문제로 실패하였다.  다시 플로이드 워셜 학습하고 풀이한 내용을 정리해 본다.내가 브루트포스 방식으로 접근했을때도 결국 연결되지 않은 유저 쌍을..

https://www.acmicpc.net/problem/11403 접근 방식  우선 정점 i에서 j로 가는 길이가 양수인 경로의 의미를 이해하려 해보았다.그래프 G에서 정점 (i,j)는  i에서 j로 가는 간선의 유무를 나타낸다.그래프 G의 정점(i,j)는 노드 i에서 노드 j로 직접 연결된 간선이 있어야 1이 되는 반면, 정점 i에서 j로 가는 길이가 양수인 경로는 노드 i에서 1개 이상의 간선을 거쳐 노드 j로 도달할 수 있는지에 주목한다.노드 1과 노드 2 사이에 직접 연결된 간선이 없어도 노드 1 => (노드 x1 => ... => 노드 xn) => 노드 2 와 같이 연결될 수 있다면 (노드 1, 노드 2)은 1인 경우가 된다. 기본적으로 그래프 G에서 1인 G[i][j]는 우리가 구하고자하는..

두 값의 차이의 절대값이 서로 같은 경우 수학에서는 |a - b| = |c - d| 와 같이 표현한다.해당 개념을 잘 숙지하고 있으면 아래와 같이 다양한 상황에서 이 개념을 활용할 수 있다. 1. 기하학적 관계 파악예: N-Queen 문제에서 대각선 관계 확인응용: 격자 기반 게임, 경로 찾기 알고리즘위의 그림과 같이 행간 차이와 열간 차이가 동일한 경우 점 A, 점 B는 동일 대각선상에 놓인다는 것을 알 수 있다.해당 경우를 N-queen 문제에서 대각선상에 말이 놓이는 경우의 예외를 처리할 때 사용할 수 있다.ex ) if(Math.abs(x2 - x1) == Math.abs(y2 - y1))  A* 알고리즘에서 대각선 이동 비용 계산로봇 내비게이션에서 장애물 회피 경로 계산 double calcul..

https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/문제는 위 링크 참조 해당 문제를 처음 접근 했을 때 객체를 교환하는 것은 너무 복잡해 보여 값만 교환하는 방식으로 문제를 해결할 수 있었다.이후 직접 객체를 교환하는 방식을 학습해보았다.  풀이 요약1. 에지 케이스 처리: 리스트가 비어있거나 하나의 노드만 있는 경우 그대로 반환2. dummy 노드를 생성하여 head 노드 교환을 처리3. 4개의 포인터 사용 : prevFirst, first, prevSecond, second (각각 교환할 두 노드와 그 직전 노드들을 가리킨다.)4. 앞에서 k번째 노드(first)와 직전 노드(prevFirst) 찾기5. 뒤에서 k번째 ..