쿠쿠의 개발일지

[문제] 출처 - https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net [문제 풀이] 최단 경로를 찾는 BFS로 해결할 수 있다. 만약 모든 벽을 0으로 바꾸고 찾게 된다면 N과 M 제한 조건에 의해 (1000*1000)^2의 복잡도를 가지게 되어 시간 초과가 된다. 이 문제의 핵심은 벽을 부수고 이동하는 것이 빠르면, 벽을 한 개 까지 부수고 이동하여도 된다 라는 조건이 있다. 즉 어떤 지점에 도착했을 때 벽을 부수고 온 ..

[문제] 출처 - https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr [문제 풀이] 이 문제는 소수를 판단하는 함수와 dfs방식으로 찾는 함수를 만들어서 구현을 해준다. dfs함수를 구현할때 String 값을 Integer값으로 변경하여 찾을 수 있는 값 전부를 중복없이 리스트에 담아주고 리스트에 담긴 값들을 소수판단하여 세주면 된다. 백트래킹 방법 사용 for문을 사용해 ..

퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. -출처 위키백과 백트래킹(Backtracking) 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 입니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다. 즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 입니다. 주로 문제 풀이에서는 재귀로 모든 경우의 수를 탐색하는 과정에서 답이 절대로 될 수 없는 상황을 정의하고 그 경우 ..

[문제] 출처 - https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [문제 풀이] 이 문제는 BFS 와 구현을 해야한다. 그래서 다소 어렵게 느껴졌다. 모든 좌표에 대하여 BFS 탐색을 시작한다. 국경선을 공유하는 두 나라의 인구차이 L명 이상 R명 이하면 방문처리를 한다. ArrayList를 사용하여 방문한 좌표값을 기록한다. BFS 탐색이 끝나면 List에 있는 좌표값을 이용해 각 칸의 인구수를 (연합의 인구수) / (연합을 이..

[문제] 출처 - https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net [문제 풀이] 백준 부분수열의 합 이라는 문제와 같지만 N제한이 최대 40이다. 백트래킹 방법을 사용하면 2^40 의 방법이 나와서 이 방법으로는 해결할 수 없다. 전체 수열을 절반으로 쪼개어 모든 방법을 구해야 한다. 2^20 + 2^20 = 1048576*2 이므로 모든 경우를 구할 수 있다. 주어진 N개의 배열을 반으로 쪼개고 그 모든..

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