말하는 컴공감자의 텃밭

모든지점에서 양방향 다리를 통해 정해진 비용 안으로 아이템을 많이 얻는 길을 탐색해야하는 문제이다.플로이드 워샬과 다익스트라를 생각할 수 있는데 모든 정점이기 때문에 플로이드 워샬을 선택하는게 맞았다.다만.. 다익스트라가 땡기잖아 >  접근법은 먼저 모든 정점을 탐색해야 했기에 포문에 넣어 로직을 돌려줬다.로직은 우선순위큐를 활용해서 시간이 짧은 순으로 정렬하여 처리를 했다.해당 거리를 방문하고 비용이 m 보다 크지 않다면 큐에 넣어 반복해 주었다.기존에 visit Boolean을 안써서 틀렸었다..  123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616..

먼저 사람 수와 파티의 수가 주어진다.진실을 아는 사람들이 주어지고, 이후에 파티에 참가하는 인원이 주어진다.거짓말을 하려면 해당 파티에 진실을 아는 사람이 없어야 한다. 간단한 문제지만 구현을 어떻게 할지 고민이 됐다. 먼저 진실을 아는사람이 파티에 존재한다면, 해당 파티에 있는 사람은 모두 진실을 듣게된다.해당 파티에 진실을 모르고 있던 사람들을 진실을 아는 집단에 추가하여 업데이트한다.이후 진실을 아는사람이 없는 파티마다 정답에 ++ 해주면 된다. 따라서 진실을 아는사람을 큐에 넣고, 각각의 사람에게 어떤 파티를 참여했는지 정리한다.BFS를 통해 해당파티에 진실을 아는 사람이 있다면 해당 파티에 있는 전원을 진실 집단에 추가한다.해당 파티를 visited 를 통해 진실된 사람이 있는지 체크해주고 마..

오늘은 해장 알고리즘..비전공자와 함께 토크토크하며 시작합니다..  문제를 정리하면 배열이 주어지고, 해당 배열에서 3가지를 선택해서 0에 가장 가깝게 만드는게 관건이다.입력은 3  🔹 인풋은 5,000 숫자 세개를 모두 탐색하게되면 N³. = 125,000,000,000 이 된다.시간 제한 1초, 10⁸ 안팎이어야 하므로 이분탐색을 활용해서 시간을 log 대로 줄여보자. 해결 프로세스1. 숫자를 정렬하자.2. 두개를 먼저 이중 포문으로 고정하자.3. 나머지 숫자는 고정된 값 + 탐색하는 값으로 0과 가까운지 확인하며 이분탐색으로 찾자.4. 저장된 용액보다 0과 가깝다면 업데이트 해자.5. 0을 만들거나, 모든 경우의 수를 따졌다면 최적의 결과를 출력하자. 정렬에 N log N, 이중 포문 N², 이진..

최소 스패닝 트리  최소 스패닝 기본 문제이다.모든 정점이 연결되어야 하고, 각 연결된 간선이 최소값으로만 구성이 되어야 한다.크루스칼과 프림 알고리즘으로 해결할 수 있는데, 두가지로 풀어보았다.🔽 알고리즘 차이점 확인https://hb-in99.tistory.com/191 최소 신장 트리를 위한 프림, 크루스칼 알고리즘정점과 가중치가 존재하는 간선이 주어진 상태에서 우리는 모든 정점을 가장 적은 비용으로 연결한 그래프를 최소 신장 트리라고 말한다. MST(Minimum Spanning Tree) 라고 말하며 이러한 문제에서 사hb-in99.tistory.com  프림 알고리즘 1234567891011121314151617181920212223242526272829303132333435363738394..

