💾 알고리즘 (56)

[Programmers] : 해시 > 완주하지 못한 선수

🔗 문제 링크 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 💻 코드 import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { String answer = ""; ArrayList p = new ArrayList(); ArrayList c = new ArrayList(); for(int i=0; i < participant.length; i++) { p.add..

[Programmers] : 스택/큐 :: 주식가격

package org.kyhslam; import java.util.Arrays; public class stack03 { public static int[] solution(int[] prices) { int[] answer = new int[prices.length]; for(int i=0; i prices[j]){ break; } } } System.out.println(Arrays.toString(answer)); return answer; } public static void main(String[] args) { int[] p =..

[Programmers] : 스택/큐 :: 프린터

문제 https://programmers.co.kr/learn/courses/30/lessons/42587?language=java 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 내가한거 package org.kyhslam; import java.util.*; public class stack02 { public static class Task { private int priority; private int location; public Task(int priority, int location) { this.p..

[Programmers] 정렬 : k번째수

https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr package com.hyosung.algo; import java.util.Scanner; public class pro_sort02 { static int[] buff; static void swap(int[]a, int x, int y) { int temp = a[x]; a[x] = a[y]; a[y] = temp; } static void quickSort(int[] a, int left, int right) { int ..

다익스트라(Dijkstra Algorithm)

하나의 정점에서 다른 모든 정점들의 경로를 구하는 알고리즘이다. 간선들은 모두 양의 간선들을 가져야 한다. Dijkstra의 알고리즘에서는 시작 정점에서 집합S에 있는 정점만을 겨처서 다른 정점으로 가는 최단 거리를 기록하는 배열이 있어야 하는데 이 배열을 우선순위 큐로 구현하여 해당 큐에 들어간 Node중에 가중치가 젤 작은 정점을 가져오도록 구현해야 한다. 시작 정점을 0으로 잡고, 각 지점까지의 거리를 표시한다. 여기서 각 정점까지의 정보와 거리를 우선순위 큐에 넣는다. 그리고 우선순위 큐에서 가장 짧은 거리인 4정점까지의 거리인 3이므로 4정점에서 시작을 한다. 나는 해당 배열을 우선순위 큐로 구현하였다. 우선수위 큐 구현(가장 작은 값 순서로) package org.kyhslam.cps.sect..

부분집합의 합

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 참고 : m.blog.naver.com/PostView.nhn?blogId=tlstjd436&logNo=221568959948&proxyReferer=https:%2F%2Fwww.google.com%2F 백준(BOJ) 1182 - 부분수열의 합 (부분집합 구하기) //[java]- 재귀 부분수열의 합문제N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인..

우선순위 큐 : 객체의 특정값으로 정렬

Student 클래스의 age 나이를 기준으로 나이가 많은, 적은 순으로 우선순위 큐를 사용하는 방법 나이가 많은 순 import java.util.PriorityQueue; // 우선순위 큐 // 객체의 특정 값을 기준으로 정렬 public class priorityQueu_Test { public static class Student implements Comparable { String name; int age; public Student(String name, int age){ this.name = name; this.age = age; } @Override public int compareTo(Student o) { return this.age

유니온 파인드 (Union-Find)

유니온 파인드 (Union-Find) 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미 상호 배타적 집합(Disjoint-set)이라고도 한다 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘 Find : x가 어떤 집합에 포함되는지 찾는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 그림으로 이해하기 노드의 개수만큼 아래와 같이 모든 값이 자기 자신을 가리키도록 한다. i : 노드번호, P[i] : 부모노드 번호 를 의미하며, 즉 자기자신이 어떤 부모에 포함되어 있는지를 의미한다 간단히 Parent[i] = i 로 표현한다 Union(1,2) 를 하면 2번째 인덱스에 "1" 값이 들어간다. 부모를 합칠 때는 일반적으로 더 작은..

우선순위 큐 : priority_queue (최대힙, 최소힙)

우선순위 큐(Priority Queue) 일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조이다. 이와 달리 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다. 최대힙 PriorityQueue의 생성자에 Collections.reverseOrder() 을 주어야 한다. import java.util.*; // 최대힙 (priority_queue : 우선순위 큐) public class cp73 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); PriorityQueue queue = ..

[Programmers] 네트워크 DFS 풀이 (Java)

네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 풀이 class Solution { public int solution(int n, int[][] computers) { int answer = 0; boolean visited[] = new boolean[n+1]; for(int i=0; i < n; i++){ if( visited[i] == false){ answer += dfs(i, computers, visited); } } return answer; } public static int dfs(int x, int[][] computers, boolean[] visited){ if(visited[x]){ return 0; } visited..

[DP : 동적계획법] 최대연속부분수열

{33, 36, -73, 15, 43, -17, 36, -28, -1, 21} 1단계 : 배열 초기화 //초기화 public static void calculate_max(int[] s, int n){ for(int i=1; i < n; i++){ System.out.println("c[" + i + "] = max( s["+i+"], (s[" + i + "] + c[" + (i-1) + "] ) )"); c[i] = max( s[i] , (s[i] + c[i-1]) ); } System.out.println(); System.out.printf("a[] : "); view1(a); System.out.printf("c[] : "); view1(c); } c[1] = max( s[1], c[0] ) c[..

최대이익 - 동적계획법

투자액 기업0 기업1 기업2 1 2 3 1 2 4 5 3 3 6 6 7 4 9 8 9 참고로 해당 이익표의 내용들을 아래와 같이 저장하였다. A[0,2] = 4 는 0기업에 2만원 투자했을 때의 이익이 4라는 것이다. static int[][] r = { {0,2,4,6,9}, {0,3,5,6,8}, {0,1,3,7,9} }; 쉽게 생각해서 max_return이라는 새로운 배열을 선언한고 해당 배열에는 최대값을 넣는다. 즉, max_return[1][2] = 3 이라고하면 0~1번 기업까지 2만원을 투자했을 때 얻을수있는 최대이익이 3 이라는 것이다. max_return[1][2] 값을 구하기 위해서는 아래와 같은 과정이 필요하다. 1) max_return[0][0] + r[1][2] 2) max_ret..

1
2
3
4
5

Copyright © 요네츄의 프로그래밍, 독서 ✌ All Rights Reserved

Designed by JB FACTORY

티스토리툴바