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 ..

1. 문제 설명문제 링크2. 풀이 설명idx, idy를 활용해서 배열을 이동시킬 수 있는가에 대한 문제이다.하지만 한 가지 생각해야할 부분은 배열을 이동시킬 때, 중앙에서 가로 갈수록 건너 뛰어야하는 행렬의 GAP이 1씩 커진다는 점이다.이 점만 주의하면 된다.배열 이동 시키는 법은 다음과 같다.초기값을 temp라는 변수에 넣고, 배열을 한 칸씩 이동하여 돌리고, 맨 마지막 행렬 위치에 아까 temp에 넣었던 값을 삽입하면 된다.2번의 이동마다 90도씩 꺾으면 되므로, 반복문을 이용해 idx,idy의 값을 변경해줬다. idx, idy가 무엇인지 모르겠다면, 배열의 방향 전환에 대해서 검색해보고 공부하길 바란다.

1. 시간 복잡도 란?(1) 개념시간 복잡도는 주어진 문제를 해결하는데 필요한 연산 횟수를 말한다.(2) 표기 방법의 종류시간 복잡도를 표기하는 방법에는 다음의 3 가지가 있다.이름설명빅-오메가 표기법문제를 풀기 위해 주어진 상황이 최선의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-세타 표기법문제를 풀기 위해 주어진 상황이 보통의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-오 표기법문제를 풀기 위해 주어진 상황이 최악의 상황일 때 필요한 연산 횟수를 나타내는 표기법예를 들어 설명1~100의 숫자가 랜덤한 순서로 저장된 배열이 주어졌을 때, 해당 배열에서 56의 INDEX를 찾아서 출력하라 라는 문제를 풀어야 한다고 하자.이때 내가 선택한 방법은 배열의 첫 번째 인덱스부터 일일히 조회이다.빅-오..

1. 문제 분석문제 링크N개의 수 중 2개를 뽑아서 그게 M과 맞는지 계산하면 된다고 생각했다.그래서 조합을 사용했다. N이 15000개까지 주어진다. 15000C2 = 112492500 이다.주어진 시간이 2초임으로 20억 번의 계산이 가능한 상황에서 11억의 계산은 Safe다. 따라서 단순 조합을 해도 문제는 풀린다. (시간이 오래 걸렸지만...)나는 DO IT! 알고리즘 코딩테스트 책에서 소개한 투 포인터로도 문제를 풀어 보았다. 투 포인터를 쓰면 정렬 후 최대 N+1 번의 연산이 필요해서 총 N+1 +NlogN = O(NlogN) 의 시간이 든다.이걸 N의 최대 값인 15000으로 계산해보면, 15000 * log(15000) = 62641 개의 연산만 하면 되어서 훨씬 빠르다.두 방법 다 소개해..

1. 문제 분석문제 링크1~N까지 수 중에서 연속된 합으로 N이 나올 수 있는 가짓수 구하기시간 제한 2초, 주어지는 N의 최대값 10,000,000무엇을 최적화라 말하는지 아직 모르겠어서, 이것들의 의미가 와닿지 않는다.2. 푸는 원리투포인터로 풀기연속된 수들의 합을 축척한 변수 acc를 만든다.오른쪽 포인터 b가 움직일 때마다, acc 에 b 만큼 더한다.왼쪽 포인터 a가 움직일 떄마다 acc에서 a 만큼 뺀다.특정 시점에서 acc의 값이 N과 같아졌을 경우, N이 되는 가지수를 하나 센다.문제 푸는 방법은 생각났지만, 세부적으로 a와 b를 acc에 더하는 시점, while 문을 끝내는 시점 등에서 많이 해매서, 답지를 봤다.a와 b가 현재 존재하는 index 부분은 acc에 더해진 부분이라는 것을 ..

