인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 8 1 2 12 1 3 6 1 4 10 2 3 2 2 5 2 3 4 3 4 2 2 4 5 5 출력예제 1 13 풀이 - 일단 DFS로 탐색을 하려면 경로가 들어있는 map배열과 방문했는지 확인할 수 있는 ch 배열이 필요함 - 여기서는 정점(a)-정점(b) 관계와 비용 c를 map[a][b]=c로 표시한다 - 최소비용을 알기 위해서는 전역변수인 cost를 탐색하면서 작은 값이 나올때마다 바꾸어주어야 한다 - DFS(1, 0)부터 시작하는데 시작정점 1에서 sum=0인 상태로 탐색한다 - 정점이 1~n까지 있기 때..

인프런 - 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 풀이 - 기존 문제에서 행렬이 아닌 벡터를 사용 - map[1].push_back(2) => 1번 인덱스에 2라는 노드가 생겨서 서로 연결 됨 - map[1].size()는 map[1]에 연결되어있는 노드의 수를 나타냄 - map[v][i] ex) map[1][2]이면 map[1]에 연결되어 있는 2라는 정점의 값이 됨 - ch[map[v][i]]가 0이면 해당 ch값을 1로 바꾼 후 DFS호출 => 호출 후 ch를 다시 1로 변..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 0000000 0111110 0001000 1101011 1100001 1101100 1000000 출력예제 1 8 풀이 - 앞서 푼 64번 문제의 격자 형태 변형 문제 - 격자 탐색(상, 하, 좌, 우 탐색) 시 dx, dy 배열을 이용함 - 새로 탐색할 좌표 xx = n+dx[i] , yy= m+dy[i] 이때 상하좌우 4번 탐색하기 때문에 for문은 0~4까지 돌면 된다 - 상하좌우 탐색 시 좌표가 1보다 작아지거나 7보다 커지면 안되기 때문에 continue로 아무 처리 없이 지나가게 한다 - 새로운 좌표인 ..

인프런 - 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..