SH

BOJ Link https://www.acmicpc.net/problem/1758  풀이 과정순서에따라 받을돈에 0..-1..-2..-(N-1) 원이 차감된다. 이 때 합(받을돈-차감된 돈)이 음수일 경우, 0으로 치기 때문에 그리디하게 풀 수 있다. 그렇지 않다면 순서에 상관없이 똑같은 돈을 받을 것이다. 따라서, 내림차순으로 정렬하여 합을 누적하고 출력한다. 제출 코드#include #include #include #include int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; std::cin >> N; std::vector vec(N); for (int i = 0; i > vec[i]; } sort(vec..

https://www.acmicpc.net/problem/9653똑같이 출력하는 브론즈5 문제이다.  빨리 풀기    출력문 비교하기https://www.diffchecker.com/pdOMgc5X/

목차 Data(Base) 분산데이터를 한 곳에 저장한다면 관리에 용이하다. 다만, 데이터가 늘어갈수록 용량 및 성능에 지장이 생긴다.다음은 이를 막기 위한 DB 분산 전략이다. 복제(Replication) : 전체 데이터베이스 또는 그 하위 집합을 여러 서버에 복사하여 각 서버가 읽기 요청을 독립적으로 처리할 수 있도록 분산. 한 서버의 데이터에 대한 모든 변경 사항은 다른 서버로 전파하여 처리한다.페더레이션(Federation) : 사용자 기반의 서로 다른 부분을 제공하는 여러 개의 작은 데이터베이스로 구성된 데이터베이스 생성파티셔닝(Partitioning), 샤딩(Sharding) : 데이터베이스를 작은 부분으로 나누어 분산 저장하는 방식 현대에서는 3번 방식을 주로 사용한다. 시스템의 특성에 따라 ..

BOJ Link https://www.acmicpc.net/problem/12851  풀이 과정N에서 N-1, N+1, N*2 각각의 경우를 탐색하여, K에 도달하는 최소 depth와, 경우의 수를 출력하는 완탐 + 그래프 탐색 문제이다.  방문 체크 배열에 depth를 기록한다. 탐색 순서에 따라 똑같은 값에 도달하더라도, depth가 더 작은 경우가 있을 수 있다. 이를 체크하기 위함이다. (또한 N+1 => N-1 => N+1 => N-1 무한 루프를 막는다.) 똑같은 값에 도달할 때, depth가 같더라도 탐색한다. 정답에서 최소 depth와 함께 "경우의 수"도 요구하기 때문이다. depth만 요구한다면, 방문 체크 배열보다 depth가 작을때만 탐색해도 된다. 굳이 최적화 하자면, 같은 값이고..

BOJ Link https://www.acmicpc.net/problem/1495  풀이 과정0이상 M이하의 범위를 지키면서,처음 값 S에서 V[0]...V[N-1]을 가감하며 탐색할 수 있는 지 찾는 문제이다. 할 수 있는 경우가 여러개라면 최대값을 출력한다. 현재 dp[i][j]를 P비용으로 연주하려면, dp[i-1][j-P]나 dp[i-1][j+p]가 true면 된다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { public static void ..

목차 개요일반적인 개발 방식에서는 요구사항 분석 -> 설계 -> 개발 -> 테스트 -> 배포의 개발 주기를 갖는다. 이 방식의 단점은 다음과 같다. - 소비자의 요구사항은 명확하지 않거나 변경될 수 있다.- 이에 따라, 설계 또한 변경된다. 이를 배제해도 애초에 완벽한 설계란 어렵다.- 이에 따라, 구현 또한 변경된다. 수정 과정에서 소스코드 품질이 저하될 수 있다.- 단위 유닛의 테스트를 위해 연관한 모든 부분을 테스트해야 한다. 테스트 비용 증가 외에도 전반적인 버그 검출이 어려워진다. 이를 보완하기 위한 방법중 하나로, TDD가 있다. 테스트 주도 개발 (TDD, Test Driven Development)테스트 작성 이후, 이를 통과하는 소스 코드를 작성하는 프로세스를 짧은 주기로 반복하는 개발 ..

BOJ Link https://www.acmicpc.net/problem/1991  풀이 과정BST의 순회법 3가지를 구현하는 문제다. left, right가 자식노드의 레퍼런스를 가리키는 일반적인 방법에서 조금 바꿔서 인덱스 기반으로 풀었다. 입력이 노드의 순서대로 주어지지 않기 때문에 이점만 유의하면 된다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { static Node[] tree; static StringBuilder sb = new St..

BOJ Link https://www.acmicpc.net/problem/1497  풀이 과정일반적인 부분집합 + 브루트포스로 풀 수 있다. 문제에서 N  또한, 다음과 같은 최적화를 할 수 있다. 입력 범위가 작아서 나는 쓰지 않았다. 1. A기타가 B기타가 칠 수 있는 곡을 모두 포함한다면 (B가 A의 부분집합이면), B기타를 탐색에 고려할 필요가 없다. 2. 백트래킹비트마스킹을 쓸 때, 탐색 중인 기타와 OR 연산을 해도 bitCount(= 연주할 수 있는 곡 수) 가 같다면 제외한다. (1번과 같은 논리이다. 현재까지 탐색한 기타들이 A가 되고, 탐색 중인 기타가 B가 된다.) (마찬가지로, 현재까지 어떤 기타들을 포함했는지 기록하지 않아도 된다. 어차피 B(부분집합)가 되면서 알아서 제외한다.)..

BOJ Link https://www.acmicpc.net/problem/17471  풀이 과정dfs/bfs 두번 + 조합 문제이다.  문제에선 요구하진 않지만, 비트마스킹으로 풀이했다. N  1. A선거구에 포함될 구역을 조합으로 뽑는다. -> bit의 dep번째 자리에 0 또는 1을 쌓아가며 뽑는다.pick(bit, dep + 1);pick(bit | (1  2. A선거구에 포함되지 않은 B선거구 구역을 XOR 연산으로 뽑는다.int a = bfs(bit);int b = bfs(compbit ^ bit); 여기서 combit는 왼쪽 기준으로 2~N+1번째 자리가 모두 1인 비트이다.(1번째 비트는 padding 을 위해 비웠는데 더 불편했다..)for (int i = 1; i  3. 비트 마스킹한 변..

BOJ Linkhttps://www.acmicpc.net/problem/17136 개요처음에 depth가 엄청 깊어질 거라 생각해서 그리디하게 풀 수 있나 생각했다. 반례로 안된다고 확정지었다.완탐으로 구현했는데, 역시나  1의 개수가 많아질수록 복잡도가 팩토리얼 단위로 늘어나므로 IDE에서도 오래걸렸다.(정확한 시간 복잡도 계산은 까다로웠다.)풀이 과정이중 for문을 사용해 탐색하며 3가지 최적화를 했다. (그럼에도 통과하지 못했다.) 1. 매 dfs 탐색 마다 map이 전부 0인지 세기 -> 붙이기/떼기 동작에서 같이 세기map이 10*10이라 그냥 매 탐색마다 셌었는데 바꿨다. 2. size 1 to 5탐색 -> size 5 to 1로 바꾸기가지치기에 현재 cnt가 ans 이상이면 return하는 ..