Engineering Note

it 취업을위한알고리즘문제풀이 문제 합이 같은 부분집합(DFS : 아마존 인터뷰) N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. ▣ 입력설명 첫 번째 줄에 자연수 N(1

it 취업을 위한 알고리즘 문제풀이 문제 코드 //60. 합이 같은 부분집합(DFS : 아마존 인터뷰) #include #include int n; bool flag = 0; int num[10]; int subnum[10]; int sum1; int sum2; //부분집합 구하기 void dfs(int level) { if (flag == true) return; if (level == n) { //부분집합 누적합 구하기 sum1 = sum2 = 0; for (int i = 0; i < n; ++i) { if (subnum[i] == true) { sum1 += num[i]; } else { sum2 += num[i]; } } if (sum1 == sum2) { flag = 1; } return; } ..

it 취업을 위한 알고리즘 문제풀이 문제 코드 //59. 부분집합(MS인터뷰:DFS) #include #include int n, ch[11]; void dfs(int level) { if (level == n + 1) { for (int i = 1; i

it 취업을 위한 알고리즘 문제풀이 문제 코드1 코드2 문제해결방법1 입력 값이 작은 형태에서는 기준 시작 위치부터 주어진 구간의 모든 영역을 하나씩 더하는 방법으로 4중 for문으로 구할 수도 있지만 입력값이 커지면 시간 복잡도가 너무 복잡해진다. 이를 해결하기 위해서 입력받으면서 일단 누적합저장할 변수를 새로 만들고 누적합을 구한다. 이때 누적합의 규칙은 i*j 사각형의 격자 까지의 넓이를 구한다. 구하는 방법은 다음과 같다. (3,4)까지의 누적합은 "(2,4)까지의 누적합 + (3,3)까지의 누적합 - (2,2)까지의 누적합(중복된부분 제거를 위해 빼줌) + (3,4)현재 위치의 입력값 일반화를 위해서 쓰레기값이 저장된 메모리를 활용하지 않기 위해 2차원 배열의 모든 초기값을 0으로 해준다. (0..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 코드1 코드2 코드2

it 취업을 위한 알고리즘 문제풀이 문제 코드 문제해결방법 문제의 주어진 값 입력 받기 누적 값을 구할 시작 위치 좌측 끝 꽃지점 i,j에서 현수가 가져갈 넓이 가로만큼 우로 더해가고 다시 다음줄 부터 가로만큼 우로 더해가기 다음줄은 현수가 가져갈 세로만큼 까지만 진행 누적 값과 최대값 비교해서 최대값보다 현재 누적 값이 크다면 최대값 변수에 저장

it 취업을 위한 알고리즘 문제풀이 문제 코드2 문제해결방법 무슨 변수가 필요할지 먼저 생각하고 알고리즘 구현 최소차 값, 현재 인덱스 값에서 평균과 차 저장할 값(현재 차이), 최소차일 때 숫자변수, 합, 평균 2중 for문으로 2차원 배열의 각 행의 값을 입력 받으며 누적 합을 구함 각 행의 값을 모두 입력 받으면 열의 길이로 누적 합을 나누어서 평균을 구함 이때 소수점 첫 째 자리에서 반올림이므로 0.5를 더해 반올림 (정수/실수 => 실수, 실수/정수=>실수 ==>연산되는 자료형 중 넓은 범위의 자료형으로 결과 값이 나옴) 구한 평균과 각 행의 각각의 열들의 차이를 구해(이때 절대값 함수 사용) 가장 작은 값을 찾음 지금 까지 구한 차보다 작은 차가 구하면 최소차 변수에 저장 차 값이 같은 값이 ..

it 취업을 위한 알고리즘 문제풀이 문제 코드