본문 바로가기
728x90

bruteforce

[백준알고리즘] 18111번: 마인크래프트 -C++ [백준알고리즘] 18111번: 마인크래프트 -C++ 18111번: 마인크래프트 (acmicpc.net) 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 실버 문제 치고는 정답률이 낮다. 문제를 풀면서 그럴만하다고 느낀 게 실수하기 쉬운 부분이 있다. 다만 어려워서 그런 것은 아니기 때문에 반례도 생각하면서 풀어보면 좋을 문제다. 나는 생각한 반례도 다 돌아는 갔는데.. 통과를 못해서 반례 모음이 올라온 것을 보고 잘못된 부분을 찾을 수 있었다. 그리고 최대한 함수를 작게 나눠서 작성하고 있는데, 확실히 오류 .. 더보기
[백준알고리즘] 1057번: 토너먼트 -C++ [백준알고리즘] 1057번: 토너먼트 -C++ 1057번: 토너먼트 (acmicpc.net) 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 김지민과 임현수가 만나는 라운드를 출력하는 문제다. 이 문제는 수학적으로 쉽기도 하고, 직접 구해도 풀 수 있는 문제다. 나는 여기서 직접 만나는 경우를 구했다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 먼저, 앞서 수학적으로도 구할 수 있고, 직접 일일이 구할 수도 있다고 했다. 수학적으로 구할 수 있는 방법은 다음과 같다. 현재 라운드에서 참가자의 번호가 \( N.. 더보기
[백준알고리즘] 15683번: 감시 -C++ [백준알고리즘] 15683번: 감시 -C++ 15683번: 감시 (acmicpc.net) 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 예전에 파이썬으로 풀다가 무슨 일 때문인지 하다가 포기했던 문제다. C++로 새롭게 푸는데 생각보다 쉽게 풀려서 당황스럽다. 시간제한은 1초이지만 메모리 제한은 큰 문제다. 시간제한 때문에 고민을 좀 했다. 하지만 한 가지 조건 덕분에 완전 탐색(브루트포스) 방식으로 문제를 해결할 수 있었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제를 풀 수 있는 .. 더보기
[백준알고리즘] 14500번: 테트로미노 -C++ [백준알고리즘] 14500번: 테트로미노 -C++ 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 다 풀고 나니 DFS니 BFS니 뭐 다양하게 풀 수 있는 경우가 있는 것 같다. 근데 그런 것들은 어떻게 하라는 건지 이해를 잘 못하는 바람에 다른 풀이를 직접 해보지는 못했다. 예전에 파이썬으로 풀었던 문제인데, 포스팅은 하지 않았다. 풀고나서 파이썬 코드를 보니까 뭔 코드인지 전혀 못 알아먹겠어서 같이 첨부하지도 못할 것 같다. ㅋㅋㅋㅋ 이래서 네이밍이 중요하고.. 더보기
[백준알고리즘] 1759번: 암호 만들기 -C++ [백준알고리즘] 1759번: 암호 만들기 -C++ 1759번: 암호 만들기 (acmicpc.net) 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 예전에 파이썬으로 풀었던 문제다. 하지만, 역시나 기억이 나지 않았다. ㅋㅋ.. 다 풀고 글을 쓰려고 예전 글을 보니까 역시 파이썬 코드는 간단하다. 오늘 짠 C++ 코드도 더 간단히 가능하겠지만, 요즘 복잡하면서 간단한 것보다는 길더라도 깔끔한 코드를 지향하고 있어서 뭐 만족한다. 예전에 파이썬으로 풀었던 포스팅은 아래의 링크를 통해 가면 있다. [백준알고리즘] 17.. 더보기
[백준알고리즘] 10974번: 모든 순열 -C++ [백준알고리즘] 10974번: 모든 순열 -C++ 10974번: 모든 순열 (acmicpc.net) 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 가능한 순열을 오름차순으로 출력하는 문제다. 처음에는 순열을 만드는 STL 라이브러리를 사용하지 않고 문제를 풀었고, 이후 해당 기능의 라이브러리가 있을 것 같아 찾아서 적용해봤다. 두 경우 모두 통과했고, 아래에 순서대로 작성해놨다. 간단한 문제라서 길진 않다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 1. 직접 구현 직접 순열을 만들고 출력하는 함수를 만들어주었다. DFS로 동작하면서 브루트포스(완전 탐색)를 시도해서 문제를 풀었다. 길이가.. 더보기
[백준알고리즘] 2210번: 숫자판 점프 -C++ [백준알고리즘] 2210번: 숫자판 점프 -C++ 2210번: 숫자판 점프 (acmicpc.net) 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 메모이제이션을 사용할까 하다가 숫자판도 작고, 만들어낼 숫자의 길이도 6자리로 길지 않았기 때문에 계산을 해보다가 메모이제이션 없이 완전 탐색을 시도했다. 대강 계산했을 때 각 위치에서 4방향으로 이동할 수 있기 때문에 메모이제이션 없이 각 시작 위치에서 \(4^5\)개의 위치로 이동할 수 있다. 즉, \(5 \times.. 더보기
[백준알고리즘] 1038번: 감소하는 수 -C++ [백준알고리즘] 1038번: 감소하는 수 -C++ 1038번: 감소하는 수 (acmicpc.net) 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쉬운 듯 안 쉬운 듯한 문제.. DFS로 푸시는 분들이 많으신 것 같고 풀이가 많으신 것 같지만, 나는 DP로 풀었다. DP로 푸는 방법 중에서도 벡터를 두개만 사용해서 문제를 풀었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 처음 문제를 접했을 때에는 숫자를 1씩 증가시키면서.. 그러면서 각각의 수가 감소하는 수인지 확인하는 방법으로 코.. 더보기
728x90

티스토리툴바