분류 전체보기
-
[알고리즘 개념] 힙 (heap)알고리즘 공부/알고리즘 개념 2020. 8. 11. 15:55
이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리 구조 완전 이진트리 이진트리와 다르게 데이터가 루트 노드부터 시작하여 자식 노드가 왼쪽, 오른쪽 자식 노드 순서로 쌓이게 되는 트리를 말한다. 이진트리는 중간에 노드가 비어있을 수 있지만, 완전 이진 트리는 중간 노드가 비어있을 수 없는 형태이다. 힙 힙은 최대 힙과 최소 힙이 있다. 최대 힙은 구성하는 모든 노드가 '부모 노드가 자식 노드보다 크다'라는 규칙을 가진 것이다. 최소 힙은 반대로 구성하는 모든 노드에 대해 부모 노드가 자식 노드보다 작다는 규칙을 가진 것이다. 따라서 힙의 루트는 최댓값이나 최솟값이다. 따라서 힙은 최댓값과 최솟값을 쉽게 찾을 수 있는 자료 구조이다. 배열의 인덱스를 활용하여 자식 노드와 부모 노드를 찾기 쉽기 때문에 ..
-
[프로그래머스] 스택/큐 - 프린터알고리즘 공부/문제 풀이 2020. 8. 11. 15:13
이전 문제와 마찬가지로 인쇄 목록의 순서가 있기 때문에 큐를 떠올렸다. 큐를 이용하여 문제를 해결하였다. class Waiting{ int priority;//우선순위와 int index;//location 변수와 비교 위해 index 추가 public Waiting(int p,int i) { this.priority=p; this.index=i; } } static int solution(int[] priorities, int location) { int answer = 0; //뽑힌 인쇄 수 == 뽑힌 인쇄 순서 Queue q=new LinkedList(); //대기 큐 초기화 for(int i=0;i 출력 if(top>-1 && q.peek().priority==priorities[top]) { W..
-
[프로그래머스] 스택/큐 - 다리를 지나는 트럭알고리즘 공부/문제 풀이 2020. 8. 11. 00:31
문제의 "순서가 있는 트럭"이라는 말에서 큐를 떠올렸다. 큐를 이용해서 구현해야지 까지... 생각하고 여러 가지 방안을 생각해보았는데 특정한 경우에만 적합한 방법이라는 것을 알았다. 문제의 예시에서도 그렇고, 내가 손으로 생각해 볼때도 계속 시간당 bridge가 어떻게 될까를 생각하며 고민하였다. 그래서 결과 중심으로 문제를 푸는 것이 아닌 시간 단위의 과정으로 bridge 상태를 고려하며 풀어야겠다고 생각했다. 따라서 현재 bridge를 나타내는 변수를 만들었다. bridge의 크기는 문제에서 주어지는 bridge_length이고, 1초가 지날 때마다 배열의 값이 한 칸씩 왼쪽으로 이동하게 된다. 다리 위에 놓인 트럭의 무게 합이 다리가 버티는 weight보다 작은 경우 큐에서 값을 꺼내와 bridge..
-
[프로그래머스] 스택/큐 - 기능개발알고리즘 공부/문제 풀이 2020. 8. 10. 14:50
static int[] solution(int[] progresses, int[] speeds) { //정답 배열의 크기 알수 없으므로 ArrayList로 선언 ArrayList list_answer = new ArrayList(); int[] left=new int[progresses.length]; //남은 퍼센트 int[] days=new int[progresses.length]; //배포 가능일 수 //left,days 초기화 for(int i=0;ispeeds[i]*day) day++; days[i]=day; } int temp=0; for(int i=0;i
-
[프로그래머스] 스택/큐 - 주식가격알고리즘 공부/문제 풀이 2020. 8. 10. 13:59
주어진 prices에서 값을 하나씩 읽어 들어오며, 이전의 prices 값보다 크거나 같다면 인덱스에 해당하는 값을 하나씩 증가시키는 방향으로 코드를 작성하였다. 단, 숫자가 작다가 다시 커지는 경우도 있으므로 가격이 떨어진 후 다시 값이 증가되어 값이 count 될 수 있으므로 prices와 같은 크기의 flag boolean 변수를 만들어 이미 값이 떨어진 변수는 더 이상 count 할 수 없도록 처리하였다. 마지막 prices는 값의 변동이 일어나지 않으므로 무조건 0값이다. 따라서 반복문에 포함시키지 않았다. static int[] solution(int[] prices) { int[] answer = new int[prices.length]; boolean[] flag=new boolean[pr..
-
[알고리즘 개념] 스택/큐알고리즘 공부/알고리즘 개념 2020. 8. 9. 12:07
스택 그림을 보면 알 수 있듯, 스택은 LIFO(Last In Frist Out) 후입 선출 구조이다. 즉, 밑이 막힌 구조로 마지막으로 넣은 것이 먼저 나온다는 것이다. 쉽게 생각하면 쌓아 올린 접시를 생각하면 된다. 실생활에서는 컴퓨터의 뒤로 가기 기능이 스택을 이용하여 구현되었다. 페이지 뒤로 가기, 실행 취소 (Ctrl + Z)와 같은 기능은 스택의 대표 예제이다. 데이터를 삽입할 때는 push 데이터를 삭제할 때는 pop이라는 용어를 사용한다. 스택에서는 마지막 데이터 위치를 기억하기 위해 top이라는 변수를 사용하여 구현하게 된다. 스택 구현은 배열과 연결 리스트를 통해 구현할 수 있다. 배열의 장점은 구현이 쉽고, 원하는 데이터의 접근 속도가 빠르다는 것이다. 하지만, 배열의 크기가 정해져 ..
-
[프로그래머스] 정렬 - H-index알고리즘 공부/문제 풀이 2020. 8. 6. 23:57
문제를 처음에 보고 말이 어렵다고 생각했다. 하지만, 막상 구현해보니 간단하게 코드를 짤 수 있었다. 우선 h-index의 조건은 두 가지이다. 1. h개 이상의 논문에 대해서 2. h번 이상의 인용이 이루어져야한다. 첫번째 조건은 index를 이용하여 충족시키도록 하였다. 주어진 배열을 오름차순으로 정렬한 후, 큰 수부터 접근하였다. 1,3,4,5,7 을 예시로 들어보자 초기 상태는 1,3,4,5,7,*라고 생각하자. *은 현재 가리키고 있는 인덱스라고 생각하면 된다. 당연히 h-index는 0이 될 것이다. 나는 h-index를 먼저 증가시키고 위의 두가지 조건을 만족시키지 않으면 다시 감소시킨다음 return하도록 코드를 짰다 따라서 h-index는 1이되고 가리키는 값은 7이 되어 1,3,4,5,..