(1) 정의Red-black Tree를 이용하여 구현한 Key 값을 기준으로 정렬되는 Map이다.정렬 기준은 default로 오름차순이고, 매개변수로 Comparator를 넣으면, 개발자 입맛에 따라 바꿀 수 있다. TreeMap map = new TreeMap((o1,o2) -> (return o1.score - o2.score)); Red-black Tree 란? 이진탐색을 보완하여 성능을 개선한 Tree 자료 구조이다. 이진탐색은 일반적으로 O(logN)의 시간복잡도를 가지지만, 데이터가 한쪽으로 치우쳐서, 일자형 Tree가 나올 경우(ex- 계속 작은 값의 데이터만 입력 등) O(n)이라는 시간복잡도가 든다. 이에 비해 Red-black Tree는 부모노드를 기준으로 큰 값은 오른쪽, 작은..

1. 문제 설명문제 링크2. 접근 방식TreeMap을 이용해서 접근했다.TreeMap은 Key 값을 기준으로 정렬된 자료구조를 말한다. 정렬 기준은 default가 오름 차순이고, 매개변수로 Comparator를 넣어서 바꿀 수 있다. 이때 주의할 것은 대소관계 비교는 "Key" 값으로 이루어진다는 것이다.TreeMap map = new TreeMap((o1,o2) -> (return Integer.compare(o1.score, o2.score)));여기서 주의해야할 점은값에 중복이 있다.최대값, 최소값 중 어느 것도 빠져나갈 수 있다.이다.다행히 TreeMap은 deque처럼 rear부분과 front 부분을 둘 다 조회 가능하다. (삭제도 바로바로 될 것 같은데, 이 부분은 자료 구조를 더 찾아봐야겠..

1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/1167)2. 접근 방식임의의 정점에서 제일 먼 정점은 트리의 지름이 되는 두 개의 점 중 하나이다. 라는 아이디어를 기반으로 문제를 푼다. (위의 Idea가 이해가 안된다면, 한번 예시를 가지고 해보면 된다. 어느 정점에서 출발하든, 그 정점의 제일 먼 정점은 트리의 한 축이다.)시작 정점을 입력하면, 제일 먼 정점과 그까지 갈 때의 거리를 반환하는 bfs 함수를 만든다.해당 함수에 임의의 정점 (제 풀이에선 1)을 넣고, 트리의 지름이 되는 정점을 구한다.반환 받은 정점을 다시 bfs 함수에 입력해서, 입력 정점에서 제일 먼 정점과 그까지 갈 때의 거리를 반환 받는다.해당 거리를 출력한다. 3. 코드 분석import..

1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/2178)2. 접근 방식 BFS의 경우 시작 노드에서 갈 수 있는 가장 가까운 노드 계층부터 우선적으로 가기 때문에, 시작 노드에서 목적지 노드까지 가는 최단 경로로 가는 것을 보장한다. 따라서 해당 문제는 BFS로 푼다. 이전의 BFS문제와의 차이점은 해당 문제가 그래프가 아닌 2차원 배열로 입력값이 주어진다는 것이다. 하지만 다를 것은 없고, `시작 노드에서 위 아래 좌 우 붙어있는 행렬 값` == `인접 정점` 이라고 생각하면 된다. 문제는 다음과 같이 풀었다. ArrayDeque를 만들어서, 시작 행렬을 집어넣는다.ArrayDeque가 빌 때까지 큐안의 값을 꺼내서, 사방 탐색하고, 미방문 행렬의 경우 queu..

(0) 그래프란?a. 정의값을 담고 있는 정점(Vertex)와 그 정점들을 잇는 간선(Edge)으로 이루어져 있는 자료구조b. 그래프 관련 용어용어뜻정점(Vertex or Node)데이터를 저장하는 곳간선(Edge)정점과 정점을 잇는 선인접하다.정점 A와 B가 간선으로 이어져 있으면, 정점 A와 B는 서로 인접하다.라고 한다. 인접 정점: 하나의 정점 A와 간선으로 이어져 있는 정점들을 인접정점이라고 한다. 위의 예시에서 B는 A의 인접정점이다.차수하나의 정점 A와 연결된 간선의 개수이다. a의 예시에서 정점2의 차수는 3이고 정점4의 차수는 4이다. 진입 차수: 방향이 있는 그래프에서 외부로부터 들어오는 간선의 개수를 말한다. 진출 차수: 방향이 있는 그래프에서 외부로 뻗어나가는 간선의..

