본문 바로가기

📝 알고리즘

(143)

[C++/BOJ] 2149 : 암호 해독 문제 어떤 문장을 키를 이용하여 다음과 같이 암호화하려 한다. 암호화하기 전의 문장을 평문이라 하며, 암호화 된 문장은 암호문이라고 한다. 키, 평문, 암호문은 모두 영어 대문자로 된 공백 없는 문장이다. 키의 길이를 N이라고 했을 때, 우선 평문을 N 글자씩 잘라서 다음과 같이 나열한다. 예를 들어 평문이 MEETMEBYTHEOLDOAKTREENTH 이고, 키가 BATBOY라고 해 보자. 제일 윗줄은 이해를 돕기 위해 키를 다시 한 번 쓴 것이다. 이제 이 행렬(배열)을 열(Column) 단위로 정렬을 하는데, 정렬을 하는 키준은 키의 문자로 한다. 즉 BATBOY를 정렬하여 ABBOTY와 같이 정렬하는 것이다. B와 같이 여러 번 나타나는 문자의 경우에는 원래의 행렬에서 더 왼쪽에 있었던 것을 먼저 ..

[C++/BOJ] 2293 : 동전 1 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 백준 골드 5 문제! 백트래킹이나 완탐 문제일 줄 알았는데 알고보니 dp였다.... 0원인 경우의 수는 1이다. dp[0] = 1; 1원이 가능한 경우의 수는 1원..

[코드트리] BFS 탐색 / 갈 수 있는 곳들 갈 수 있는 곳들 숫자 0, 1로만 이루어진 n * n 격자가 주어졌을 때, k개의 시작점으로부터 상하좌우 인접한 곳으로만 이동하여 도달 가능한 칸의 수를 구하는 프로그램을 작성해보세요. 숫자 0은 해당 칸이 이동할 수 있는 곳임을, 숫자 1은 해당 칸이 이동할 수 없는 곳임을 의미합니다. 입력 형식 첫 번째 줄에는 격자의 크기를 나타내는 n과 시작점의 수를 나타내는 k 값이 공백을 사이에 두고 주어집니다. 두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 순서대로 공백을 사이에 두고 주어집니다. 그 다음 줄 부터는 k개의 줄에 걸쳐 각 시작점의 위치 (r, c)가 공백을 사이에 두고 주어집니다. (r, c)는 r행 c열 위치가 시작점 중 하나임을 의미합니다. 모든 시작점의 위치에 적..

[코드트리] BFS 탐색 / 네 방향 탈출 가능 여부 판별하기 네 방향 탈출 가능 여부 판별하기 n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 상하좌우에 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 과 같이 뱀이 배치 되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이 때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요. 입력 형식 첫번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두번째 줄부터 (n+1)번째 줄까지는 각 행에 뱀이 없는 경우 1, 뱀이 있는 경우 0이 입력으로 공백을 사이에 두고 주어집니다. 시작 칸과 끝 칸에는 뱀이 주어지지 않는다고 가정해도 좋습니다. 2 ≤ n..

[코드트리] 완전탐색 / 자리 수 단위로 완탐 연습문제 5개의 숫자 [1, 5, 2, 6, 8]이 주어졌을 때 이 중 단 하나의 숫자만 두 배로 해서, 인접한 숫자간의 차이의 합이 최대가 되도록 해보세요. 위 문제는 단순하게, 모든 위치의 숫자를 2배씩 해보는 완전탐색을 진행해 볼 수 있습니다. 1. 첫 번째 숫자 1에 2배를 하는 경우 [2, 5, 2, 6, 8]이 되므로, 인접한 숫자간의 차이의 합은 3 + 3 + 4 + 2 = 12가 됩니다. 2. 두 번째 숫자 5에 2배를 하는 경우 [1, 10, 2, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 9 + 8 + 4 + 2 = 23이 됩니다. 3. 세 번째 숫자 2에 2배를 하는 경우 [1, 5, 4, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 4 + 1 + 2 + 2 = 9가 됩..

[코드트리] Greedy - 그리디 알고리즘 / 동전 연습문제 1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 위 문제를 보면 당연히 큰 동전부터 쓰는 것이 좋아 보입니다. 하지만 큰 동전부터 사용하게 되면 5 + 1 + 1 + 1이므로 4개의 동전이 필요하지만, 4 + 4 역시 8 이므로 최소 동전의 수는 2가 됩니다. 그런데 다음 경우는 어떨까요? 1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 이 경우에는 큰 동전부터 거슬러주는 것이 항상 좋습니다. 그 이유는 주어진 동전들이 전부 배수관계에 놓여있기 때문입니다. 그렇기에 큰 동전이 사용이 가능하다면, 작은 동전을 사용하는 것보다 항상 좋은 선택이 되는 것입니다. 따라서 배수 ..

[코드트리] Backtracking - 백트래킹 / 재귀 연습문제 백트래킹. 대충 알고있는건 백트래킹 == 완전탐색(모든 경우의 수를 무식하게 찾기)에서 가지치기로 효율 높임 이정도라서..ㅋㅋ 연습문제도 풀어봐야겠다 대부분의 알고리즘 문제들은 원하는 모든 조합을 만들어 그 중 문제에서 원하는 답을 고르는 식으로 해결이 가능합니다. 만약 n 제한이 작고, 모든 조합을 만드는 데 걸리는 시간이 문제에서 주어진 제한 시간보다 더 작다면, 항상 모든 조합을 다 만들어 보는 것이 가독성 측면에서나, 코드를 작성하는 입장에서 가장 좋다고 할 수 있을 것입니다. 다만, (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 1), (1, 1, 1, 2, 2), .. 등 여러 가능한 순열과 조합을 만드는 것을 for문 만을 ..

[C++/백준] 11052 : 카드 구매하기 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. (카드 종류는 생략) 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 예를 들..

이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음

728x90

티스토리툴바