인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 출력예제 1 6 풀이 - v(정점)==n이 될때 종료지점, 이 때가 1에서 n까지 도착한 것이기 때문에 cnt를 증가 - v==n이 아닐때는 각 정점에서 갈 수 있는 정점을 찾는다 - 아직 가지 않았고, 간선이 연결되있는 정점을 찾는다 => ch[i]==0 && map[v][i] ==1 - ch[i]에 1을 넣고 DFS(i) => 끝난 후에는 ch[i]를 0으로 초기화한다 #include #include using namespace std; in..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 6 9 1 2 7 1 3 4 2 1 2 2 3 5 2 5 5 3 4 5 4 2 2 4 5 5 6 4 5 출력예제 1 0 7 4 0 0 0 2 0 5 0 5 0 0 0 0 5 0 0 0 2 0 0 5 0 0 0 0 0 0 0 0 0 0 5 0 0 풀이 - 이차원 배열을 선언 - 간선 개수만큼 for문을 돌면서 a / b / c에 입력을 받음 ([a][b]에 c만큼의 비용) - map[a][b]에 c를 넣어주면 된다 - 무방향 그래프일 때는 map[1][2]=1이면 map[2][1]=1이기에 map[b][a]=1;을 추..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 8 7 6 3 1 5 2 4 8 출력예제 1 1 2 3 4 5 6 7 8 풀이 - 왼쪽 끝과 오른쪽 끝을 lt, rt로, 그 둘을 절반한 것을 mid로 놓는다 - lt~mid까지 한 묶음 / mid+1~rt까지 한 묶음이 된다 - data[p1]과 data[p2]를 비교해서 작은 값을 tmp[p3]에 넣는다 - 이 작업을 모두 수행하면 왼쪽 묶음이든 오른쪽 묶음이든 한쪽은 tmp에 모두 들어간다 - 남은 한쪽을 넣어주기 위해 while문을 사용한다 - 모든 작업을 마친후 tmp에 있는 모든 값을 data에 옮겨 준다..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 3 1 3 5 5 2 3 6 7 9 출력예제 1 1 2 3 3 5 6 7 9 풀이 - 세 개의 배열이 존재 (a / b / c배열) - c배열에 a,b 두 배열을 합친다 - 세 배열에 대한 포인터가 존재(p1, p2, p3) - a[p1], b[p2]의 값을 비교해서 작은 쪽을 c[p3]에 넣어줌 - 값을 c에 넣으면 p1 또는 p2의 값이 증가, p3값도 증가 - 두 배열의 길이가 다르기 때문에 남은 쪽이 존재 => while문을 통해 남은 애들까지 c배열에 넣어줌 #include #include using nam..

문제 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 풀이 - 앞에 풀었던 문제들과 비슷한 느낌으로 경우를 나눠서 돌리면 된다. - 여기서는 사용안함의 개념이 없기 때문에 -와 +만 생각한다. - solution 함수에 ..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 4 12 2 4 6 8 출력예제 1 4 풀이 - 2, 4, 6, 8로 +, -, 사용X 의 경우로 나누어서 12를 만든다. - 세 경우에 따라 DFS(L+1, sum+a[L]) / DFS(L+1, sum-a[L]), DFS(L+1, sum)이 된다. - count값을 0으로 두고 count값이 변하지 않으면 해당 수를 만들 수 없기 때문에 -1을 출력한다. - 경우의 수를 추적해보고 싶으면 path배열을 두고 DFS함수 시작 전에 경우에 따라 path[L]에 a[L], -a[L], 0을 넣어 준다. - sum이 원하..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 6 출력예제 1 1 3 5 6 7 10 풀이 - 하나의 DFS함수에는 (L+1, sum+a[L])으로 배열이 값을 더하고, 다른 하나는 (L+1, sum)으로 더하지 않고 간다 - L==n+1이 됬을 때 sum과 total-sum이 같으면 두 부분집합의 합이 같은 것이기 때문에 flag = true로 한다 - sum이 total/2보다 크다면 두 부분집합의 합이 같을 수 없으므로 return 시킨다 #include #include using namespace std; int n, a[11], total; bool f..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 11 출력예제 1 1 2 3 1 2 1 3 1 2 3 2 3 풀이 - check배열 사용해 트리 왼쪽으로 가면 1, 오른쪽으로 가면 0을 넣어줌 - L=n+1이면 해당 부분집합을 출력함 #include #include #include using namespace std; int n, ch[11]; //59. 부분집합(DFS 완전탐색) void DFS(int L){ if(L==n+1){ //종료지점 int i; for(i=1;i

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 11 출력예제 1 1011 풀이 - 재귀함수는 무조건 탈출 조건이 있어야함 if(){ return }else{ }형태로 틀을 잡음 - 아래 표를 스택으로 생각하면 계속 나누어서 recur(0)까지 간 뒤 나머지를 출력해주면 된다 recur(0) => return recur(1) printf(1%2) => 1 recur(2) printf(2%2) => 0 recur(5) printf(5%2) => 1 recur(11) printf(11%2) => 1 #include #include #include #include us..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 3 출력예제 1 1 2 3 풀이 - 재귀함수로 1,2,3 출력 - 재귀함수 위치에 따라서 출력 순서가 달라진다. recur(1) (매개변수, 복귀주소, 지역변수) recur(2) (매개변수, 복귀주소, 지역변수) recur(3) (매개변수, 복귀주소, 지역변수) main (매개변수, 복귀주소, 지역변수) - 이 순서대로 쌓여서 실행되어 1, 2, 3 출력이 가능하다. #include #include #include #include using namespace std; //56. 스택활용 재귀 void recur(in..