Unfazed❗️🎯

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

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]는 우리가 구하고자하는..