쿠쿠의 개발일지

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 풀이 주어진 n 제한이 20이하로 작은 수 이다. -> 완전탐색을 생각할 수 있다. '-' 인경우, '+' 인 경우 두 가지를 '선택' 하여 타겟 넘버를 만들 수 있다. 따라서 조합을 사용하여 모든 경우를 체크할 수 있다. 시간복잡도 O(2^20) 인덱스는 배열의..

[문제] 출처 - https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net [문제 풀이 전] 순열의 정의 : 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다 (위키백과) 크기가 N인 수열이 서로 다른 순열은 총 N! 개가 있다. 모든 순열을 사전순으로 나열했을 때 A = { 1 , 2, 3 } 인 경우 사전 순은 다음과 같다. 1 2 3 = i 이면서 A[j] > A [i-1]을 만족하는 가장 큰 j를 찾는다. A[i-1] 보다 큰 수 중 가장 작은 수 A [j] = 4 ---> 7 2 3 6 5 4 1..

[문제] 출처 - https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net [문제 풀이] 최댓값을 찾는 문제이므로. 입력으로 받은 단어의 자릿수를 만들고 각 단어의 합을 구하여 높은 값부터 대입해준다. EX) ABC + DEF = 100A + 10B + 1C + 100D+ 10E + 1F = 100A + 100D + 10B + 10E + 1C + 1F => 100A + 100D + 10B + 10E + 1C + 1F => A = 9 , D = 8 ..

[문제] 출처 - https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net [문제 풀이] 왼쪽 아래 꼭짓점 x1, y1 오른쪽 위 꼭짓점의 x2, y2 좌표값을 for문으로 직사각형 배열의 값을 1로 만든다. 값이 0인 지점에서 DFS를 하여 새로운 영역 개수를 저장할 ArrayList와 그 영역의 크기를 저장할 Count 값 선언 M과N 으로 주어졌지만 NM으로 하는 게 편해서 NM으로 설정하였습니다. [소스 코드] import j..

[문제] 출처 - https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [문제 풀이] DP를 사용해서 풀 수 있지만 N 조건이 15 이하라 사용하여 해결할 수 있다. 해당 날에 일을 할 수 있다/없다 라는 조건으로 계산한다. 최대 2^15 = 32768 이기 때문에 가능하다. 1. 정답을 찾은 경우 // 2. 불가능한 경우 // 3. 다음 경우 세 가지를 구현하여 문제를 풀 것이다. 아래 소스 코드와 주석을 참고하면 된다. [소스 코드] import java.io.*; import java.util.*; public class Main { static int t[]; static int..

[문제] 출처 - https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net N극(0) S극(1) 중을 하나를 나타내는 4개의 톱니바퀴를 회전시켜야 한다. 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 서로의 극이 같은 경우에는 회전시키지 않고, 다른 경우에만 회전을 시킨다. 극을 비교할 때에는 2번 6번 방향을 기준으로 한다. [문제 풀이] 시뮬레이션은 문제의 조건을 잘 읽고 그대로 이행을 해줘야 ..

문제 출처 - https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 N제한이 8이라는 매우 작은 수 3개의 벽을 세우는 모든 경우의 수를 만드는 DFS 벽을 만들고 바이러스를 퍼트리는 과정의 BFS -> 인접한 다른 정점으로 갈때 가중치가 1 *주의!! = 원본 배열을 바꾸면 안되기 때문에 복사된 배열을 사용해야 하는데 a = b 와 같은 대입연산자를 사용하면 얕은 복사가 생겨 원본 배열 값에 영향을 미치기 때문에 깊은복사를 해야한다. 문제를에 벽의개..

[문제] https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [문제 풀이] 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하기. 주의해야 할 점은 음수를 제외한 연속합이 최대이지 않을까라고 생각을 할 수 있는데 음수를 포함해도 연속합이 커지는 경우가 있다. ex) 3 -1 3 최대합 : 5 문제를 참고하여 D[i] = i 번째 수로 끝나는 가장 큰 연속합이라는 점화식을 세울 수 있다. A[i] A[i-1] A[i] A[i-2] A[i-1..