알고리즘 공부

[프로그래머스 2단계 - 더 맵게] 효율성 풀이과정

https://programmers.co.kr/learn/courses/30/lessons/42626?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제가 정말 좋아하는 효율성, 자료구조 문제입니다. 문제 설명 PriorityQueue에 대한 이해가 있으면 쉽게 풀 수 있는 문제입니다. (모르면 효율성 통과 못할겁니다..) PriorityQueue는 Windows OS의 스케쥴러에도 사용됩니다. Python에는 heap이 있습니다. 아래는 우선순위큐에 대해 자세히 설명되어있는 블로그입니다. https://medium.com/@dor..

[알고리즘] 에라토스테네스의 체

소수 판별 알고리즘의 종류 1. 2 ~ N -1까지 순회하면서 나누어 떨어지는 수가 있는지 확인하는 방법. 2. N의 약수는 (N/2-1)보다 클 수 없으므로 2 ~ N / 2 - 1까지 순회하는 방법. 3. N의 제곱근까지의 약수의 개수 * 2로 순회하는 방법 N = 12일 때 sqrt(N) = 3.46입니다. 12의 약수는 2 * 6 3 * 4 4 * 3 6 * 2 가 있는데, 12의 제곱근인 3.46를 기준으로 x * y | y * x로 숫자만 바뀌는 특성을 이용합니다. 1번 방법의 시간 복잡도는 O(N)입니다. 2번 밥법의 시간 복잡도는 O(N) T(N) N/2입니다. 3번 방법의 시간 복잡도는 O(sqrt(N)) 입니다. "에라토스테네스의 체" 알고리즘은 소수를 판별하는 가장 유명한 알고리즘 중..

Least Recently Used 자료구조 구현 Java

FIFO LIFO LRU LFU NUR SCR 대표적인 메모리 관리 방식 중 하나인 LRU를 구현해보자. 문제 설명 Main public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] work = new int[m]; for (int i = 0; i < m; i++) work[i] = sc.nextInt(); new Main().solution(n, work); } I / O 메인 메서드에서 Cache의 크기 N인 메모리에 수행하는 작업의 개수 M이 주어집니다. M개의 Integer 작업이 주어집니다. 모든 작업이 수행되고 메모리 공간에..

[자료구조] 트리(Tree)

트리 ( Tree ) 트리는 계층적인 구조를 표한할 때 유용하게 사용할 수 있는 자료구조입니다. [ 트리 관련 용어 설명 ] 루트 노드 (root node) 부모가 없는 최상위 노드입니다. 단말 노드 (leaf node) 자식이 없는 노드를 말합니다. 크기 (size) 트리에 포함된 모든 노드의 개수입니다. 깊이 (depth) 루트노드부터의 거리를 말합니다. 높이 (height) 깊이 중 최댓값을 의미합니다. 차수 (degree) 자식 방향의 간선갯수를 의미합니다. 이진 탐색 트리 ( Binary Search Tree ) 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조입니다. 이진 탐색 트리의 탐색 37은 30보다 크기 때문에 오른쪽 간선을 탑니다. 37은 48보다 작기 때문에 왼쪽..

[자료구조] 트라이(Trie)

https://programmers.co.kr/learn/courses/30/lessons/60060?language=java 코딩테스트 연습 - 가사 검색 programmers.co.kr Trie 구현 먼저 Node 클래스를 만듭니다. class Node { Map childNodes = new HashMap(); @Override public String toString(){ return childNodes.keySet().toString(); } } Node Class는 필드로 HashMap의 자식 노드를 가집니다. 자식 노드를 확인하기 위해 toString을 오버라이딩 해줍니다. class Trie { Node rootNode = new Node(); void insert(String s) { N..

프로그래머스 스택/큐 : [프린터] JAVA 풀이

https://programmers.co.kr/learn/courses/30/lessons/42587?language=java 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 문제 설명 프린터를 우선순위대로 출력을 할때 내가 원하는 출력물이 몇번째로 출력되는지 구하는 문제입니다. 매개변수로는 우선순위인 int[] pripriorities와 내가 원하는 출력물의 인덱스 location이 주어집니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도..

프로그래머스 3단계/효율성 : [숫자 게임] Java 풀이

https://programmers.co.kr/learn/courses/30/lessons/12987#qna 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 팀 A의 카드 배열 [ 5, 1, 3, 7 ] 팀 B의 카드 배열 [ 2, 2, 6, 8 ] 여기서 팀 B가 최대로 점수를 많이 가져가는 방법은 1 : 2 승리 3 : 6 승리 7 : 8 승리 5 : 2 패배 3점 일것입니다. 문제 난이도는 쉽지만, 3단계 문제답게 효율성 테스트가 까다로운 문제입니다. 정답 코드 import java.uti..

프로그래머스 스택/큐 : [기능개발] Java 풀이

https://programmers.co.kr/learn/courses/30/lessons/42586?language=java 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 기본 자료구조에 대한 이해가 필요한 문제입니다. import java.util.*; class Solution { public int[] solution(int[] progresses, int[] speeds) { Queue queue = new ArrayDeque(); ArrayList list = new ArrayList();..