본문 바로가기
반응형
SMALL

알고리즘 문제 풀이/Baekjoon

17141 - 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 삼성 SW 상시 역량 테스트의 기출 문제입니다. 조합과 BFS, 문제의 조건만 잘 처리한다면 풀 수 있는 문제입니다. N의 범위가 굉장히 작기 때문에 제가 5중 for 문을 사용했는데도 안전하게 통과가 됐습니다. 더 좋은 방법이 있다면 알려주세요. 또, 빠르게 풀려다보니 코드가 정리가 안되어있는데 주석으로 적어놓겠습니다. from itertools import combinations from collections im.. 더보기
11052 - 카드 구매하기 다이나믹 프로그래밍 문제입니다. 최댓값을 고르는 문제인데, 처음엔 가격 위주로 생각하기 보단, 그 카드의 갯 수를 어떻게 만드는지를 고민해봅시다. N개의 카드 뭉치를 만들 땐, 이전 뭉치에서 한 장을 더해서 N개를 만들거나, 두 장을 더해서 N개를 만들 수 있습니다. 그렇게 쭉 가다보면 N 장을 더해서 N개를 만들 수 있겠죠 즉, card[N] = card[N - 1] + card[1] / card[N - 2] + card[2] / card[N - 3] + card[3] ... / card[N- N] + card[N] 이런 식으로 되겠죠. 그렇다면 최댓값은 뭘까요? 그 이전의 최대 비용에서 카드를 더할 수 있는 경우의 수를 더하면 됩니다. 최대 비용과 그 이전의 카드에서 지금의 카드 장 수를 맞추기 위한.. 더보기
5622 - 다이얼 해싱으로 풀어봤는데, 너무 간단해서 해싱이라고 표현하기도 그렇네요. 어쨋든, 다이얼 중간마다 4개인 애들만 잘 처리하면 쉽게 풀 문제입니다. 근데, 저는 항상 문자열을 크게 받고 순회할 때 널 문자 체크를 안해서 답이 계속 오답으로 나왔는데, 여러분들은 그렇게 안 하셨으면 합니다. 까먹지마세요. #include int main(void) { char word[16]; scanf("%s", word); int arr[100]; int time = 3; int cnt = 0; for (int i = 65; i < 91; ++i) { if (i == 90) { arr[90] = time - 1; break; } else if (i == 'S') { arr[i] = time - 1; cnt = 0; contin.. 더보기
10809 - 알파벳 찾기 이 문제도 역시나 문자열 처리하는 문제입니다. 저는 해싱으로 문제를 풀어봤습니다. 전체적인 알파벳들의 처음 위치만 기록하면 되기 때문에 해싱으로 바로 접근하여서 O(n)을 노렸습니다. 배열 인덱스로 97을 뺏었는데 그렇게 하면 보기 안 좋으니 'a'로 해줘도 됩니다. 그리고 word의 '\0' 문자를 만났을 때 break를 안 걸면 쓰레기값을 참조하여서 틀린 답을 뱉어냅니다. 그러니 추가적인 조건으로 '\0' 문자를 만났을 땐 처리를 해줘야합니다. #include int main(void) { char word[101]; int arr[101]; for (int i = 0; i < 101; ++i) { arr[i] = -1; } scanf("%s", word); for (int i = 0; i < 101.. 더보기
11720 - 숫자의 합 (C) 문자열 연습을 위함입니다. 파이썬에선 간단하게 받은 문자열이 C에서는 조금 복잡한 절차가 필요합니다. #include int main(void) { int N; scanf("%d\n", &N); // \n문자를 넣어줘야 합니다. 안 그러면 밑에 있는 %c가 \n을 받아서 10을 출력합니다. char num; int result = 0; for (int i = 0; i < N; ++i) { scanf("%c", &num); result += num - 48; } printf("%d", result); } 더보기
미로 탐색 - 2178 (C++) #include #include using namespace std; deque dqi; deque dqj; deque cnt; int y, x; int y_[4] = { 0, 0, 1, -1 }; int x_[4] = { 1, -1, 0, 0 }; int n, m; int map[100][100]; int visited[100][100]; int result; int main(void) { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%1d", &map[i][j]); visited[i][j] = 1; } } dqi.push_back(0); dqj.push_back(0); visited[.. 더보기
팩토리얼 - 10872 (C) #include int main(void) { int num; int result = 1; scanf("%d", &num); for (int i = 1; i 더보기
단지번호붙이기 - 2667번 (Python) from collections import deque N = int(input()) mat = [] visited = [[1 for _ in range(N)] for __ in range(N)] dq = deque() dxdy = [(1, 0), (0, 1), (-1, 0), (0, -1)] result = [] for _ in range(N): strings = input() temp_mat = [] for string in strings: temp_mat.append(int(string)) mat.append(temp_mat) for i in range(N): for j in range(N): if mat[i][j] and visited[i][j]: dq.append((i, j)) visited[i].. 더보기
반응형
LIST

티스토리툴바