전체 글50 [프로그래머스] 정수 삼각형 - JAVA https://programmers.co.kr/learn/courses/30/lessons/43105?language=java#_=_ 문제 해석 정수 삼각형 최상단에서 왼쪽 또는 오른쪽으로 내려가면서 값을 더해갈때 가장 최댓값은? 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 문제 풀이 모든 경우의 수를 해본다면? O(2^n) 내려가면서 왼쪽 또는 오른쪽 숫자를 사용했을때 최댓값만 남긴다 O(n^2) 최대값을 구할때 sorting을 사용해도 된다 Arrays.sort(arr); //내림차순 Integer []arr = {1, 2, 0}; Arrays.sort(arr, Collections.reverseOrder()); class .. 2021. 4. 3. [백준]1로 만들기 - 복습 https://www.acmicpc.net/problem/1463 각 단계별 3가지 경우의 수가 있으니 10^6 숫자를 전역탐색하기에는 시간이 부족하다 1을 만드는게 목적이니 1에서부터 3가지 방법을 사용하면서 값을 만들면서 최소 횟수만 남겨서 기록한다 #include #include #include using namespace std; int N; int cache[1000001]; void solve(int x) { if (x > N) return; int& ret = cache[x]; ret = cache[x - 1] + 1; if (x % 2 == 0) ret = min(ret, cache[x / 2] + 1); if (x % 3 == 0) ret = min(ret, cache[x / 3] + 1.. 2021. 3. 31. [백준]그룹 단어 체커 - 백준 https://www.acmicpc.net/problem/1316 알파벳 체크배열 만들어두고 이미 채크된 알파뱃을 다시 사용하는지 확인 #include #include #include using namespace std; string input[101]; int alpha[26]; int main() { int N; cin >> N; for (int i = 0; i > input[i]; } int cnt = 0; for (int i = 0; i < N; i++) { memset(alpha, 0, sizeof(alpha)); int isGroup = true; for (int j = 0; j < input[i].length(); j++) { char c = input[i][j.. 2021. 3. 31. [백준]DFS와 BFS - 복습 https://www.acmicpc.net/problem/1260 #include #include using namespace std; int adj_matrix[1001][1001] = { 0, }; int check[1001] = { 0, }; int N, M, V; void dfs(int node) { cout x; int y; cin >> y; adj_matrix[x][y] = 1; adj_matrix[y][x] = 1; } dfs(V); cout 2021. 3. 31. [백준]부분수열의 합 - 복습 https://www.acmicpc.net/problem/1182 5개의 숫자중 1개 선택하는경우 + 2개 선택하는경우 + 3개 선택하는경우 ... 5C1 + 5C2.. 2^5 2^5까지의 값을 2진수로 생각해보면 각 자리수를 한번씩 토글한다 해당 자리수 토글을 해당 수열을 선택했다고 생각하자 #include #include using namespace std; int input[21]; int main() { int N, S; int cnt = 0; cin >> N >> S; for (int i = 0; i > input[i]; } for (int i = 1; i < pow(2, N); i++) { int sum = 0; for (int j = 0; j < N; j++) .. 2021. 3. 22. [백준]단어 정렬 - 복습 https://www.acmicpc.net/problem/1181 길이가 같은 경우 사전순으로 나열하기 위해 백터에 스트링과 가중치 저장 라이브러리 sort에서 비교함수를 만들어서 사용하는 방법 sort(vec.begin(), vec.end(), cmp_STR); 백터 사용 struct STR { string u; int weight; }; vector vec; vec.push_back(temp); #include #include #include #include using namespace std; struct STR { string u; int weight; }; vector vec; int calculateWeight(string u) { int weight = 0; for (int i = 0; i .. 2021. 3. 22. 이전 1 2 3 4 5 6 7 8 9 다음