GW LABS

백준 1755번 숫자놀이는 요건에 따라 Map을 정렬하면 쉽게 풀 수 있는 문제였다. C++의 경우 맵을 정렬하는 API가 없기 때문에 Vector 타입으로 변경하여 해결해야 한다. 아래는 풀이 소스이다. 정렬 함수는 C++의 람다 함수를 통해서 구현했다. #include #include #include #include using namespace std; map numberMap = { {0, "zero"}, {1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}, {6, "six"}, {7, "seven"}, {8, "eight"}, {9, "nine"} }; int main() { int m, n; cin >> m >> n; map conta..

오랜만에 백준 구현문제를 풀어보았다. 단순한 구현문제로 반복문을 활용하는 문제이다. 코드를 줄이는 연습을 계속해서 진행해야겠다. 반복문 안에 들어가는 변수들은 미리 선언해서 반복문의 중복을 피하도록 해야한다. #include #include using namespace std; char phase[100][100]; int main() { int size; cin >> size; for (int i = 0; i > phase[i][k]; } } int cmd; cin >> cmd; switch (cmd) { case 2: for (int i = 0; i < size; ++i) { for (int k = 0; k..

백준 8974번 희주의 수학시험은 주어진 규칙에 따라 수열을 만들고 더하는 연산을 수행하면 되는 문제이다. 입력범위가 적기 때문에 부르트포스 방식으로 풀이했는데, 수열의 일반항을 구해서 O(1) 가능할지도 검토해봐야겠다. 아래는 풀이이다. #include using namespace std; int container[1001]; int main() { int start, end; cin >> start >> end; int index = 1; int number = 1, accumulator = 1; while (index

C++로 그래프 탐색에 대한 문제를 연습한 적이 많지 않다. 파이썬으로 풀때와 차이점은 BFS 문제에 그래프 깊이 정보를 pair 형식으로 queue에 넣어도 메모리 초과 문제가 발생하지 않는 것 같다(오....). 1389번 케빈 베이컨의 6단계 법칙은 양방향 인접리스트를 입력받아 그래프 노드간 거리를 구하고, 그 합계가 최소인 지점을 찾는 문제이다. DFS로 풀이하려고 했는데 문제 분류에 BFS가 되어 있어 BFS로 풀이했다. #include #include #include #include #include using namespace std; bool visited[201] = {false}; int getLinkScore(int user, int target, map link) { int score..

정렬을 이용한 문제이다. 좌표들을 정렬하고 나서 원래 갖고 있던 인덱스를 통해 조건에 맞는 값을 출력하면 되는 문제였는데 set을 이용해서 자동으로 입력값들을 정렬하는 방식으로 접근했다. 다른 풀이법으로는 이진탐색을 이용해서 풀이하는 방법이 있었다. #include #include #include #include #include #include using namespace std; int main() { int count; cin >> count; set cord_set; int* cords = new int[count]; for (int idx = 0; idx < count; ++idx) { int tmp; scanf("%d", &tmp); cords[idx] = tmp; cord_set.insert(..

C++로 문제푸는 연습을 다시하면서 복습을 할만한 문제였다. 소수 판별의 경우 에라토스테네스의 채를 사용할 수도 있지만 판별하려는 숫자의 제곱근만큼만 탐색하면서 소수를 찾아도 충분히 풀 수 있는 문제였다. 팰린드롬 판별의 경우에는 문자열로 변환하여 손쉽게 판별할 수 있었다. 아래는 풀이이다. #include #include #include using namespace std; bool isPrime(const int& number) { if (number == 1) { return false; } if (number == 2) { return true; } bool answer = true; int limit = static_cast(sqrt(number)); for (int idx = 2; idx > ..

문제를 처음 읽었을 때 어떻게 하면 코드를 줄이면서 구현할 수 있을지 생각해봤다. 회의실 배정 문제같은 그리디 문제에서도 범위와 관련한 문제가 있었는데 이 문제에서는 겹치는 범위를 처리해야 했던 문제였다. 겹치는 범위를 처리하기 위해서 단순히 범위를 표현하는 배열을 만들어두고 그 배열에 겹치는 범위를 표시했다. 아래는 해당 소스코드이다. one, two, three = list(map(int, input().split(" "))) fee_table = [0 for _ in range(100)] for _ in range(3): start, end = list(map(int, input().split(" "))) for idx in range(start-1, end-1): fee_table[idx] += ..

백준 1021번 회전하는 큐 문제는 큐를 이용해서 큐를 회전시키면서 주어진 숫자들을 뽑아내는데 최소 회전 회수를 구하는 문제이다. 쉬운 문제였는데 많은 시간을 소비해 버렸다. 문제 풀이에 있어서 컨디션도 영향을 미치는 것 같다. 또한 알고리즘 문제 풀이에 있어서는 최대한 문제 자체에 집중하기 위해서 필요한 코드만 작정하는 습관을 들여야겠다. 의사코드를 먼저 작성하면 항상 도움이 된다. from collections import deque q_size, pop_count = list(map(int, input().split(" "))) pop_target = list(map(int, input().split(" "))) q = deque([i for i in range(1, q_size+1)]) answe..