송민준의 개발노트

programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 프로그래머스 HIndex 문제 이해가 제일 중요하고 규칙을 찾아내야 하는 문제이다. 문제의 핵심이 아래 문장이다. "n편 중 h번 이상 인용된 논문이 h편 이상 나머지 논문이 h번 이하 인용" 우선 주어진 배열을 내림차순으로 정렬했다. 그러면 아래 표와 같이 구성이 되는데 H값이 배열의 값보다 작거나 같을 때까지 만족을 한다. 그럼 인덱스 3의..

programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 처음에 bfs로 접근하는 등의 삽질을 겁나게 하다가... 문제의 조건들을 다시 고려해보았다. 여기서 팁은 1. 숫자의 순서는 무조건 주어진 순서대로 간다는 것.(역순으로 막 뒤집어서 숫자 만들고 안그럼) 2. 순서대로 높은 숫자를 탐색하다가 그 숫자가 위치해야할 자릿수를 고려해야 함. public String solution(String number, int k) { int start = 0;// 탐색 시작 범위 int numberLength = number.length(); int limit = numberLength-k; // 제한범위 int rem..

programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr Truck이라는 클래스를 만들어서 접근 최초에는 Truck이 다리중량이 남는다면 동시에 여러대도 들어갈 수 있는 줄 알고 접근을 했다. 하지만 문제 예시를 보면 * 3 [7] [4] [5,6] * 4 [7] [4,5] [6] 위와 같이 순서대로 4, 5가 들어가는 걸 볼 수가 있다. import java.util.LinkedList; import java.ut..

programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 두개 뽑아서 더한 결과를 반환하는데 중복이 없어야 하며 오름차순으로 정렬이 되어 있어야함. 이중 for문으로 탐색을 함. TreeSet을 써서 정렬과 중복제거의 효과를 가짐 import java.util.Set; import java.util.TreeSet; public class PickTwoAndAdd { public sta..

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 주어진 스킬들이 선행스킬을 만족하는지 체크하는 문제. 주어진 스킬들을 하나씩 체크해서 선행스킬을 만족하는지 확인해줌. 선행스킬이 기준스킬보다 뒤에 있거나(인덱스가) 없으면 그건 불합격스킬트리임. package programmers.level2; public class SkillTree { public static int solution(String skill, String[] skill_trees) { int answer = 0; for(String tree : skill_trees) { // char 쪼갬 char[] treeCharArray = tree...

programmers.co.kr/learn/courses/30/lessons/64061?language=java 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 2차원 배열을 뽑기상자라고 보고 뽑기를 실행한만큼 Stack에 담아서 위아래 두 인형이 같으면 터트리는 게임. Stack을 선택한 이유는 뽑기결과가 계속해서 쌓인다는 점과 최상단의 값을 활용해야 해서임. import java.util.Stack; /** * 4, (3, (1, 1), 3), 2, 4 * (4, (3, (1, 1), 3), (2, 2), 4) */ public c..

1. Priority Queue란 무엇인가? 기본적으로 큐가 있고 이는 FIFO(First in First out) 구조로 되어 있다. Priority Queue는 이 FIFO 구조에 우선순위를 지정하고 우선순위가 높은 순으로 나가는 구조이다. Priority Queue는 Heap을 이용하는데 MinHeap과 MaxHeap으로 구분될 수 있다. 구조는 아래와 같다. Priority Queue에서 MinHeap으로 구성할 경우 자료구조에서 뽑아내면 위의 경우 10이 나오게 된다. 2. 그렇다면 어디에서 사용이 되는가? 다양한 곳에서 사용이 되겠지만 예를 들면 스터디카페에 룸을 대여할 때 스터디룸 관리에 사용하는 경우가 있다. 3. 사용 방법 - 선언 Queue queue = new PriorityQueue..

- 시간복잡도를 표기함으로써 작성한 코드가 얼마나 시간이 소요될지 알 수 있다. Big-O 표기법 O(1) O(log n) O(n) O(n log n) O(n^2) O(n^3) O(2^n) 상수 시간 로그 시간 직선적 시간 로그 직선적 시간 2차 시간 3차 시간 지수 시간 Better Worse 시간복잡도를 분석하는 것은 input n에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것과 같다. 그리고 이는 Big-O 표기를 이용하여 정의할 수 있다. 1. O(1) int sum = N * (N + 10) / 2; 2. O(N) int sum = 0; for (int num = 1; num