GHY 's TechBlog

[ 백준 ] 1753번 최단경로 문제풀이 feat. 자바 JAVA 문제 문제풀이방법 이 문제의 특징을 알아보자. 1. 방향이 있는 그래프이다. 2. 시작점이 주어지고 그 점에서 다른 점으로 가는 최단 경로를 구하는 문제이다. 3. 가중치가 존재한다. ( w는 10 이하의 자연수 ) -> 가중치가 양수이고, 특정점이 주어지고 다른 점으로 가는 모든 최단 경로를 구하는 조건들을 봤을 때, 이 문제는 전형적인 다익스트라 문제이다. 생각해볼만한 것 1. Queue를 써서 풀어도 되는 것 아닌가? - Queue를 사용한다는 것은 결국 BFS 구현이 된다. - 값이 작을 때는 문제의 해는 올바른 값을 도출한다. - 하지만, 시간초과가 날 것이다. 2. visited를 꼭 써야하나? ( 방문한 노드를 체크하는 것 )..

[백준] 1655번 가운데를 말해요 문제풀이 feat.자바 JAVA 문제 문제풀이방법 문제에서 요구하는 것은 수빈이가 어떤 수를 말할 때마다 그 수들의 가운데 있는 수를 찾아서 말하는 것이다. 그렇다면 어떻게 해야할까? 1. 단순히 생각했을 때, 입력값들을 저장해놓고 정렬을 한 후에, 가운데 있는 값을 찾아주면 된다. - 하지만, N의 범위가 100,000이고, 매번 정렬을 하는 것의 시간복잡도는 O(NlogN) -> 그러므로 총 시간복잡도는 N*N*logN이 될 것이고 시간초과 다. 2. 입력한 값 중에 중간 값들을 기억하고 있으면 어떨까? - 입력한 값의 작은값을 담는 공간 하나와, 큰 값들을 담는 공간 하나, 총 2개의 공간을 만들어 놓고, 두개의 공간에는 데이터의 수가 일정하게 유지시키면서 작은 ..

[백준] 2428번 표절 문제설명 문제만 보면, 상당히 간단한 문제여서 금방 풀 수 있을 것 같았는데,, 늪에 빠져서 한참을 헤맸다ㅠㅅㅠ 문제풀이 방법 1. 두 파일을 비교하면서 i≠j이고, size(Fi) ≤ size(Fj)이면서, size(Fi) ≥ 0.9 × size(Fj) 이 조건을 만족시키는 쌍일 경우만 검사를 하면 된다. 2. 하나씩 비교해가면서 탐색해도 되지만, n의 최대 크기가 100,000 이기 때문에, n^2 탐색을 하게 되면 시간초과가 날것이다. 3. 그렇기 때문에 오름차순 정렬 후, 이분탐색을 사용해서 조건을 만족시키는 최대 값을 찾으면 된다. Example) 예를들어, 조건을 만족시키는 최대값의 index가 3이라고 가정해보자. 그렇다면, 비교해야할 index 0 을 제외하고 in..

[백준] 1068번 트리 문제 설명 입출력 문제풀이 방법 트리가 주어지고, 삭제할 노드에 연결되어 있는 노드를 모두 제거한 후 리프노드의 개수를 출력하면 된다. 1. 주어진 노드가 어떤 루트 노드와 연결되어 있는지 정보를 저장할 arr 배열 하나를 선언한다. 2. 삭제할 노드 R 을 입력받은 후 delete(R) 을 통해 R에 연결되어 있는 노드를 모두 삭제한다. - 삭제가 된 노드인지를 판별하기 위해 boolean값의 node 배열을 사용했다. - 삭제가 된 노드면 node[i]의 값을 true로 바꾸게 된다. - 삭제를 하는 방법은 BFS방법을 통해 연결된 것을 모두 지우도록 했다. 3. 삭제가 끝나면 리프노드를 찾아야 한다. - 삭제되어진 노드는 제외하고 ( 즉, node가 true인 것은 제외 )..