Doby's Lab

이번 문제는 처음으로 겪어보는 복합형(?) 문제였다. 여러 고난이 있었는데 고난을 겪었던 코드들을 읽어보면서 어떻게 정답에 도달했는지 알아보자. 논리를 어떻게 접근할까 (첫 번째 고난) 스타트팀 링크팀을 각각 나눠서 능력치를 더하고 비교해서 최솟값을 어떻게 구할지 논리에서 막혔었다. 1시간 정도 고민하다가 문제들을 분할시켜보았다. 1. 스타트 팀, 링크 팀 나누기 2. 각 팀 능력치 더하기 3. 각 팀 능력치의 차 값 구하기 4. 차 값의 최솟값 구하기 4개 정도로 분할시켜 하나씩 진행할 수 있었다. #include #include #include using namespace std; int n; bool visited[2001] = { 0, }; bool visited2[1001] = { 0, }; v..

이번 문제는 꽤나 건들기 싫었던 문제였다. 빡구현의 기미가 풀기 전부터 계속 느껴졌었다. 그래도 CLASS 2가 3문제 남은 시점에서 빨리 졸업하자라는 생각으로 문제에 임했다. 개념 이번 문제는 브루트 포스(Brute-Force) 알고리즘을 사용했다. 브루트 포스란 완전 탐색의 의미를 가지고 '모든 경우의 수를 다 확인해보자'라는 뜻이다. 'for문을 몇 개를 쓰거나 복잡해지든 말든 일단 모든 경우를 다 탐색해보자' 같은 주관적 느낌도 생겼다. 그렇다고 해서 브루트 포스가 무식한(?) 느낌의 알고리즘은 아니다. 오히려 컴퓨터의 장점(단시간 안에 수억 개의 연산을 처리한다는 점)을 잘 살리는 알고리즘이다. (책에서 그랬다..ㅎ) 고생했던 포인트 1. 8x8 사이즈의 체스판을 선언해둬야 했었다. 처음에는 문..

(추가 내용 2021.11.15) https://draw-code-boy.tistory.com/96 [알고리즘] 백준 6443번: 애너그램 (C++), 백트래킹 중복 처리 유형 2번째! https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램 draw-code-boy.tistory.com 비슷한 문제가 나와서 정리해두었다. 백트래킹의 코드 구조를 익히면서 [N과 M 시리즈]를 풀고 있었다. 이번 문제에서 막히게 되었는데 해당 문제에서 이런 걸 요구했기 때문이다. 'N이 4이고, M이 2일 때, 9 7 9 1의 수들로 부분 수..

(N과 M (1) 문제를 중심으로 설명하려 했으나 Backtracking과 DFS의 차이를 설명하기 위해 N과 M (2) 문제가 적합하다는 생각이 들었다.) 개념 백트래킹은 DFS를 응용하여 나온 알고리즘 같았다. DFS에 대해서는 그래프 이론에 대한 문제를 풀기 시작할 때 제대로 다시 다루겠지만 간단히 정리하면 어떠한 그래프가 주어졌을 때, 시작 노드로부터 연결돼있는 모든 노드를 탐색해나가는 완전 탐색 알고리즘이다. 또한 노드끼리 연결되었는가도 따져보아야 하는데 다음에 다시 다루겠다. 이러한 그래프가 있다고 가정하자. 시작 노드가 1일 때, DFS는 모든 노드들을 다음과 같이 탐색해나간다. 백트래킹은 DFS에 어떠한 조건을 주어서 (조건이라고 해서 무조건 if문을 사용하지 않는다.) 원하는 부분만 탐색..

이 문제를 보았을 때, 너무 쉬운 문제인데 CLASS 2에 왜 있을까라는 생각을 했다. 어떤 수 N이 있다고 가정하자. 'N이 카드 패에 있는지 없는지는 그냥 for문 돌려서 확인하면 끝나는 거 아닐까?'라고 생각할 수 있었다. 하지만, 문제에서의 N과 M의 주어진 범위를 보고, 시간제한을 보면 떠올랐던 생각으로 풀었을 때 '시간 초과'라는 오류를 초래할 수 있다. 왜냐하면 N의 범위가 1~500,000 M의 범위가 1~500,000이면 for문을 돌렸을 때 시간 복잡도가 O(N*M) 일 것이고, 최댓값이 250,000,000,000 즉, 2500억을 넘어가기 때문이다. 시간제한은 1초로 약 1억번 안에 끝내라는 암묵적인 조건을 주기 때문에 for문으로는 처리할 수가 없었다. 해결법 어떠한 배열 안에 특..