1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/2108)산술 평균, 중앙값, 최빈값, 범위를 구하면 된다. 2. 푸는 원리 산술 평균 -> 총합 / 머릿수 중앙값: 중앙에 있는 녀석 계산 최빈값: TreeMap을 사용 Key = 입력 받은 값, value = 해당 값이 나온 횟수, TreeMap은 순서가 보장됨으로, 입력을 한번 정렬한 후에 TreeMap에 넣으면 된다. 범위 : 최대값 - 최소값 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.TreeMap;/* * ..

1. 문제 설명 [ACM호텔 문제링크](https://www.acmicpc.net/problem/10250) 2. 푸는 원리 그냥 반복문 돌리면 된다. 자신감을 되찾기 위해서 풀었다. 3. 코드 분석 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /* * 10250 ACM 호텔 * */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRe..

1. 문제 설명 11729번 하노이 탑 이동 순서 링크 이동 순서를 Log로 찍어야 한다. 2. 푸는 원리 재귀를 이용한다. (0) 재귀함수에는 출발지, 경유지, 도착지, 도착지까지 옮겨야 하는 원판의 번호가 있다. (원판의 번호가 큰 것이 크기가 큰 것이다. 따라서 제일 작은 원판은 번호가 1이다.) (1) 실제로 원판을 옮기는 것이 아니라, 그 이동 순서에 대한 로그만 찍는다. [기저조건] (1)옮겨야하는 원판의 번호가 0이 되면 그냥 return 한다. [계산] (1) 현재 옮겨야할 원판보다 작은 모든 원판을 경유지로 옮기는 Log를 찍는다. (재귀 이용) (2) start와 end를 StringBuilder에 담아서 현재 원판의 이동을 Log로 찍는다. (StringBuilder에 담는 행위 자체..

1. 문제 설명 1874 스택수열 문제 설명 1~N까지 오름차순으로 스택에 하나씩 집어넣는다. 스택에 하나씩 들어올 때, 적절히 POP하여, 문제에서 원하는 수열을 만들 수 있는지 구하라 만들 수 있다면 PUSH = + , POP = - 로 그간 해왔던 명령어를 출력하고, 만들 수 없다면 NO를 출력하라 2. 문제 푸는 방법 A. 첫 번째 방법 (STACK 자료 구조 이용) (1) 답이 되는 수열(이하 ans)과 스택에 입력하는 순서인 오름차순 수열(이하 arr)을 배열에 저장했다. (2) 둘 다 지시자를 가지고 있다. ans의 지시자를 ansIndicator, arr의 지시자를 arrIndicator라고 할 때, ​ a. arrIndicator가 가르키고 있는 것이 ansIndicator보다 작거나 같..

1. 문제 설명 0 만들기 문제 링크 3~9까지 수가 주어지는데, 그 사이 사이에 + 혹은 - 혹은 두 수 붙이기를 사용하여, 총 합을 0으로 만들어라. 2. 푸는 원리 이런 문제는 일일히 char로 분할하여 가지고 있는 것보다, String으로 한번에 가지고 있다가 StringTokenizer로 푸는 것이 좋다는 것을 알았다. (1) DFS를 돌린다. (-> String에 다음 depth의 값을 추가하는 식) (2) 한번은 두 수 사이에 +를 넣고, 한번은 두 수 사이에 -를 넣고 한번은 두 수 사이에 공백을 넣고 경우를 진행한다. (3) 마지막 수까지 String 문자열에 쌓이면, cal이란 이름의 함수에 넣어서 계산한다. (4) cal의 역할은 다음과 같다. ​ a. 공백인 부분을 합쳐서 하나의 수..

1. 문제 분석 [3190 뱀 문제 링크](https://www.acmicpc.net/problem/3190) 지렁이 게임의 원리대로 움직이는 문제 빈 공간은 0, 사과는 1, 뱀이 존재하는 자리는 2로 표시한다. 뱀이 2차원 배열 내를 움직임 -> 움직이니까, 지나간 장소는 2가 아니라 다시 0으로 와야함. 사과를 먹으면 뱀의 몸집이 1 커짐 뱀이 벽에 부딪히면 게임오버 뱀이 자신의 몸에 부딪히면 게임오버 뱀은 방향 전환이 가능 -> 몇 초에 반시계, 시계 방향 중 어디로 움직일지는 주어진다. 게임이 몇 초간 걸리는지 구하기 (뱀은 한 번 움직일 떄, 2차원 배열에서 한 칸 움직이고, 이떄 시간이 1 든다.) 2. 푸는 원리 저기 나오는 1~5를 함수로 작성해서, 함수가 돌아가도록 하면 된다. 처음에는..

1. 문제 설명 (사탕게임 링크)[https://www.acmicpc.net/problem/3085] 캔디 크러쉬 처럼, 서로 다른 종류의 캔디가 보이면 자리를 바꾼다. 그 후, 한 행, 혹은 한 열에서 같은 종류의 캔디끼리 나열되어 있으면 그건 터져서 사라짐. 주어진 2차원 배열에서 한 번 자리를 바꿨을 때 터질 수 있는 최대한의 캔디의 개수를 구하시오 2. 푸는 원리 서로 다른 종류의 캔디를 만나면 자리를 바꾼다. 모든 행을 검사하며, 일련의 연속성을 가진 캔디의 개수를 센다. -> 최고 길이 갱신 모든 열을 검사하며, 일련의 연속성을 가진 캔디의 개수를 센다. -> 최고 길이 갱신 최고 길이를 출력한다. 3. 코드 분석 import java.io.BufferedReader; import java.i..

1. 문제 분석 감소하는 수 문제 링크 321, 952 등 제일 큰 자릿수부터 작은 자릿수로 올수록, 자릿수의 값이 작아지는 경우, 감소하는 수라고 한다. 반면 322, 235 등은 위의 정의에서 벗어나기에 감소하는 수가 아니다. 0을 0번째 감소하는 수, 1을 1번째 감소하는 수, 9를 9번째 감소하는 수 라고 했을 때, 주어진 N에 관하여, N번째 감소하는 수의 값을 구하여라 2. 푸는 원리 조합이다. 하지만 원래의 조합처럼 오름차순으로는 풀 수 없다. (1) 첫번째 자릿수를 고정하고, 그 자릿수를 limit으로 정한다. (2) 조합을 돌며, 두 번째 자릿수는 limit보다 작은 수 중에서 하나를 택한다. (3) 재귀를 돈다. (4) 세 번째 자릿수를 고를 때는 두 번째 자릿수가 넘어설 수 없는 li..

1. 문제 분석 백준 테트로미노 링크 2차원 배열에서 면 대 면으로 붙는 원소끼리 총 4개를 이었을 때, 원소간의 합이 최대값이 되는 경우를 구하여라. 2. 푸는 원리 테트로미노로 나올 수 있는 값들이 미리 나와 있다. 왼쪽 상단부터 1번이라고 하자. 그리고 왼쪽 -> 오른쪽으로 번호를 붙이겠다. 1번부터 4번에 해당하는 블럭은 DFS로 값을 구할 수 있다. 예를 들어보면, 다음과 같다. 하지만 5번의 경우 단순 dfs로 안 풀린다 왜냐하면 두번째 depth 부터 갈 수 있는 길이 2 갈래로 갈라지기 때문이다. 따라서 DFS로는 풀지 못하고, 중앙에서 시작하여 4방 탐색 중 3방을 고르는 조합으로 문제를 풀었다. 3. 코드 분석 import java.io.BufferedReader; import java..

0. 설명 하려는 것 (1) 순열, 조합, 중복 순열, 중복 조합의 정의 (2) JAVA 언어를 썼을 때, 구현 방법 1. 순열 (1) 순열의 뜻 nPr = n 개 중에서 r개를 중복 없이 뽑아서 순서 있게 나열하는 것을 말한다. 따라서 {1, 2, 3, 4, 5} 중 5P3 에서 {1, 2, 3} 과 {1, 3, 2}는 다른 숫자이다. (2) 구현 방법 순열은 재귀로 구현한다. 순열을 재귀로 구현하기 위해서는 다음과 같은 구성요소들이 필요하다. 전체 원소들에 대한 방문 배열 isVisited [] : 순열로 값을 뽑을 때, 중복이 없어야 하므로, 방문 배열을 통해, 이미 방문한 지점은 그냥 지나치도록 구현 해야 한다. 뽑힌 r개의 원소를 담을 배열 output [] : 전체 원소가 담긴 배열을 arr ..

1. 문제 설명 2503번 숫자야구 주소 영수가 숫자 3개를 머릿속으로 생각, 민혁이는 그 숫자를 맞추기 위해 3개의 수를 말하여 N번 추측을 한다. 민혁이가 말한 숫자 중 하나가 영수가 생각한 숫자와 위치도 같고, 숫자도 같으면 1 Strike, 민혁이가 말한 숫자 중 하나가 영수가 생각한 숫자와 위치는 다르지만, 숫자는 같으면 1ball, 이 행위를 N번 반복할 때, 영수가 생각한 숫자 3개가 될 수 있는 후보 수의 개수를 구하여라 2. 문제 푸는 원리 민혁이가 추측한 숫자가 영수의 머릿속 숫자와 얼마나 같은지는, 해당 숫자가 받은 ball_count를 보면 된다. 예시에서, 영수가 생각한 숫자가 324이고, 민혁이가 추측한 수가 429이면 1S 1B이다. 따라서 민혁이가 말한 숫자 N 개의 Ball..

목차 1. 문제 설명 2. 원리 설명 3. 코드 분석 1. 문제 설명 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 2. 원리 설명 해당 문제는 deque라는 양방향에서 add, poll이 가능한 자료구조를 이용하여 문제를 풀었다. 아직 deque가 낯선 분들은 여기로 가서 봐주세요 https://velog.io/@sdk1926/deque%EB%8A%94-%EC%99%9C-%EC%93%B8%EA%B9%8C toggle(boolean) 값을 두었다. 그래서 R이라는 명령어가 들어오면 true, fal..

목차 1. 문제 설명 2. 푼 원리 설명 3. 코드 1. 문제 설명 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 푼 원리 설명 일단 나는 이거 답지 봤다. (1) 팀을 조합으로 반으로 나눈다. -> (2) 각 팀 멤버간의 시너지 계산 -> (3) 차 구해서 그 차가 지금까지의 값 중 최소일 경우 갱신 요거까지는 생각을 했는데, (2)도 조합으로 스타트팀 내에서 2명씩 짝을 잡아서 값을 계산 해야 한다고 생각했다. 그러면 경우의 수가 기하급수적으로 늘어난다...

목차 1. 문제 설명 2. 내가 푼 방법 3. 코드 분석 1. 문제 설명 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 육지하고 바다가 있는데, 해적은 육지로만 갈 수 있다. 육지는 인접할 수 있고, 해적은 대각선을 제외한 사방으로만 움직일 수 있다. 보물은 해적이 걸어서 갈 수 있는 육지 안에 가장 거리가 긴 육지노드에 각각 존재하는데, 이때, 보물 2개를 찾는 최단 거리를 구하시오. 2. 문제 푼 원리 설명 2차원 배열을 돌면서 육지를 만나면..

1. 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2. 풀이에 대한 설명 2차원 배열을 순회하면서, (1) 1을 만난다면! 거기서 부터 해당 1의 상하좌우 중 붙어있는 1이 있는지 확인한다. (아파트 단지 내의 아파트 수 체크) (2) 내가 금방 방문해서 확인한 1은 -1로 값을 바꾸어서 방문 처리한다. (3) 1 search가 끝나면 해당 아파트 단지의 아파트 수를 다 센 것이다. (4) 이때 아파트 수를 aptList라는 아파트 단지..