본문 바로가기
728x90

브루트포스

[백준알고리즘] 2589번: 보물섬 -C++ [백준알고리즘] 2589번: 보물섬 -C++ 2589번: 보물섬 (acmicpc.net) 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제를 봤을 때 브루트 포스인가? 단순히 최단거리는 못 구하는데? 일단 해보자! 했다. 예전에는 너무 최단거리 문제만 풀다가 브루트 포스 문제 여부를 감을 잡지 못했었는데, 지금 오히려 눈이 넓어졌나보다. 골드라고 해서 살짝 쫄았는데 정답 비율은 생각보다 높았다. 어쩐지 어렵진 않더라.. 문제 풀이 문제는 브루트 포스 방식을 사용하면 된다. 그리고 그래프 탐색을 사용하면 된다... 더보기
[백준알고리즘] 18111번: 마인크래프트 -C++ [백준알고리즘] 18111번: 마인크래프트 -C++ 18111번: 마인크래프트 (acmicpc.net) 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 실버 문제 치고는 정답률이 낮다. 문제를 풀면서 그럴만하다고 느낀 게 실수하기 쉬운 부분이 있다. 다만 어려워서 그런 것은 아니기 때문에 반례도 생각하면서 풀어보면 좋을 문제다. 나는 생각한 반례도 다 돌아는 갔는데.. 통과를 못해서 반례 모음이 올라온 것을 보고 잘못된 부분을 찾을 수 있었다. 그리고 최대한 함수를 작게 나눠서 작성하고 있는데, 확실히 오류 .. 더보기
[백준알고리즘] 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.. 더보기
[백준알고리즘] 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씩 증가시키면서.. 그러면서 각각의 수가 감소하는 수인지 확인하는 방법으로 코.. 더보기
[백준알고리즘] 1026번: 보물 -C++ [백준알고리즘] 1026번: 보물 -C++ 1026번: 보물 (acmicpc.net) 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 음 뭔가 브루트포스로 돌리면서 어려울 것 같았는데, 실상은 그렇지 않았다. 정답률이 보장하는 쉬운 문제였던 것 같다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제는 A 배열과 B 배열을 정렬해서 각 원소의 곱의 합이 최소가 되도록 만들면 된다. 문제에서는 B 배열의 순서를 이동시킬 수 없다고 해서 변수 명도 \(vecNonVariable\)로 잡기는 했지만,.. 더보기
728x90

티스토리툴바