본문 바로가기
728x90

Algorithm

[백준알고리즘] 9663번: N-Queen -C++ [백준알고리즘] 9663번: N-Queen -C++ 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제로 유명한 N-Queen 문제다. 유명한 문제인만큼 정답 비율은 53%가 넘음에도 불구하고 골드 5의 난이도를 갖고 있는 문제다. 그만큼 중요한 문제라고 말하는 것 같다. N-Queen 문제는 원래 8 Queen 문제로 유명하다. 문제의 요구조건은 동일하나 \( 8 \times 8 \) 크기의 체스판에 8개의 퀸을 놓는 문제다. 이거에 대한 접근법도 다양하게 있던.. 더보기
[백준알고리즘] 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.. 더보기
[백준알고리즘] 11729번: 하노이 탑 이동 순서 -C++ [백준알고리즘] 11729번: 하노이 탑 이동 순서 -C++ 11729번: 하노이 탑 이동 순서 (acmicpc.net) 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 유명한 재귀 문제이기도 한 하노이 탑 문제다. 예전에 파이썬으로 풀고 글을 업로드한 경험이 있는데, 아래에 링크를 두었다. 이때는 최소 이동 횟수를 계산했었다는 게 놀랍다. 과거의 나 대단하군. [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python (tistory.com) [백준알고리즘] 11729번: 하노이 탑 이동 .. 더보기
728x90

티스토리툴바