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 == 64라면,√N은 8이다.ab = 64라면  √N 은 8*8 처럼 a와 b가 같은 수이다.만약 a 따라서 a √N 이 되면 반자동적으로 b > √N 이 된다.따라서 만약에 특정 수 N에 대하여 2 ~ √N까지의 수 중에 나누어 떨어지는 수가 없다면, √N보다 큰 수 중에서도 나누었을 때, 나누어 떨어지는 숫자가 없다는 말이다.왜냐하면 2 ~ √N의 수 중 N을 나누었을 때, 나누어 떨어지는 a란 수가 ..

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

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

1. 문제 설명문제 링크당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.첫 번째(3번), 두 번째(1번) 폰켓몬을 선택첫 번째(3번), 세 번째(2번) 폰켓몬을 ..

1. 문제 설명문제 링크1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.이전에 등장했던 단어는 사용할 수 없습니다.한 글자인 단어는 인정되지 않습니다.다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.tank → kick → know → wheel → land → dream → mother → robot → tank위 끝말잇기는 다음과 같이 진행됩니다.1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.2번 사람이 자신의 첫 번째 차례에 kic..

1. 문제 설명문제 링크하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.한 번에 하나의 원판만 옮길 수 있습니다.큰 원판이 작은 원판 위에 있어서는 안됩니다.하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원..

1. 문제 설명문제 링크문제 설명가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다타일을 가로로 배치 하는 경우타일을 세로로 배치 하는 경우예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.제한사항가로의 길이 n은 5,000이하의 자연수 입니다.경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.입출력 예nresult411입..

1. 문제 설명[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/12977?language=java)주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.제한사항nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.입출력 예numsresult[1,2,3,4]1[1,2,7,6,4]4입출력 예 설명입출력 예 #1 ..