쿠쿠의 개발일지

2021년 첫 회고를 써본다. 블로그에 문제풀이 및 알고리즘 공부한 걸 올려보는데 글 쓴다는 게 쉽지 않은 것 같다. 회고록은 그냥 느낌대로 카테고리따라 끄적끄적 써보겠다. 중간까지 썼는데 사진 올리다 뭐 잘못해서 다 날려먹었다. 퇴사 2019년 대학을 갓 졸업하고 측정장비 제어 회사에 운 좋게 들어가게 되었다. 첫 직장인지라 엄청난 걱정반 기대 반을 가지고 회사에 갔는데 젊은 사람도 많았고 내가 속해 있는 팀이 너무 잘해줘서 열심히하구 무난 무난하게 생활한 것 같았다. 월급도 마냥 나쁘지도 않고 집이랑 10분 거리인 회사를 내가 퇴사를 해야겠다고 다짐을 한 계기는 좀 더 높은 곳에 가고 싶은 욕심이 생겼다. 회사 특성상 출장이 많아 여러 기업에 가봤다. 특히 삼성에 많이 갔는데 건물도 높고 밥도 진짜 ..

[문제] 출처 - https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [문제 풀이] 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수 들이 있다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하면 된다. 자연수가 주어지고 연속된이라는 점에서 투포인터를 사용 할 수 있다. N이라는 자연수가 주어졌을때 N보다 작거나 같은 소수들을 리스트에 담아야 한다. 에라토스테네스의 체 사용 투포인터를 움직일때 리스트의 범위를 잘 지켜야 한다! [소스 코드] import java.io.*; import java.util.*; publi..

[문제] -출처 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N 해당 풀이 연속된 수들의 부분합 중에 그 합이 S 이상 되는 것중 가장 짧은 것의 길이를 구하는 문제이다. 연속된 수이고 자연수로 이루어져있으니 투 포인터를 이용하여 쉽게 해결 할 수 있는 문제이다. 두가지 조건만 잘 지키면 된다. 합이 S 이상 가장 짧은 것의 길이 import jav..

[문제] 출처 - https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net [문제 풀이 전] N = Target) Left++; (2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 해줍니다. (부분 배열의 길이를 늘려 합을 더한다.) if(sum < Target) Right++; (3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1 해줍니다. if( sum == Tar..

[문제] 출처 - https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net [문제 풀이] 위에부터 아래로 내려가면서 값을 더하며 최하단층에서 가장 최댓값을 구한다고 생각을 한다. 이 아이디어를 토대로 점화식을 d[i][j] = (i,j) 에 도착했을 때 합의 최댓값이라고 설정한다. 어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위, 오른쪽 위에 있는 것 즉 ( i , j )가 선택되기 전에 선택된 수는 왼쪽 위 ( i-1, j-1) 오른쪽 위 ( i-1, j )이고 D[i][j] = Max(D[i-1][j] , D[i-1..

문제 출처 - 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..