1. 문제 설명문제 링크문제 설명이 조금 직관적이진 않은데, A는 친구의 친구를 흘러가서 E까지 친구가 된다. 즉 DFS로 했을 때, 깊이가 5까지 가는 관계가 있는지 찾는 문제이다.2. 접근 방식문제에 나와 있듯이, 임의의 시작 노드를 선정해서, 거기서부터 깊이가 5인 DFS 재귀가 성립하는 게 있으면 1, 모든 노드를 시작 노드로 두고 해도, 깊이가 5인 재귀가 성립하지 않으면 0을 출력하면 된다.3. 코드 분석import java.io.*;import java.util.ArrayList;import java.util.StringTokenizer;public class Main { static int N, M; static ArrayList[] lists; static boolean ..

1. 문제 설명문제 링크2. 접근 방식두 가지 함수를 이용해 문제를 푼다.DFS : 현재 수가 소수가 맞다면, 오른쪽의 자릿수를 하나 늘려서 재귀 한다. (문제에서 요구한 자릿수 까지 반복)소수 판별: 주어진 수가 N이라면 2~ √N까지의 수로 N을 나누었을 때, 나머지가 0이면 false, 하나도 나머지가 0이 안되면 소수임으로 true를 반환한다.해당 함수들을 이용해, 현재 자릿수까지 소수인지 판별 후 그 다음 자릿수로 넘어간다.3. 코드 분석import java.io.*;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.BitSet;import java.util.StringTokenizer;public class Main..

1. 하나의 숫자에 대한 소수 판별(1) 방법만약 소수인지 판별해야할 숫자를 N이라고 한다면, 다음과 같은 방법으로 N이 소수인지 여부를 판별할 수 있다.int N = Integer.parseInt(br.readLine());for(int i = 2; i(2) 왜 √N까지만 확인하면 되나요?'N에게 약수가 존재한다면, 약수는 곱해서 N을 만들 수 있는 각자의 짝이 존재한다. 짝이 되는 약수의 쌍을 (A,B)라 할 때, A가 √N보다 작다면, B는 √N보다 크다.'위의 성질을 이용해서, √N의 이하만 확인한다. 만약 √N 이하인 부분에서 1을 제외한 어떠한 수도 N을 나눌 수 없다면, √N 이상의 반대편에서도 N 자신을 제외한 어떤 수도 N을 나눌 수 없음이 증명된다. 따라서 N은 소수임이 판명된다.예시 ..

1. 문제 설명문제링크2. 접근 방식기수 정렬을 이용해서 문제를 풀려고 했다. 근데, 다른 사람들의 질문을 보니, 예전에는 기수 정렬을 이용해 문제가 풀렸으나, 메모리 제한이 생긴 이후로 풀리지 않는다고 한다. 문제에서 주어지는 데이터의 크기는 10,000,000 개이고, 하나의 데이터를 int 배열의 원소로 넣어서 보관한다면, 총 40MB가 든다. (밑에 보면, java의 경우 512MB까지 용량 허용된다고 적혀있는데, 똑같이 안된다.)기수 정렬의 공간 복잡도는 O(W+n)으로 40MB의 경우 문제에서 주는 메모리 용량을 초과한다. 내가 ArrayDeque 10개를 활용해 기수 정렬을 구현하는 바람에 오류가 났나 싶어서, 코딩 테스트 책에 있는 풀이를 똑같이 구현하였으나, 그건 또 시간초과가 났다.하지..

1. Token 인증 방식이 어떻게 이루어 지는가회원이 로그인을 시도한다고 가정해보자.ⓐ Client가 ID/PW 로그인 창에 써서 제출한다. ⓑ Server가 DB를 통해 해당 ID/PW를 가진 회원이 있는지 확인한다. 여기서 해당 회원의 정보가 우리 DB에 있어서 우리 회원인 것이 확인 되었다고 가정해보자. ⓒ Server에서 해당 회원의 정보를 이용하여 고유한 Token을 만든다. ⓓ 그리고 해당 토큰을 아까 유효한 요청을 한 클라이언트에게 보내준다. ⓔ 이제 클라이언트는 인증이 필요한 API를 이용할 경우 해당 Token을 요청 Header에 동봉하여 같이 보낸다. ⓕ 이제 서버에서는 해당 Token의 유효성을 검증 후 유효한 토큰이 맞다면 응답으로 요청한 내용에 대한 정상 답변을 보내주면 된..

1. 문제 설명문제 링크2. 접근 방식quick 정렬을 이용해 문제를 풀었다. 하지만 기본적인 quick sort로 문제를 풀면 시간초과가 난다. quick sort의 최악 시간복잡도는 O(n^2) 인데, 데이터의 크기가 5,000,000 이라 n^2를 하면 2 억번의 계산을 훌쩍 넘기 때문이다.따라서 O(nlogn)의 다른 정렬을 쓰거나, quick sort를 최적화 해줘야 한다. 나는 quick sort를 최적화하는 방향을 선택했다. 해당 문제는 k번째 index의 수가 무엇인지만 구하면 되는 문제이므로, 모든 배열을 정렬시킬 필요가 없다. 따라서 이분 탐색처럼 구역을 나눠서, 필요 없는 부분의 정렬은 하지 않는다.K번째 수를 알아내면 거기서 종료한다. ⓐ 현재 정렬하려는 범위의 중앙값을 pivot으..

1. 문제 설명문제 링크2. 접근 방식슬라이딩 윈도우와 자료구조 덱큐를 이용한다. 해당 문제는 데이터의 개수가 이미 10^6이라서 O(n) 안에 문제를 해결 해야한다. 이 문제를 윈도우 안에 있는 값들을 최소값 정렬해서 풀려는 사람들이 있을지 모르는데, 정렬은 O(nlogn)이 들어서 시간초과가 난다.따라서 덱을 이용해 정렬의 효과를 내야한다. 덱큐의 조건은 다음과 같다. 현재 바라보고 있는 값을 덱큐에 넣을 예정이다.(1) 만약 덱큐의 꼬리의 있는 값보다 현재 넣으려고 하는 값이 작으면 꼬리에 있는 값을 제거한다.(2) 어짜피 슬라이딩 윈도우 기준 제일 오른쪽에 있는 값이 더 작다면 그것보다 왼쪽에 있는 값이 클 경우, 쓸모가 없다. 어짜피 슬리이딩 윈도우가 이동하는 내내, 현재 원소보다 상대적으로 왼..

1. 문제 설명문제 링크2. 접근 방식0. 사전 세팅Node Class : 멤버 변수로 index와 value를 가지고 있다. index는 입력에서 해당 값이 나온 순서를 저장하고, value는 실제 값을 저장한다. NGE 배열 : index에 해당하는 입력 값의 오큰수가 무엇인지 저장한다. top : stack을 배열로 구현하였기 때문에 top이 어디인지 알려줄 변수로 사용했다. 1. 원리stack이 비어있으면 현재 조회 중인 입력값을 넣는다. stack이 비어있지 않은 경우 stack.top과 현재 조회 중인 입력값(A)를 비교한다.stack.top stack.top의 오큰수는 A이므로 NGE 배열의 top의 index에 A를 저장한다.stack.top의 오큰수는 정해졌음으로 pop하고, 그 다음..

1. 문제 설명문제 링크2. 접근 방식삽입 정렬을 이용하여 문제를 풀어보았다.정렬된 영역에서 현재 값을 삽입할 위치 선택을 위해 단순 반복문을 사용하는 것보다 이진 탐색을 사용하는 것이 그나마 시간이 빠를 것 같아서, 이진 탐색을 이용했다.이진 탐색에서 중간 값보다 작았을 시, 클 시 start나 end에 그냥 mid를 더해줘서 무한 Loop에 빠지는 실수를 범했다.start = mid +1, end = mid -1로 해주어서 start= 0, mid = 1인 경우를 대비해줘야 한다. 3. 코드 분석import java.io.*;import java.util.ArrayList;import java.util.StringTokenizer;public class Main { public static vo..

1. 문제 분석[문제 링크](https://www.acmicpc.net/problem/1253)2. 접근 방식배열의 양 끝에 포인터를 둔다. 현재 Good이 되는 수인지 검산 한다. (포인터 2개의 합이 현재 검산 중인 수보다 크면 오른쪽 포인터를 한 칸 내린다.) (포인터 2개의 합이 현재 검산 중인 수보다 작으면 왼쪽 포인터를 한 칸 올린다.)숫자는 음수도 가능하므로, 제약없이 전체에 대해서 계산 해야한다. 이는 O(n^2)의 시간 복잡도가 들지만, 계산해야할 총 데이터 수가 2000 이므로 10^3 이라 계산이 괜찮다. 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;im..

1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/2018)2. 접근 방식투포인터 문제 투 포인터 구간 안에 합을 변수 acc에 저장한다.acc acc > N 이면 왼쪽 포인터를 한 칸 움직여서 그 값을 acc에 더한다. 이렇게 오른쪽 포인터가 구간의 맨 끝에 도달할 때까지 반복하며 acc == N 인 경우를 센다.3. 코드 분석 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedRead..

1. 문제 설명문제 링크2. 접근 방식해당 문제는 주어지는수의 개수가 10^5 개이다. 이는 n^2만 해도 1억 번의 계산을 넘어서, 시간초과가 날 것이다. 만약 값을 입력 받으면서, 그 전에 받았던 입력들을 일일히 조회하여 구간합을 구한다면, 이는 n^2로 시간 초과가 난다. 누적 합 배열을 이용해 구간 합을 O(1) 안에 구한다.sum[] 이라는 배열을 만든다. sum[i]는 sum[0] ~sum[i]까지의 합이다.sum[i] = sum[i-1] + arr[i] (현재값) 으로 구할 수 있다. i ~ j 까지의 구간합을 구해야할 경우 (i 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream..

1. 문제 설명문제 링크2. 접근 방식sum[i] [j] = (0,0) ~ (i,j) 까지의 합으로 나타냈다.i = 0 인 열은 이전 행의 최대 값을 저장하도록 해서, 누적합이 계속 이어지도록 만들었다.하지만 구간 합 (a,b) ~ (c,d)를 구하라 함은, a 그래서 나는 다음과 같이 구했다.다음과 같이 푸른색 형광펜에서 보라색 형광펜 값을 빼주고 그 결과들을 더 했다.3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] ar..

1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/11720)문제N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.입력첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.출력입력으로 주어진 숫자 N개의 합을 출력한다.예제 입력 1 복사11예제 출력 1 복사12. 접근 방식숫자는 모두 한 자릿수 이다. 길이가 10인 배열을 만들어서 index -> 숫자, value -> 숫자의 개수를 저장한다.String 문자열 한 줄로 들어온 숫자들을 모두 체크한 이후에, 길이 10의 배열을 순회하면서 index* value의 총합을 구한다. 3. 코드 분석import java.io.Buffe..

1. 문제 설명문제링크8진수 -> 2진수2. 접근 방식8진수 → 2진수로 변환하는 방법은 다음과 같다.ⓐ 8진수 각 자리를 떼어낸다.ⓑ 각 자릿수를 2진수로 바꾼다. (한자리는 0~8 사이의 수임으로 2진수로 바꿀 시, 2진수는 무조건 3자리 이하임)ⓒ 2진수로 바꾼 수를 이어 붙인다. (이때, 모든 2진수는 3자리를 차지해야한다. 아니면 전혀 상관 없는 이상한 수가 된다.)3. 코드 분석import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea..

1. 문제 설명문제 링크카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다."[닉네임]님이 들어왔습니다."채팅방에서 누군가 나가면 다음 메시지가 출력된다."[닉네임]님이 나갔습니다."채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.채팅방에서 닉네임을 변경한다.닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.예를 들어, 채팅방에 ..