개발개발

1. 문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 2. 풀이 투포인터를 사용해 풀이한다. A의 부분합과 B의 부분합의 합을 구해야하는 상황이므로 A의 부분합과 B의 부분합을 미리 구해놓고 A의 부분합과 B의 부분합을 각각 정렬해 투포인터를 이용해 합이 T일 경우, answer에 추가한다 +) A의 부분합과 B의 부분합이 중복될 경우 한번에 처리해주기 위해,..

1. 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 코드 import java.util.Scanner; // 백트래킹 public class Main { static int answer = 0; public static void nQueen(int[] arr, int n, int depth) { if(n == depth) { answer++; return; } for(int i = 0; i < n; i++) { // 한 row에서 퀸을 놓을 수 있..

1. 문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이 이진탐색을 사용한다. 새롭게 해야 하는 게임의 수를 이진탐색을 사용해서 찾는다. 소숫점을 버리기 위해 새로한 게임을 포함한 승률을 구하는 가정에서 100을 곱하게 되는데, 이 때 int 범위의 수가 넘을 수 있으므로 long 처리를 해줘야 된다는 것을 주의 해야 한다. 3. 코드 import java.util.Scanner; //이진탐색 public class Main..

1. 문제 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 2. 풀이 투포인터와 BFS를 모두 활용한다. 구해야 되는 것은 가장 작은 고도의 차이므로, 가장 높은 고도(high)와 가장 낮은 고도(low)를 설정해 그 고도 내에서 집배원이 모든 집을 방문할 수 있는지 본다. 투포인터를 이용해 low 값 과 high 값을 변경해가며 가장 작은 고도차를 찾는다. 고도 내에서 모든 집을 방문할수 있는지 확인 할 때 BFS를 사용한다..

1. 문제 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 2. 풀이 숫자가 A, B, C, D 총 네종류가 있고 합이 0이 되는 A, B, C, D 쌍을 구해야 한다. 이를 A와 B의 가능한 모든 합과 C와 D의 가능한 모든 합으로 나누어 구하고 A와 B의 합과 C와 D의 합 중 0이 되는 쌍을 찾는다. 즉, (A+B) + (C+D) 이런식으로 나누어 생각하는 것이다. A와 B의 합과 C와 D의 합은 가능한 모든 경우의 수를..

1. 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 2. 풀이 방법 1) 우선 순위 큐 사용 자바로 우선 순위 큐를 사용해 정렬 된 값을 바로 사용해서 하려고 했더니 시간 초과가 난다. 자바로 풀기 위해 다른 방법을 찾아 봤다. 방법 2) Deque 사용 숫자가 있는 위치와 숫자의 값을 모두 Deque에 넣어 풀이하는 방법이다. (1) 현재 숫자를 입력 받는다. (2) 현재 덱 내에 있는 수 중 뒤에서 부..

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 45 46 47 48 49 50 51 52 53 54 #include #include #define MAX 1001 using namespace std; char map[MAX][MAX]; struct point { int row, col; bool isBroken; // 벽 부쉈으면 true int length; // 이동 거리 }; int BFS(int rowSize, int colSize) { int moveDir[4][2] = { { 1, 0 },{ -1, 0 },{ 0, 1 },..

1. 문제 https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 2. 코드 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 #include #include #include using namespace std; int main() { int t; cin >> t; // 이때, 정수 값 뒤 누른 엔터가 그대로 남아있어 getline에 들어감 string s, temp..

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 #include #include #include #include using namespace std; int main() { int t; cin >> t; string cloth, kind; while (t--) { int n; cin >> n; map m; // 옷 종류와 종류별 수를 담는 map while (n--) { cin >> cloth >> kind; m[kind]++; // 옷 종류별 수 갱신 } long long res = 1; for(auto it = m.begin(); it != m.end(); it++){ res *= it->second + 1; ..

1.문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 풀이 가장 긴 증가하는 부분수열은 LIS(Longest Increasing Sequence)로 매우 유명한 알고리즘이다. DP를 이용하는 문제는 매번 어렵다. 문제에는 두가지 배열이 있다. 숫자들의 나열이 담긴 배열 현재 인덱스에 해당하는 숫자까지의 LIS를 저장하는 배열 문제에서 2)의 배열에서 이전까지..