분류 전체보기

[Hash] Lv.1 폰켓몬, 완주하지 못한 선수

1. 폰켓몬 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 중복이 허용되지 않는 HashSet 자료구조를 사용하면 바로 풀 수 있는 문제 ex) [3,3,3,2,2,4]를 HashSet에 저장하면 중복되는 숫자를 제외한 3,2,4만 저장된다. import java.util.*; import java.io.*; class Solution { public int solution(int[] nums) { int answer = 0; int pokemon = nums.length/2; HashSet set = new HashSet(); for(int i = 0;..

[Binary Search Tree] 길 찾기 게임

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr class를 사용하여 이진 탐색 트리 구현하기 y가 같을 때(level이 같을 때) x좌표는 오름차순으로. 이외에는 y좌표 내림차순으로 import java.io.*; import java.util.*; class Node{ Node right; Node left; int value; int x; int y; public Node(int value, int x, int y, Node right, Node left) { this.value = value; this.x = x; this.y = y; this.ri..

[java] 트리와 DFS

백준 11725: 트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제를 해결하기 위해서 사용할 것 ✅트리 데이터를 저장할 인접 리스트 visited ✅ 방문 기록 저장 배열 tree ✅ 부모 노드 저장 정답 배열 parent import java.io.*; import java.util.*; //무엇이 필요한가 //트리 데이터를 저장할 인접 리스트 //방문 기록 저장 배열 //부모 노드 저장 정답 배열 public class tmp { static int n; static boolean[] visited; static ArrayList tree[]; st..

[java] 큐 / 우선순위 큐 / 힙

1. 백준 1655: 가운데를 말해요 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net Queue를 사용하여 중앙값을 찾는 방법 중앙값 기점으로 maxPq(Heap) / minPq(Heap) 이용하기 maxPq: 중앙값보다 작은 값 저장 / minPq: 중앙값보다 큰 값 저장 import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException { Buffere..

[java] 플로이드-워셜 알고리즘

플로이드-워셜 알고리즘 ✏️dp(동적계획법)의 개념을 활용한 최단경로 탐색 알고리즘 ✏️ 벨만포드 알고리즘과 마찬가지로 음수 가중치 에지가 있어도 수행이 가능하다. ✏️ 시간복잡도는 O(V^3)으로 느린편이다. 반복문을 노드 개수 V만큼 총 3번 반복하기 때문. 우선 동적계획법의 원리부터 간단히 적어본다. 노드가 1~4까지 4개 있다고 가정했을 때, 1부터 4까지 가는 최단경로가 1→2→4 라고 하자. 이는 1부터 2까지 가는 최단경로와 2부터 4까지 더하는 최단경로의 조합이 된다. Min(1→2) + Min( 2→4) 플로이드 워셜 알고리즘은 이와 유사하게 최단거리를 저장하는 배열을 만들고 dp 원리를 이용하여 값을 업데이트 해준다. 이 배열을 D라고 했을 때 D[Start][End]는 Start에서 ..

[java] 벨만포드 알고리즘

벨만포드 알고리즘 🔑그래프에서 최단거리를 구하는 알고리즘 ✏️음수 가중치 에지가 있어도 수행이 가능하며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 시간 복잡도: O(VE) 1. 에지 리스트로 그래프 구현> 최단 경로 배열 초기화 tip) 자바의 경우, Arrays.fill을 사용하면 빠르다. static final int INF = Integer.MAX_VALUE; Arrays.fill(arr, INF); 2. 모든 에지를 확인하면서 정답 배열을 업데이트 해준다. 노드 개수가 N이라고 가정할 때, 최단거리 배열에서 업데이트 반복 횟수는 N-1번이다. N개의 노드가 있고 음수 사이클이 없을 때 최단 경로를 구성하는 엣지의 개수는 최대 N-1개가 된다. (N개가 될 수가 없다) ✏️업데이트..