분류 전체보기
-
다익스트라 알고리즘(Dijkstra's Algorithm)Algorithm/이론 2020. 8. 25. 18:46
다익스트라 알고리즘 정점 하나를 시작점으로 하여 나머지 정점들 간의 최단거리를 구하는 알고리즘 그래프는 무향이거나 유향이나 대부분 유향인 경우가 많으며, 간선 간의 이동거리가 존재한다. 또한 거리값이 음수가 아닐 때만 사용할 수 있다. 시간복잡도는 인접리스트로 구현했을 경우 O(ElogV), 인접행렬로 구현했을 경우 O(V^2)가 된다. 동작 과정 1. 준비물 int E, V, K // 간선 수, 정점 수, 시작점 class Node // Comparable {weight 오름차순 비교} List graph int[] distance // 거리 정보 저장 int[] prev // 최단 거리 경로 저장 boolean[] visited PriorityQueue pq 2. init() graph에 v+1개의 ..
-
[Programmers] 2020카카오공채 문자열 압축Algorithm/Programmers 2020. 8. 24. 19:50
[Level 2] 문자열 압축 https://programmers.co.kr/learn/courses/30/lessons/60057 레벨 2 문제인데 문제를 제대로 이해하지 못해서 너무 오래 풀었다.. ㅠㅠ 압축할 문자열 s가 매개변수로 주어질 째, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성하시오. 헷갈렸던 포인트는 문자열을 앞에서 부터 n개씩 잘라야한다는 부분이 n=2, aa/ab/aa/dd/ee/... 같이 연속해서 n개로 압축하는 것이 아니라 aa/abcabcd/rr/dd/... 처럼 첫 부분만 2개로 잘리면 뒷부분에서는 자유롭게 2개씩 묶어 압축하는 방식으로 이해했다. 노답스;; Solution 완전 탐색으로 ..
-
[Java] StringBuilder class 함수Programming/Java 2020. 7. 3. 15:34
StringBuilder https://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html append(Object o) StringBuilder에서 가장 많이 사용하는 함수로 문자열 데이터 끝에 문자 형태로 인자가 추가된다. insert(int index, Object o) StringBuilder 객체의 index위치에 문자 형태의 o가 삽입된다. delete(int index), delete(int start, int end) index에 해당하는 char를 지운 StringBuilder 객체를 반환해준다. indexOf(String str), lastIndexOf(String str) 각각 StringBuilder 객체에서 처음으로 등장..
-
[BOJ] 심심한 준규Algorithm/BOJ 2020. 7. 2. 18:58
[2892] 심심한 준규 https://www.acmicpc.net/problem/2892 문제 설명의 표에있는 excrypted message가 입력이 되고, 암호화된 메시지의 글자가 문자인지 아닌지 출력하는 문제 Solution 애초에 xor 연산하는 방법도 몰라서 답을 봤다. excrypted message에서 문자와 문자가 아닌 글자의 숫자 범위를 보고 유추하는 방법이였다. '0'~'9'까지 숫자키와 'a'~'z'까지의 소문자를 xor 연산했을 때 나오는 결과 범위는 64~95 까지 이고, '0'~'9'까지 숫자키와 ' ', '.'을 xor 연산했을 때 나오는 숫자범위는 16~31 까지이다. excrypted message를 16진수 정수로 변환했을 때 어떤 범위에 속하는지에 따라 '-' 혹은 '..
-
[Programmers] 카카오프렌즈 컬러링북Algorithm/Programmers 2020. 6. 16. 12:23
[Level 2] 카카오프렌즈 컬러링북 https://programmers.co.kr/learn/courses/30/lessons/1829 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램 작성 영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다. 그림의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다. Solution picture 전체 배열을 돌면서 0이 아니면서 아직 방문하지 않은 영역(count 하지 않은 영역)에 대해 BFS를 돌린다. BFS()에서는 해당 영역에 해당하는 최대 칸 수를 갱신하고 max 변수에 저장한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..
-
[Programmers] 라면공장Algorithm/Programmers 2020. 6. 4. 01:14
[Level 2] 라면공장 https://programmers.co.kr/learn/courses/30/lessons/42629 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(suppies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 ..
-
[Programmers] 괄호 변환Algorithm/Programmers 2020. 6. 2. 16:13
[Level 2] 괄호 변환 https://programmers.co.kr/learn/courses/30/lessons/60058 Solution 문제에서 주어진 조건대로 재귀 함수로 구현하여 풀 수 있었다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 import java.util.*; class Solution { static StringBuilder sb; public String solution(String p) { String answer ..
-
[Programmers] 전화번호 목록Algorithm/Programmers 2020. 6. 1. 22:25
[Level 2] 전화번호 목록 https://programmers.co.kr/learn/courses/30/lessons/42577 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같은 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97674223 지영석 : 1195524421 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. Solution phone_book[]의 원소를 String 길이 기준으로..