devrabbit22 님의 블로그

백준 - [단계별로 풀어보기 브루트 포스] 1018 체스판 다시 칠하기

이번 문제는 꽤 오랫동안 고민했던 문제였다. 결국 여러 코드와 해설을 찾아보며 참고했고, 이를 바탕으로 직접 구현해 보았다.브루트포스 방식으로 값을 하나씩 대입해 검사하는 접근 자체는 어렵지 않았다.하지만 8 × 8 범위의 체스판을 검사하면서 최소로 다시 칠해야 하는 칸의 수를 구하는 과정에서 범위를 어떻게 설정해야 할지 감을 잡지 못했다. 특히 전체 N × M 체스판에서 어떤 위치를 기준으로 8 × 8 영역을 검사해야 하는지에 대해 한동안 고민하게 되었다.using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace ConsoleApp3{ int..

백준 - [단계별로 풀어보기 브루트 포스] 19532 수학은 비대면강의입니다.

이번 문제는 연립방정식을 만족하는 x와 y의 값을 브루트포스 알고리즘을 이용해 찾는 문제이다. 먼저 a, b, c, d, e, f의 값을 입력받아 두 개의 연립방정식을 구성한다.이후 x와 y의 범위가 -999부터 999까지로 제한되어 있기 때문에 해당 범위의 모든 값을 하나씩 대입하여 두 식을 모두 만족하는 값을 찾으면 된다.using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace ConsoleApp3{ internal class BruteForce { static void Main(string[] args) {..

백준 - [단계별로 풀어보기 브루트 포스] 2231 분해합

이번 문제는 분해합으로 브루트포스 알고리즘에 관한 문제이다. 문제에서 말하는 분해합이란 어떤 수와 그 수의 각 자리수의 합을 더한 값을 의미한다. 예를 들어 어떤 수가 198이라면 분해합은 다음과 같이 계산된다.더보기198 + 1 + 9 + 8 = 216 이 경우 198은 216의 생성자가 된다. 문제에서는 입력으로 주어진 수 N에 대해 분해합이 N이 되는 가장 작은 생성자를 찾는 것이 목표이다.처음에는 입력된 값에서 자리수를 빼는 방식으로 생성자를 역으로 찾을 수 있을 것이라 생각했다.예를 들어 216이라는 값이 주어졌다면 다음과 같이 계산할 수 있을 것이라 생각했다.더보기216 - 2 - 1 - 6 하지만 이렇게 계산하는 방식은 항상 올바른 결과를 보장하지 않는다. 실제로 입력값을 기준으로 역으로 계..

백준 - [단계별로 풀어보기 브루트 포스] 2798 블랙잭

이번 문제의 단원은 모든 경우의 수를 확인하는 브루트포스 알고리즘에 관한 내용이다. 블랙잭 문제는 카드의 개수 N과 기준 값 M이 주어지고, 카드에 적힌 숫자들이 입력된다. 이 카드들 중 3장을 선택하여 카드의 합이 M을 초과하지 않으면서 가장 큰 값을 구하는 문제이다.이 문제는 가능한 모든 카드 조합을 확인해야 하기 때문에 브루트포스 방식으로 접근할 수 있다. 또한 같은 카드를 여러 번 선택하지 않도록 중복 선택을 방지하는 구조를 만드는 것이 중요하다. 따라서 i using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace ConsoleApp3{ ..

백준 - [단계별로 풀어보기 시간 복잡도] 24313 알고리즘 수업 - 점근적 표기 1

이번 문제를 풀면서 함수 f(n) = a1n + a0과 양의 정수 c, n0가 주어질 때 O(n) 정의를 만족하는지 확인하는 문제라는 것을 알고 수식을 살펴보며 코드를 작성했다.하지만 모든 n ≥ n0에 대하여 조건을 만족해야 한다는 중요한 조건을 놓치고 말았다. 수식 자체를 만족하는지만 확인하는 것에 집중하다 보니, 해당 조건을 코드에 반영하지 못했던 것이다.결과적으로 a1 * n0 + a0 ≤ c * n0 조건만 확인했고, a1 ≤ c 조건을 추가하지 않아 오답이 발생했다.아래는 당시 누락되었던 코드 부분이다.using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tas..

이번 문제는 처음에 구조가 잘 이해되지 않아 여러 풀이를 참고하게 되었다. 일부 풀이는 시그마 공식을 이용해 반복 횟수를 계산했고, 또 다른 풀이는 반복문의 구조를 분석해 조합 형태로 접근했다.나는 그중에서 조합을 이용해 실행 횟수를 구하는 방법을 참고하여 문제를 해결했다. 시그마 공식을 활용한 풀이 [백준/BOJ] 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 (C/C++)백준 온라인 저지(BOJ) 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 https://www.acmicpc.net/problem/24267 24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6 오늘도 서준이는 알고리즘의 수행시간 수업 조rightbellboy.tistory.com조합 형태를 활용한 풀이 백준..

이번 문제는 반복문이 세 번 사용된 알고리즘이다. 이전 문제인 24265처럼 반복문의 실행 횟수가 서로 다른 구조가 아니라, 세 개의 반복문이 모두 동일한 범위에서 반복된다.일반적으로 반복문이 하나 사용될 때마다 시간 복잡도는 n만큼 증가하게 된다. 따라서 반복문이 세 번 사용되었다면 실행 횟수는 n × n × n이 되고, 이는 n³ 형태가 된다. 여기서 알 수 있는 사실은 시간 복잡도는 O(n³)이며, 최고차항의 차수는 3이 된다. 추가로 이 문제를 풀면서 처음에는 Math.Pow를 사용해 n³을 계산했지만 틀렸다는 결과를 받게 되었다. 그 이유는 Math.Pow 연산의 반환 타입이 double이기 때문이다.백준에서는 정수 형태의 출력이 필요하기 때문에 실수형 값이 출력되면 오답이 된다. 따라서 Mat..

이번 문제는 기존의 시간 복잡도 문제와 달리 수학 공식을 활용하여 실행 횟수를 계산해야 하는 문제이다.알고리즘 구조를 보면 이중 반복문이 사용되지만, 두 반복문의 실행 횟수가 서로 다르다.for i = 1 to n-1 for j = i+1 to n예를 들어 n = 7일 때 i는 1부터 6까지 총 6번 반복된다. 그리고 j의 반복 횟수는 다음과 같이 줄어들게 된다.더보기i = 1 → j : 2 3 4 5 6 7 (6번) i = 2 → j : 3 4 5 6 7 (5번) i = 3 → j : 4 5 6 7 (4번) i = 4 → j : 5 6 7 (3번) i = 5 → j : 6 7 (2번) i = 6 → j : 7 (1번)따라서 j의 반복..

알고리즘 수업과 관련된 문제는 시간 복잡도에 대한 이해를 확인하는 문제이다. 주어진 알고리즘의 코드 구조에 따른 실행 횟수와 시간 복잡도를 파악하고, 해당 시간 복잡도 식의 최고차항 차수를 구할 수 있는지를 묻는 문제이다. 백준 - [단계별로 풀어보기 시간 복잡도] 24262 알고리즘 수업 - 알고리즘의 수행 시간 1이번 문제는 특정 기능을 구현하는 문제가 아니라, 알고리즘의 시간 복잡도를 이해하고 있는지 확인하는 문제이다.배열의 n/2 위치에 접근하여 값을 한 번 반환하는 연산으로, 반복문 없이 단 한devrabbit22.tistory.com이전에 작성한 내용을 보면 아래와 같은 내용이 있다. 코드 실행 횟수시간 복잡도반복문 없음1O(1)반복문 1개nO(n)이중 반복문n²O(n²)위의 표에서 알 수 있..

이번 문제는 이전 문제의 연장선이다.https://devrabbit22.tistory.com/211 백준 - [단계별로 풀어보기 시간 복잡도] 24262 알고리즘 수업 - 알고리즘의 수행 시간 1이번 문제는 특정 기능을 구현하는 문제가 아니라, 알고리즘의 시간 복잡도를 이해하고 있는지 확인하는 문제이다.배열의 n/2 위치에 접근하여 값을 한 번 반환하는 연산으로, 반복문 없이 단 한devrabbit22.tistory.com이전에 작성한 내용에서 실행 횟수와 시간 복잡도의 차수에 대해 간단하게 정리했다. 이를 바탕으로 이번 문제에 대입해보면, 입력의 크기 n을 입력받아 n만큼 반복문이 실행되는 구조이다.따라서 수행 횟수는 n이 되고 시간 복잡도는 O(n)이 된다. 또한 시간 복잡도 식이 n¹ 형태이므로 최..