마인크래프트 문제를 요약하면 땅을 평평하게 하고 싶다.N x M 크기의 맵이있고, 내 인벤토리엔 B 개수의 블럭이 주어진다.맵의 숫자만큼의 높이로 블럭이 쌓여져 있고, 쌓는데 1초, 치우는데 2초가 걸린다.블럭이 존재하지 않다면 더이상 사용할 수 없고, 블럭을 치우면 인벤토리에 들어오게 된다. 모든 땅의 높이가 같게하는 방법에서 가장 최단 시간을 구하고,동시간대가 존재한다면 가장 높이 쌓은 높이를 출력하면 된다. 높이가 기본적으로 0부터 256까지이고 음수가 될수 없어 범위는 0 이다.시간계산이기 때문에 임의의 높이 X를 정하고, X를 기준으로 시간을 계산해 주었다.X보다 낮은 높이의 땅이라면 1 * (X - (현재 땅의 높이))X보다 높은 높이의 땅이라면 2 * Math.abs(X - (현재 땅의 높..

도시 분할 계획  마을에는 경로가 존재하고, 분리해서 이 경로를 없애면서 유지비용을 최대한 줄이는 문제다.마을 내부에서 서로 다른 집을 방문할 수 있어야하고, 마을이 분리됐다면 분리된 마을끼리는 연결되지 않아도 된다.이게 말로만 풀어쓰니까 이게 무슨..? 싶은데 그림으로 정리하면 편하다. 파란 부분을 A마을, 붉은 부분을 B마을이라고 하자,A 마을끼리 모두 연결되어 있고, B 마을끼리 모두 연결되어 있다.A와 B 마을 사이에 연결되는 부분이 오늘 문제의 포인트다.분할되는 부분이기 때문에 유지비가 들지 않는다.그림을 다시보면 모든 점이 연결된 그래프고, 우리는 유지비를 최소한으로 유지하고 싶으므로많은 경로가 존재한다면 그 중 유지비가 적은 값으로 연결을 시켜야 할것이다. 결국 이건 학부때 배웠던 최소 스패..

부분합   수열이 주어지고, 연속된 수들의 합이 S보다 크며, 크기가 가장 작은 수열의 길이를 찾는 문제이다.누적합과 슬라이딩 윈도우(투 포인터) 로 풀이가 가능할듯 했다. 나는 투 포인터로 풀었다.시작점부터 더해가면서 S보다 크다면 조건을 거쳐 가장 앞을 하나씩 지워주는 방식으로 진행했다. 누적합의 경우 누적합 배열을 만들어주고, 이분 탐색으로 범위를 좁히면 될것 같다. 🔽 투 포인터 풀이 12345678910111213141516171819202122232425262728293031323334353637383940import java.io.*;import java.util.*; public class Main { // 부분합&n..

아 오늘 좀 후딱 풀었네3문제 50분~ 집합  출력되는건 check, toggle인 점만 확인하면 더 쉽게 풀 수 있었을거 같다.비트마스킹으로 메모리 더 적게도 가능하겠다. 꼭 풀고 생각나 연산자설명&비트 단위 AND 연산 (비트가 모두 1이면 1 반환)|비트 단위 OR 연산 (비트 중 하나 이상 1이면 1 반환)^비트 단위 XOR 연산 (비트가 서로 다르면 1 반환)~비트 단위 NOT 연산 (0 -> 1, 1 -> 0 반환)비트 Left Shift 연산 (비트를 왼쪽으로 이동)>>비트 Right Shift 연산 (비트를 오른쪽으로 이동) 보니까 또 기억나네 커맨드 별로 기능을 나누어서 작성해주었다. Set 으로 푼 코드 🔽🔽 12345678910111213141516171819202122232425..

숫자 카드 2   카드의 개수가 몇개인지 파악해야하고, 없다면 0을 출력해야한다.간단하게 HashMap 자료구조를 활용했고 getOrDefault 를 활용해서 개수 저장해줬다. 5분커엇..  12345678910111213141516171819202122232425262728293031323334353637import java.io.*;import java.util.*; public class Main { // 숫자 카드 2    public static int N, M;     public ..

N과 M (9)   중복되는 수열을 제외하고 출력해주는게 포인트이다따라서 정렬한 arr 배열에서 수로 수열을 만들때 이전 수와 같은지 체크해주었다.if (!visit[i] && arr[i] != prev) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import java.io.*;import java.util.*; public class Main { // N과 M (9)    public static int N, M;&nbsp..