'🥇코딩테스트:Algorithm' 카테고리의 글 목록 (4 Page)

서로소 집합 자료구조 (Union Find) (백준 1043번)

2024.01.03

더보기 [Gold IV] 거짓말 - 1043 문제 링크 성능 요약 메모리: 14352 KB, 시간: 128 ms 분류 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색 제출 일자 2024년 1월 3일 16:32:22 문제 설명 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 ..

🥇코딩테스트:Algorithm

다익스트라 (boj 12851 숨바꼭질2)

2024.01.02

문제 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 기존의 숨바꼭질 문제에서 최단경로의 갯수까지 구해야 한다. 1. 목적지에 도달하면 함수를 종료하는 것이 아닌 계속 탐색을 이어나가도록 함수를 구성했다. while(!pq.isEmpty()){ Node cur = pq.poll(); if(cur.idx==K && cur.w==dist[K]){ // 목표지점에 도달한 경우 count+=1; } ... } ..

🥇코딩테스트:Algorithm

이진 검색 트리 (백준 5639번)

2023.12.28

전위순회 결과를 바탕으로 트리를 만들고, 후위순회를 출력하면 된다. 풀이 순서 1. 입력을 바탕으로 트리를 구성. (노드 클래스를 활용) 2. 노드 클래스 내부에 insert 함수 작성. insert 함수 : 입력된 노드의 값을 현재 노드 값과 비교하여, 왼쪽 혹은 오른쪽에 달아주는 함수. 이때 insert 함수에 재귀함수를 적용해야 한다. 해당 위치가 비어있으면 해당 위치에 노드를 달아주고, 비어있지 않다면 해당 위치에 있는 노드의 insert함수를 재귀호출 코드 package com.mincheolsong; import java.io.*; import java.util.*; public class Main { // BOJ 5639번 이진 검색 트리 static class Node{ int num; N..

🥇코딩테스트:Algorithm

다익스트라 (백준 13549 숨바꼭질 3)

2023.12.26

다익스트라로 풀 수 있는 문제상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 해당 문제는 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 문제이다. 문제를 그래프로 바꾸는게 중요하다고 생각한다. 수빈이는 위치 X에서 -1, +1, *2 로 움직일 수 있으니까 위치 X를 노드라고 생각했을 때 X-1, X+1, X*2 를 연결된 노드, 가중치는 문제에서 주어진 (1, 1, 0) 으로 생각했다. 다익스트라 알고리즘 (우선순위큐 활용) 코드 package com.mincheolsong; import java.io.*; import java.util.*; public class Main { // boj 13549 ..

🥇코딩테스트:Algorithm

트리의 지름 (백준 1167번)

2023.12.26

트리의 지름이란 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것이다. 결론 임의의 정점에서 가장 거리가 긴 노드를 찾는다. (dfs 한 번) 찾아진 노드에서 가장 거리가 긴 노드까지의 거리를 구하면 된다. (dfs한 번) (총 dfs 두 번에 트리의 지름을 찾을 수 있다) 설명 위 트리의 경우 1 - 3 - 4 - 5 가 트리의 지름(트리에서 임의의 두 점 사이의 거리 중 가장 긴 것) 경로가 된다. 여기서 트리의 지름이 되는 양 끝 노드는 1과 5이다. 이 때 임의의 정점에서 거리가 가장 긴 노드는 1 혹은 5를 반드시 지나게 된다. 1에서 거리가 가장 긴 경로 : 1 - 3 - 4 - 5 2에서 거리가 가장 긴 경로 : 2 - 4 - 5 3에서 거리가 가장 긴 경로 : 3 - 4 - 5 4에서 거..

🥇코딩테스트:Algorithm

플로이드 워셜 알고리즘

2023.12.14

모든 노드에서 다른 모든 노드까지의 최단경로를 모두 계산함 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행 다익스트라와 다르게 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음. 2차원 테이블에 최단 거리 정보를 저장 DP 유형에 속함 (점화식에 맞게 3중 FOR문을 이용해서 2차원 테이블을 갱신) 노드의 계수가 밀집그래프(완전그래프에 가까운 그래프)인 경우 플로이드 워샬 알고리즘이 효율적이다. 밀집그래프가 아닌 경우 다익스트라를 n번 돌리는게 빠르다 O(n^3)의 시간복잡도로 다익스트라(인접행렬을 사용한 경우)의 시간복잡도와 동일하다 N이 100이면 → 100만이어서 가능, 500이어도 → 1억 2천 500만 이어서 try해볼 ..

🥇코딩테스트:Algorithm

백준 9465 스티커

2023.11.29

dp로 푸는 문제. 알게된 점 점화식을 세울 때 arr[r][c]를 포함하는 경우와 포함하지 않는 경우만 생각하지 말자 이번 문제는 arr[r][c]를 뽑을 수 있는 이전 위치를 고려해야 했다! dp는 최적해의 부분최적해를 생각하며 점화식을 세워야 한다. 처음 접근방식 arr[r][c] 의 스티커를 떼는 경우와 떼지 않는 경우를 고려해서 점화식을 세우려고 했다. 올바른 접근방식 arr[r][c]의 스티커를 뗄 수 있는 경우만 고려하고, arr[r][c] 스티커를 뗄 수 있는 이전 위치 (arr[1][c-1] or arr[1][c-2] 혹은 arr[0][c-1] or arr[0][c-2]) 를 부분최적해로 보는 것 이었다. 점화식 r=0인 경우 dp[r][c] = max{dp[1][c-1], dp[1][c..

🥇코딩테스트:Algorithm

bfs 방문체크 위치

2023.11.22

백준 문제를 풀다 메모리 초과를 만남.. 분명 다른사람 코드와 같은데, 왜 메모리 초과가 나는지 이상했다. 이유는 bfs 방문체크 위치를 잘 못 해서 결론 : 큐에 삽입하는 순간에 방문체킹을 해서 중복을 방지하자 잘못된 방문체크 위치 (큐를 뽑는 순간 방문체크) 아래 코드는 문제에 사용된 bfs함수 일부분입니다 static boolean move(){ Queue tmp = new LinkedList(); while(!bq.isEmpty()){ int[] c = bq.poll(); int cr = c[0], cc=c[1]; if(cr==er && cc == ec){ return true; } chk[c[0]][c[1]]=true; // 방문체크 for(int d=0;d

티스토리툴바