본문 바로가기

전체 글129

[ 프로그래머스 / DFS ] 타겟 넘버 1. 문제 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 2. 소스코드 - 매우 간단한 DFS문제 소스코드 #include #include using namespace std; int ans, t; vectorcopy_numbers; void dfs(int sum, int depth){ if(depth >= copy_numbers.size()) { if(sum == t) ans++; return; } dfs(sum + copy_numbers[depth] .. 2020. 6. 30.
[ 프로그래머스 / 투포인트 ] 숫자의 표현 1. 문제 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 2. 소스코드 소스코드 #include #include using namespace std; int solution(int n) { int answer = 0, start = 1, end = 1, sum = start; while (!(start > n or end > n)) { if (sum == n) { answer++; sum -= start++; } else if (sum < n) { sum += ++end; } else i.. 2020. 6. 30.
[ 프로그래머스 / DP ] 땅따먹기 1. 문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 2. 소스코드 - 이 문제는 그리디로 풀면, 당연히 최적해를 보장하지 않는다. - 완전 탐색을 하자니, 열은 4개지만, 행의 개수가 10만이다. 완전 탐색도 불가. - 그래서 DP 구나 싶었다. - [x][y]까지의 최대값은 [x][y] + [x-1]행에서의 최대값 이다. (단, 열은 달라야한다) 소스코드 #include #include using namespace std; int dp[100001][4]; int solutio.. 2020. 6. 30.
[ 프로그래머스 / BFS ] 카카오 프렌즈 컬러링 북 1. 문제 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 2. 소스코드 - 대놓고 BFS 쓰라는 문제라서 무난했다. - 전역변수로 선언해도 초기화를 해주지 않으면 에러가 났다. 전역변수 기본 초기화가 안 먹는 문제인듯. 1) 배열 전체를 돌면서, 0이 아니고, 방문 하지 않은 위치를 BFS한다. 발견 시, 새로운 구역이므로 구역 수++ 2) 해당 영역을 모두 탐색하고 area 넓이를 반환한다. 3) 정답과 비교 후 최대 크기인 경우, 갱신한다. 4) 1으로 돌아가 반복한다. 소스코드 #include #incl.. 2020. 6. 30.

티스토리툴바