춤추는 개발자

문제 출처 https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다. www.acmicpc.net 접근 방식 및 풀이 참고 : Baekjoon Online Judge 1451번 풀이 0. 문제 요약 - 직사각형의 크기 : N * M - 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누는 문제 - 모든칸은 하나의 직사각형에 포함되어야한다.(남는 칸이 없어야한다.) - 각 직사..

문제 출처 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 접근 방식 및 풀이 - BFS와 Deque 개념 활용한 문제 - 핵심 알고리즘은 BFS에서 0이면 그냥 가고, 1이면 부수고 가야하므로 dist 배열에 1을 더해주는 것이다. - 프로그래밍에서 배열과 수학에서의 x, y 좌표.. 가 헷갈려서 중간에 런타임에러 엄청 걸렸다. 소스 코드 1 2 3 4 5 6 7 8 9 ..

문제 출처 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 접근 방식 및 풀이 - 완전탐색(brute force), dfs 사용하여 min 값을 계속 갱신한다. - 참고블로그 : #백준_10971 외판원 순회2 - Java 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..

문제 출처 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 접근 방식 및 풀이 - N의 값이 최대 8까지 이므로 배열로 만들수 있는 모든 수열들의 케이스를 조사(순열 개념 적용) - 각 배열로 구한 값들중 가장 큰 값을 출력한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ..

문제 출처 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근 방식 및 풀이 - 1182와 비슷한 문제라고 생각하는 순간 해맨다. -> 같은 알고리즘을 쓰면 시간 초과 발생 - 여러 블로그들을 참고하여 배열의 크기가 크기때문에, 배열을 반으로 나눠 각각 부분합들을 구해준 후 투포인트 알고리즘으로 해결하라는 힌트를 받았다. 참고 블로그 [백준 알고리즘]1208번 부분수열의 합2 백준 알고리즘 부분수열의 합..

문제 출처 https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2 www.acmicpc.net 접근 방식 및 풀이 - 백트래킹 방법, DFS 방법이 있었지만, DFS으로 구현하였다. - DFS로 탐색하다가 6자리 문자열을 다..

개념 출처, 참고 블로그 : https://naivep.tistory.com/52 활용 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net

문제 출처 https://www.acmicpc.net/problem/1963 0){// T가 양수일때 진행 StringTokenizer st = new StringTokenizer(br.readLine()); int A = Integer.parseInt(st.nextToken()); int B = Integer.parseInt(st.nextToken()); if(A==B){ System.out.println(0); continue; } int ret = bfs(A,B); System.out.println(ret); } } private static int bfs(int A, int B){ discovered = new boolean[10000]; Queue queue = new LinkedList(); ..

문제 출처 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 접근 방식 및 풀이 - 투포인트 알고리즘 이용 [Algorithm] - [알고리즘] 투포인트 알고리즘 - 배열의 순서는 움직일수..

문제 출처 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 접근 방식 및 풀이 - 주어진 n만큼의 소수를 구한다. - 구한 소수로 더해가며 n만큼 나오면 count를 증가한다. - ..