![]()
카테고리: 정렬 레벨: 2 언어: Java 문제 입출력 예시 풀이 public String solution(int[] numbers) { String[] str = new String[numbers.length]; StringBuilder sb = new StringBuilder(); for (int i = 0; i (o2 + o1).compareTo(o1 + o2))); if (str[0].equals("0")) { return "0"; } for (int i = 0; i < str.length; i++) { sb.append(str[i]); ..
![]()
한화시스템 BEYOND SW 캠프 2기 - 6주 차 이번 한 주는 4일간 자료구조를 배우고 금요일 하루 동안 알고리즘을 배웠다. 처음에 스택과 큐를 배웠는데 이전에 독학했을 때는 개념만 공부해 봤지 직접 구현하진 않았는데 이번에 직접 구현해 볼 수 있어서 좋았다. 스택과 큐 스택(Stack) - 스택은 삽입과 삭제 연산이 후입선출(LIFO, Last In First Out)로 이루어진 자료구조이다. - 삽입과 삭제가 한쪽에서만 일어난다. - 스택은 DFS(깊이 우선 탐색), 백트레킹 종류의 코딩 테스 hotechstory.tistory.com 스택과 큐를 배우고 강사님이 내주신 하노이 탑 문제를 풀어보는데 너무 어려웠다. 재귀를 이용해서 어찌저찌 풀었는데 너무 이해하기 어려웠었다. 알고리즘 - 하노이 탑..
![]()
AVL 트리 AVL 트리는 모든 노드의 왼쪽 및 오른쪽 하위 트리 높이 차이가 1보다 클 수 없는 이진 탐색트리로 자체 균형 이진 탐색 트리라고도 한다. 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이를 노드의 균형 요소(BF, Balance Factor)라고 하는데 이러한 균형 요소를 가지고 트리의 균형을 확인하여 노드를 적절한 곳으로 재배치해준다. 그렇다면 그냥 이진 탐색 트리를 사용하면 되지 굳이 AVL 트리를 사용하는 이유가 뭘까? 일단 이진 탐색 트리는 루트 노드를 중심으로 들어오는 데이터가 큰지, 작은 지를 판별해 데이터를 삽입하게 된다. 이진 탐색 트리의 특징은 효율적으로 탐색, 삽입, 삭제를 할 수 있는데 데이터를 삽입하고 삭제하는 것은 결국 탐색이 먼저 이루어져야 하므로 이진..
![]()
프로그래머스 - 주식가격 카테고리: 스택/큐 레벨: 2 언어: Java 문제 입출력 예시 풀이 간단히 머리로 그림을 그려보면 이해하기 쉬운 문제였다. (풀기는 난감했지만...) 그림을 그려보며 이해해 보자. 먼저 1초일 때 생각을 해보면 1초일때 주식 가격은 1이다. 이 가격은 주어진 5초가 지날 때까지 1 이하로 떨어지지 않는다. 여기서 문제의 핵심을 알 수 있는데 현재 시간에서의 주식 가격이 남은 시간 동안 얼마나 떨어지지 않고 유지되는지 알아보는 문제이다. 2초일 때를 생각해 보면 주식의 가격은 2이고 5초가 될 때까지 주식 가격은 2 이하로 떨어지지 않는다. 3초일 때를 생각해 보면 주식의 가격은 3이고 4초가 될 때 주식의 가격이 2로 떨어지고 그다음 시간에 3초로 가격이 상승한다. 5초가 될 ..
![]()
프로그래머스 - 다리를 지나는 트럭 카테고리: 스택/큐 레벨: 2 언어: Java 문제 입출력 예시 풀이 이번 문제도 이해하는데 어렵지 않다. 그림으로 먼저 이해를 해보자. 예제 1번을 생각하면서 그림을 그려보면 위의 그림과 같이 트럭들이 대기하고 있는 상태이다. 다리는 총 10의 무게를 견딜 수가 있으므로 각 트럭의 무게를 고려하며 지나가야 된다. 여기서 다리의 길이는 2이다. 즉, 트럭이 다리를 지나갈 때 최대 2대만 지나갈 수 있다. 먼저 무게가 7인 트럭이 다리를 건너고 있다면 다리가 견딜 수 있는 무게를 생각해 나머지 트럭들이 대기한다. 무게가 7인 트럭이 지나가고 나서 대기하고 있던 무게가 4인 트럭이 다리를 지나가게 된다. 다리가 견딜 수 있는 무게는 총 10이므로 무게가 4인 트럭과 5인 ..
![]()
하노이 탑 재귀 알고리즘의 대표적인 문제로 하노이 탑 문제가 있다. 문제를 설명해 보자면 1번 기둥에 있는 원반들을 3번 기둥으로 옮겨야 되는데 여기서 조건이 하나 있다. 길이가 짧은 원반 위에 길이가 긴 원반을 둘 수 없다는 조건이 있는데 해당 조건을 고려하며 문제를 풀어보자. public void hanoiTest(int from, int mid, int to, int value) { if (value >= 1) { hanoiTest(from, to, mid, value - 1); System.out.printf("%d번 원반을 %d번에서 %d번으로 옮겼다.\n", value, from, to); hanoiTest(mid, from, to, value - 1); } } 코드는 재귀를 통해서 구현하게 ..
![]()
우선순위 큐(Priority Queue) 우선순위 큐는 우선순위에 따라 값을 정렬하는 큐의 유형이다. 우선순위 큐 생성하기 PriorityQueue queue = new PriorityQueue(); PriorityQueue queue = new PriorityQueue(Collections.reverseOrder()); PriorityQueue를 생성하는 것을 살펴보면 두 가지 경우가 있다. 첫 번째로 우선순위 큐를 기본으로 생성하게 되면 우선순위가 낮은 값이 Queue의 맨 앞에 위치하게 된다. 두 번째로 Collections 클래스에 reverseOrder() 메서드를 사용하면 우선순위가 높은 값부터 맨 앞에 위치하게 된다는 차이가 있다. 우선순위 큐에 데이터 삽입하기 queue.add(1); qu..
![]()
프로그래머스 - 프로세스 카테고리: 스택/큐 레벨: 2 언어: Java 문제 입출력 예시 풀이 프로세스 문제를 이해하는 데는 오래 걸리지 않았다. 하지만 어떻게 풀어야 되는지 잘 모르는 문제였다. 우선순위에 따라서 주어진 프로세스의 위치를 알려줄 때 몇 번째로 실행되는지 구하는 문제여서 Queue 자료구조를 통해서 풀어야 한다는 것은 알았지만, 우선순위 큐가 있다는 것은 모르고 있었다. 먼저 우선순위 큐를 활용하여 푼 코드를 살펴보면 public int solution(int[] priorities, int location) { int answer = 0; PriorityQueue priorityQueue = new PriorityQueue(Collections.reverseOrder()); for (i..
![]()
프로그래머스 - 올바른 괄호 카테고리: 스택/큐 레벨: 2 언어: Java 문제 입출력 예시 풀이 괄호 문제는 대표적인 스택 문제이다. 먼저 코드를 살펴보면 아래와 같다. boolean solution(String s) { Stack stack = new Stack(); char[] charArray = s.toCharArray(); for (int i = 0; i < charArray.length; i++) { if (charArray[i] == '(') { stack.push('('); } else if (charArray[i] == ')') { if (stack.isEmpty()) return false; stack.pop(); } } return stack.isEmpty(); } 먼저 매개변수로 ..
한화시스템 BEYOND SW 캠프 2기 - 5주 차 회고 지난주와 마찬가지로 이번 한 주도 자바를 배웠다. 지난 주와 다른 점이 있다면 기본 문법을 배우는 것에서 더 나아가 조금 어려운 개념인 스트림, 스레드를 학습하고 JDBC와 나중에 스프링을 할 때 중요한 개념이 될 서블릿에 관하여 학습하였다. Java - 입출력 스트림 입출력 스트림 입출력이란 입력(Input)과 출력(Output)을 줄여서 부르는 것으로 두 대상 간의 데이터를 주고받는 것을 의미한다. 데이터를 주고 받을 때 스트림(Stream)이라는 것을 사용하게 되는데 hotechstory.tistory.com Java - 스레드 스레드(Thread) 스레드는 프로세스 내에서 실제 작업을 수행하는 것으로 모든 프로세스는 최소한 하나의 스레드를 ..
50일간 진행한 기록 100일간 알고리즘 문제 풀기를 진행하면서 벌써 50일이나 됐다. 지난 50일간 문제를 푼 것들은 꽤 많았다. 주로 백준에서 문제를 풀었지만, 지금은 프로그래머스에서 문제를 풀고 있다. 여러 기업들의 채용 공고를 살펴보니 프로그래머스를 통해서 코딩 테스트를 본다는 것을 알게 되었고 문제 사이트를 프로그래머스로 옮기게 되었다. 백준과 비슷하게 자료구조와 알고리즘 별로 카테고리가 있어서 한 분야에 집중해서 파고들기 좋을 것 같았다. 백준과 다른 점이 있다면 프로그래머스에는 SQL 코딩 테스트 문제도 있다는 것이다. SQL 쿼리문을 연습하기 어려웠는데 프로그래머스 문제를 풀어보면서 연습도 하고, 부트 캠프에서 공부한 문법도 사용해 보니 더 재밌고 좋았다. 알고리즘은 백준과 프로그래머스에서..
![]()
대체 뭐가 문제야(Are you rights on?) - 제럴드 와인버그 처음 '함께 자라기' 책을 읽고 난 후에 다음 책 정리를 작성하는 데 시간이 오래 걸렸다. 1년간 책 읽기로 했는데 지키지 못한 것은 아니고 책은 계속 꾸준하게 읽어왔다. 글을 올리는데 늦은 이유는 중간에 여러 일이 있고, 이번에 부트캠프도 시작하면서 정리할 시간이 없었기 때문에 정리하는 것이 많이 늦었다...... 지금처럼 잠깐 시간이 남을 때 미리미리 작성을 해야겠다. 이번에 정리할 책은 '대체 뭐가 문제야?'라는 책이다. 처음에 표지를 보고 접근하기 쉬운 책이라고 생각했고 분량도 200페이지 밖에 안되기 때문에 가볍게 읽기 좋겠다고 생각했지만 한참 잘못된 판단이었다. 너무너무너무너무너무 어려운 책이라서 한 번 읽었다고 온전히 ..
![]()
프로그래머스 - 기능개발 카테고리: 스택/큐 레벨: 2 언어: Java 문제 이해하기 입출력 예시 [93, 30, 55]를 가지고 문제를 이해해 보자. 먼저 그림을 그려보면서 이해를 해보면 1칸에 하루가 걸린다고 가정을 해보자. 기능 A를 완료하는 데 걸리는 기간은 7일, 기능 B는 3일, 기능 C는 9일이 걸린다. 하지만 문제에서 나왔던 것처럼 기능 B가 A보다 빨리 끝났다 하더라도 기능 A가 완료되기 전까지 기능 B는 배포가 불가능하다. 7일이 돼서 기능 A가 완료되었다고 하면 먼저 끝난 기능 B와 같이 배포하게 된다. 나머지 기능 C는 9일이나 걸리기 때문에 해당 기능이 완료되면 알아서 배포하게 된다. 문제의 핵심은 어떠한 작업이 있을 경우 그 앞의 기능보다 빨리 끝나냐, 아니냐가 중요하다. 문제 ..
![]()
프로그래머스 - 같은 숫자는 싫어 카테고리: 스택/큐 레벨: 1 문제 풀이 언어: Java 문제 입/출력 예시 문제 풀이 public int[] solution(int []arr) { int[] answer; Stack stack = new Stack(); // Integer 스택 생성 for (int i = 0; i < arr.length; i++) { // 입력값만큼 반복문을 돈다. if (i == 0) stack.push(arr[i]); // 스택에 데이터 삽입 else if (stack.peek() != arr[i]) stack.push(arr[i]); // 최근에 삽입한 데이터가 현재 데이터와 다를 경우 삽입 } answer = new int[stack.size()]; // 최종 스택의 사이즈만..
![]()
스레드(Thread) 스레드는 프로세스 내에서 실제 작업을 수행하는 것으로 모든 프로세스는 최소한 하나의 스레드를 가지고 있다. 스레드의 종류로는 단일 스레드, 멀티 스레드, 데몬 스레드로 나뉜다. 스레드는 공유 메모리를 사용하지만 동일한 메모리를 공유함에도 불구하고 다른 스레드의 작업에 영향을 주지 않는 스레드에 예외가 있는 경우 독립적으로 작동한다. (스레드풀?) 스레드를 사용하는 이유는 멀티 태스킹에 기여할 수 있는 스레드를 사용한다. 멀티 스레드 멀티 스레드는 하나의 자원에 여러 개의 스레드를 붙인 것을 의미한다. 멀티 스레드는 단일 스레드보다 시간이 더 걸릴 수 있는데 그 이유는 중간에 컨택스트 스위칭이 발생하기 때문이다. 멀티 스레드를 주로 사용하는 이유는 하나의 새로운 프로세스를 생성하는 것..
