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개의 공간을 만들어 놓고, 두개의 공간에는 데이터의 수가 일정하게 유지시키면서 작은 ..

ACM Craft 문제풀이 방법 feat. 자바 문제 알아야 할 알고리즘 지식 위상정렬(Topological_Sort) 간단하게 말하자면, 방향이 있는 그래프를 정렬하는 것이다. 전후관계가 분명한 문제에서 방향이 있을 경우, 어떤 것이 먼저 사용될 수 있는지를 파악하여 문제를 풀어나가는 알고리즘이다. 추후, 위상정렬에 관한 알고리즘 포스팅 예정 문제풀이방법 글을 읽어보면, 건물을 건설하는데 순서가 있다고 한다. ex) 1번의 건물의 걸설이 완료되면, 2번과 3번의 건물을 건설할 수 있다. 이와 같은 경우, 방향이 존재한다. ( 1번다음엔 2번, 3번으로 가는 경우만 있다. 즉, 2번에서 1번으로 갈수 있는 경우는 없다. ) 전후관계가 분명하다. 전후관계가 없을 수도 있다. 이 경우에는, 언제 건설이 되어..

[백준] 19640번 화장실의 규칙 자바 코드 및 문제풀이 방법 문제설명 * 더 구체적인 예시는 아래 힌트를 확인하면 된다. 생각해야 할 요소 1. 사람들을 차례대로 M개의 라인으로 집어넣어야 한다. 2. 비교를 할 대상은, M개의 라인 중 첫번째에 위치한 사람들이다. 2-1. 비교 기준은, 고용기간이 오래된 사람 2-2. 고용기간이 같다면, 화장실이 급한사람 2-3. 같다면, line의 숫자가 앞에 있는 것 순서이다. 문제풀이 방법 1. 사람들을 차례대로 M개의 라인으로 집어 넣기 위해서 LinkedList[] 배열을 만들어서, 차례대로 넣어주었다. 2. pq에 조건에 해당하는 것을 Comparator 을 사용하여 정렬해주었다. 문제에서 요구하는 것은 PQ를 적절히 사용할 수 있는지, PQ를 본인의 입..

[ 백준 ] 1715번 카드정렬하기 자바 코드 & 문제풀이 방법 문제설명 생각해야 할 요소 1. 처음엔 문제가 이해가 잘 안갔다. 문제에서 정렬된 두 묶음의 숫자카드가 있다고 나와있는데, 이 말이 입력값이 정렬이 된 상태로 들어온다는 건가? 헷갈렸다. 2. 문제를 읽다가 생각해낸 풀이는, 최소한의 비교 횟수가 나오려면 숫자가 작은 것들끼리 더해야 한다는 한다는 것이었다. 간단하게 생각해서 처음 나온 숫자랑 두번째 나온 숫자는 N-1 번 나올거고, 그 다음은 N-2, N-3 나오는거 아닌가? 해서 풀었다. 결과는 틀렸습니다! 그 이유는, 다른 예시를 보면 이해가 확실히 갈 것이다. 백준에서 주어진 예시에는 (10 + 20 ) < 40 이라 한번에 캐치하기 어려웠을 수도 있다. 이 문제의 패턴은 더해진 숫자..

[백준] 연구소 14502번 - JAVA 문제설명 문제풀이과정 DFS로 벽 3개를 찾는다. BFS로 바이러스를 퍼뜨린다. 안전구역의 개수를 구한다. 안전구역의 개수의 최대값을 구한다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Lab_14502 { static int N, M, answer = 0; static int[] dx = {0, 0, 1, -1}; static int[] dy = {1, -..

[ 백준 ] 경쟁적 전염 18405- JAVA 문제풀이 문제설명 생각해야할 요소 1. 생각해줘야 할 포인트는 바이러스 번호가 낮은 숫자부터 시작하고 덮어쓰기가 안된다는 것이다. cf) BFS 문제인가? 맨처음 문제를 봤을 때 BFS라고 생각했지만, 문제를 풀다보니까 맞나? 싶기도 하고... 문제풀이 방법 1.사실 무척 간단하다. map을 순회하면서 내가 전이할 virus의 번호와 일치하는 것을 Queue에 몽땅 집어 넣어준다. - 큐에 들어있는 값의 상하좌우를 보고, map의 범위에 벗어나는것, 이미 그 칸을 점령하고 있는 바이러스가 있을 경우를 제외해주고 virus를 넣어주면 된다. 2. 시간이 오래 걸리지 않기 위해서 X,Y 위치에 값이 0이 아니라면 루프를 빠져나갈 수 있도록 했다. 소스코드 imp..

[백준] 치킨배달 15686 - JAVA 풀이 문제설명 생각해야할 요소 1. 치킨집 중에서 최대 M 개를 고른다. ( M개보다 적게 고를 수 있다. ) 2. 치킨집을 어떻게 고를 것인가? ( 백트래킹, 조합 ) 3. 도시의 치킨 거리는 어떻게 구할 것인가? 문제풀이방법 1. 치킨집 중에서 최대 M 개를 고른다. ( M개보다 적게 고를 수 있다. ) - 이 부분은 문제를 풀다가 놓친 부분이다. ( 그냥 M개를 고르면 되는 줄 알았다. ) - 최대 M개라 하면, M보다 작은 수의 치킨집을 골라도 된다는 말이다. - 생각을 했을 때, M보다 작게 뽑게 된다면 치킨과 집간의 거리가 늘어날 것이고 결국 도시의 치킨 거리가 가장 작게 될지 구하지 못할 것이다. - 결국, 무조건 M개를 뽑아야 함을 알 수 있다. 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인 것은 제외 )..