dev study-log

이 문제는 필자가 좋아하는 문제 유형이다. 백트래킹을 연습하기 좋은 문제 같다. https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 해석: 이 문제는 만들 수 있는 모든 암호를 출력해주는 문제이다. 정수 L은 만들어야 하는 암호의 길이이고, 정수 C는 주어지는 알파벳의 수이다. 두 정수 모두 최대 크기는 15이다. 암호는 반드시 모음을 하나 이상 포함하고 자음을 두개 이상 포함해야 한다. 그 말인 즉, 모음을 하나 이상 포함하고 자음을 두개 이상 ..

이번 문제는 아주아주 쉽게 풀리는 문제였다. https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 참고로 필자는 문제를 풀기 전에 이 문제가 어떤 알고리즘 분류인지 힌트를 보지 않고 풀기 시작한다. 문제를 처음 봤을 때 어떤 알고리즘을 사용해야 하는지 판단하는 훈련도 같이 하기 위함이다. 문제를 푸는 기준은 그냥 solved.ac에 들어가서 티 어에서 많이 푼 순서대로 풀어나가고 있다. 잡설은 여기까지 하고 문제를 살펴보자. 문제해석: 문제에..

역시 학교 수업은 제대로 들어야겠다는 교훈을 얻은 알고리즘이다. 문제해결기법이라는 강의가 있었는데 그 강의 시간에 교수님께서 설명해주신 방법대로 풀면 바로 풀리는 쉬운 문제였다. 물론 처음에는 조금 돌긴 했지만 이내 금방 길을 찾을 수 있었다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 익히들 알고 있을 수도 있고 유명한 knapsack problem이다. 그런데..

이거는 예전에 풀었던 문제인데 어째서 업로드를 안했는지 의문이다. 그래서 지금 올린다 ㅎㅎㅎ 분명 게을러서 안올린건 아니었는데 왜 안올렸지.. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제해석: 이 문제를 처음 보면 아마 많은 분들이 자료형이 작다고 생각할 것이다. 또한 제한시간 또한 10초로 매우매우 넉넉한 편이 고 여기서 많은 분들이 브루트포스(Brute-Force)를 떠올렸을 것이다. 또한 제한시간이 10초로 주어진 이유는 그만큼 branch로 나..