본문 바로가기

CS/Algorithm

(알고리즘) 레드블랙트리 2021. 3. 31. 21:27 이번 포스팅은 레드 블랙 트리를 포스팅할 예정이다. 레드 블랙트리를 포스팅하는 이유는 Java를 더 잘 이해하기 위해서이다. Java의 HashMap 사이즈가 64가 넘을 때에 레드 블랙트리를 사용하고 TreeMap 또한 레드 블랙트리를 사용하기 때문에 해당 코드를 이해하기 위해서 우선적으로 레드 블랙트리에 대한 이해가 선행되어야 함을 깨달았다. 조금 힘들더라도 내실있는 포스팅을 해보도록 노력하겠다! 레드 블랙트리는 왜 쓰는가? 이진 탐색 트리의 단점을 보완하기 위해서 쓰는 자료구조이다. 만약에 정렬된 데이터를 이진 탐색 트리로 구현한다면 아래와 같은 구조일 것이다. (이미 정렬된 데이터에 대해서는 비효율적인 자료구조) 그렇다면 시간복잡도를 따진다면 O(n) 이 나오게 된다. 결코 좋은 시간 복잡도라고 ..
(알고리즘) 프로그래머스 - 오픈채팅방 2020. 11. 4. 12:05 programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 더보기 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. [닉네임]님이 들어왔습..
(알고리즘) boj - 치킨배달 (15686) 2020. 11. 4. 08:51 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이과정 문제 설명 각각의 치킨집의 위치와 도시의 위치가 주어진다. 치킨집의 개수가 주어진다. (치킨집의 개수 = 뽑아야 할 치킨집 개수) 도시를 기준으로 치킨집 간의 최소 거리를 구한 다음에 최소 거리를 합해서 최소한의 도시의 치킨 거리를 구한다. 문제에서 가장 중요한 것은 치킨집을 뽑는 것이다. 모든 경우를 뽑을 필요는 없기 때문에 순서가 있는 조합을 사용하는 게 핵심이다. jwdeve..
(알고리즘) boj - 뱀 (3190) 2020. 10. 22. 10:53 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 과정 문제 설명 벽을 만나거나 뱀 자신에게 닿으면 종료 다음칸에 사과가 있다면 뱀의 길이를 늘린다. 뱀의 머리를 사과 있는 칸으로 머리를 이동 다음칸에 사과가 없다면 뱀의 길이를 늘리지 않는다. 뱀의 꼬리를 자르고 사과 있는 칸으로 머리를 이동 특정 시간에 VALUE가 D이면 머리를 우측으로 L이면 좌측으로 이동 머리 회전은 이동 후에 진행된다. 필자는 벽과 뱀이 지나간 자리를 모두 2로 설정하였고 다음칸이 2면..
(알고리즘) N과 M (4) - 중복조합 2020. 10. 21. 01:31 www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 조합은 순서에 대한 구분이 따로 없으며 이 조건에서 앞의 문제와 같이 중복을 허용하면 된다. 이를 위해서 기존 조합 문제와는 달리 i에 +1을 하지 않는다. 소스 코드 public class Problem_15652 { private static int n; private static int m; private static int[] arr; public static void main(String[..
(알고리즘) N과 M (3) - 중복순열 2020. 10. 21. 01:18 www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 이전에 순열은 순서가 있지만 중복은 허용하지 않았다. 중복을 허용하지 않았다는 말은 자기 자신을 포함하지 않았다는 말을 의미한다. ex) [1, 1] [2, 2] [3, 3]...... 중복 순열을 구현할 땐 단지 이전에 구현하였던 순열에 방문 노드 로직만 제거하면 된다. public class Problem_15649 { private static int n; private static int m..
(알고리즘) N과 M (2) - 조합 2020. 10. 21. 01:00 www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 이 문제는 이전에 앞전에 포스팅하였던 내용 중 순서가 없는 조합에 대한 문제이다. 조합에 대한 문제는 따로 방문노드를 설정할 필요 없이 depth와 인덱스 값만 들고 다니면 된다. jwdeveloper.tistory.com/270 (알고리즘) 순열과 조합의 차이 순열과 조합의 차이는 무엇인가? 순열을 알아보기 전에 순열과 조합의 차이를 먼저 알아보자! 순열과 조합의 가장 큰 차이는 순서가 있고 없고..
(알고리즘) N과 M (1) - 순열 2020. 10. 20. 23:27 www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 순열에 대한 문제이다. 이전 포스팅에서 언급하였다시피 순열은 순서가 있는 배열이며 DFS를 사용하여 풀이를 할 수 있다. jwdeveloper.tistory.com/270 (알고리즘) 순열과 조합의 차이 순열과 조합의 차이는 무엇인가? 순열을 알아보기 전에 순열과 조합의 차이를 먼저 알아보자! 순열과 조합의 가장 큰 차이는 순서가 있고 없고 이다. 예를 들어 자전거의 번호가 있는 자물쇠를 � jwd..
(알고리즘) 순열과 조합의 차이 2020. 10. 20. 10:05 순열과 조합의 차이는 무엇인가? 순열을 알아보기 전에 순열과 조합의 차이를 먼저 알아보자! 순열과 조합의 가장 큰 차이는 순서가 있고 없고 이다. 예를 들어 자전거의 번호가 있는 자물쇠를 연다고 가정해보자. 자물쇠 번호가 1234라고 한다면 순서에 대한 고려 없이 4321을 입력하면 자물쇠는 열리지 않는다. 이를 순열이라고 한다. (순서가 있음) 또 다른 예시로 닭가슴살 샐러드를 가정해보자. 닭가슴살 샐러드의 재료는 닭가슴살, 양상추, 소스, 토마토라고 한다면 우리는 샐러드를 담을 때 닭가슴살을 처음으로 넣고 두 번째는 양상추... 이런 식으로 넣지 않고 그냥 재료에 맞게 넣는다. 이를 조합이라고 한다. (순서가 없음) 이제 수학적으로 다가가 보자 1 2 3 4 배열이 있고 2가지 경우를 뽑는다고 가정해..
(알고리즘) 정렬 (3) - 퀵정렬 2020. 2. 26. 00:18 퀵 정렬이란? 풀기 힘든 문제를 풀기 쉽게 작은 단위로 점점 더 쪼개서 정렬을 수행하는 알고리즘 작은 단위로 쪼개는 과정은 파티셔닝을 통해 이루어진다. 기준되는 값을 하나 정해서 큰 값은 우측 작은 값은 좌측으로 정렬하면서 해당 작업이 끝나면 기준값을 기준으로 좌측 우측의 기준값을 또다시 설정하여 해당 과정을 반복하여 결국은 정렬이 이루어지는 알고리즘이다. 아래를 예시로 해당 알고리즘을 설명해보자 기준값을 기준으로 나누기 현재 배열의 길이는 9이다. pl을 왼쪽 커서 pr을 왼쪽 커서라고 지칭하겠다. 또한 기준값은 배열의 절반이라고 명시한다. 1. pl, pr, 기준값 설정 2. pl이 기준값보다 클 때까지 계속 전진! pr은 기준값보다 작을 때까지 계속 전진! 현재 pl은 8을 만났고 pr은 3을 만났..

티스토리툴바