알고리즘 (26) 썸네일형 리스트형 백준 - 5622 다이얼 본 문제의 요구사항은 다음과 같다 할머니가 오래된 다이얼을 돌리는데 걸리는 시간은 숫자의 위치에 따라 일정하게 증가한다. 즉 1은 2초 , 2는 3초 ... 9는 10초 소요된다. 할머니는 숫자를 알파벳으로 외운다. 즉 2~ 9 범위사이의 숫자만 알파벳으로 외우는 것이 가능할 것이다. 본문제를 풀기위한 특별한 기술이 필요하지 않다. 알파벳 A ~ Z 각각 소요시간을 테이블로 만든후 입력받은 문자열을 하나씩 체크해가면서 소요시간을 합산하면 된다. 단 알파벳을 통해 배열의 첨자(인덱스)를 찾기위해서는 'A' 만큼 뻬면된다. 구현된 코드는 아래와 같다 #include #include using namespace std; int main() { // A 부터 Z 까지 각 다이얼을 돌리는데 걸리는 시간에 대한 값.. 백준 - 4963 섬의 개수 본 문제의 요구사항은 다음과 같다 정사각형 배열이 육지와 바다로 표시되는데 육지이면 1 섬이면 0으로 표시된다. 서로 다른 육지가 이동할수 없다면 이들은 각각 다른 섬이다. 즉 임의의 A, B 사이에 가로, 세로 그리고 대각선 방향으로 인접되어 있지 않아야 섬으로 인정된다. 아래 그림의 경우 모든육지는 대각선 방향으로 이어져 있기 때문에 한개의 섬으로 취급된다. 주어진 배열에서 섬이 몇개인지 구하는 프로그램을 작성하여야 한다. 본문제를 풀수 있는 방법은 여러가지 가 있겠지만, DFS , BFS 로 풀이하는 것이 괜찮아 보인다. step1) 방문하지 않은 임의의 육지를 방문한다. step2) 인접한 8방향의 위치중 육지인 곳을 방문한다. step3) step2 에서 방문한 각 육지에서 인접된 방문되지 않은.. 백준 - 4673 셀프 넘버 본 문제의 요구사항은 다음과 같다 임의의 숫자 n 에서 n 을 구성하는 각자리숫자의 합을 d(n) 이라고 한다. 예를 들면 d(15) = 15 + 1 + 5 = 21 이다. n 은 d(n) 의 생성자라고 한다. 즉 15는 21의 생성자이다. 임의의 숫자 m 이 생성자가 없다면 이러한 숫자를 셀프넘버라고 한다. 10000 보다 작거나 같은 모든 셀프넘버를 한줄에 하나씩 출력해야 한다. 본문제의 풀이과정은 다음과 같다. 10001 개의 배열을 잡고 0으로 초기화 한다. n 은 d(n) 보다는 무조건 작기때문에 1부터 10000 까지만 d(n) 을 구한다. 배열의 d(n) 에 해당되는 index 의 값을 1로 세팅한다. 모든 d(n) 계산 완료후 배열에서 0 인 값의 index 의 집합이 셀프넘버의 집합이 된.. 백준 - 4354 문자열 제곱 본 문제의 요구사항은 다음과 같다. 임의의 두문자열의 곱은 두 문자열을 서로 이어 붙인 것으로 표현한다. 예를들면 "abcd" * "efg" = "abcdefg" 따라서 문자열의 제곱도 위와 같은 방식으로 표현할수 있다. ("abcd")2 = "abcdabcd" ("aac")3 = "aacaacaac" 임의의 문자열(s) 이 주어졌을때 어떤 문자열 a에 대해서 s=an을 만족하는 가장 큰 n 을 구해야 한다. 본문제의 풀이과정은 아래와 같다. a 의 길이는 s 의 길이의 약수이어야 한다. 따라서 s 의 약수길이에 해당되는 모든 sub 문자열이 동일한 값으로 반복되는지 검사를 하면 된다. 반복여부를 판단하기 위해서는 나머지 연산자를 적절히 이용하면 된다. 예를들어 s = "abcdabcdabcd" 라고했을.. 백준 1110 - 더하기 사이클 본 문제의 요구사항은 다음과 같다 - 주어지는 숫자의 범위는 0 ~ 99 이다 - 주어진 숫자의 1의 자리와 , 각자리 숫자의 합의 1의 자리 를 이어붙여 새로운 숫자를 만든다. - 이러한 과정을 반복하여 원래 수로 돌아오는 횟수가 몇번인지 구한다. 본 문제를 풀기위해서 한 사이클 즉 하나의 숫자를 다음 숫자로 변환하는 과정만 잘 도출해 내면 간단하게 해결할 수 있다. 1의 자리 숫자를 구하기 위해서는 10으로 나눈 나머지 이므로 % 연산자를 활용하면 아래 코드처럼 구현할 수 있다. #include #include #include using namespace std; void process(); int main() { int num; cin >> num; int numClone = num; int cyc.. 백준 1463 - 1로 만들기 본문제의 요구사항은 다음과 같다 1. 어떤 수 N 에서 정해진 연산을 통해 1로 만드는 최소횟수를 구한다. 2. 연산은 나누기3 , 나누기2 , 뻬기 1중 하나를 선택할수 있다. 단 나누기 연산은 나누어 떨어질 때에만 가능하다. 본 문제를 풀기위해서는 가능한 모든 경우의 수를 따져바야 하는데 DFS ( 깊이 우선 탐색 ) 를 이용하면 된다. 예를 들어 N 이 12 라고 생각해보면 N 은 3으로도 나누어떨어지고 , 2로도 나누어 떨어진다. 즉 F(12) = min ( F(12/2) , min ( F(12/3) , F(12-1))) + 1 로 계산할수 있다. 좀더 풀이를 나아가보면 .. F(6) = min( F(6/2) , min(F(6/3), F(6-1))) + 1 F(4) = min(F(4/2) , F(.. 백준 1158 - 조세퍼스 문제 본문제는 K 값에 해당 한만큼 점프를 하면서 N 개의 배열을 탐색하는데 매 점프마다 만나는 배열의 Index 를 순서대로 출력해 주면 된다. 물론 한번 만나는 index 위치는 다음 순회때에는 계산되지 않도록 한다. 특별한 알고리즘 없이 배열과 배열의 탐색으로 본 문제를 해결할수 있다. 한가지 주의할 사항은 K 값을 최소화 해줄 필요가 있다는 점이다. 만약 방문하지 않은 남은 index 들이 5이고 k 가 7 이라면 7번을 점프할 필요가 없다. 즉 임의의 지점에서 자신의 위치로 다시 돌아오는 횟수만큼을 제할 수 있다. 아래 그림과 같이 start 지점에서 7번 점프하는것과 2번 점프하는 것과 동일하다. 즉 다음 점프의 횟수는 남은 index 개수로 나눈 나머지와 같다. 이러한 착안들을 기초로 작성된 코드.. 백준 1065 - 한수 본문제의 요구사항은 주어진 값보다 작은 한수(각자리수가 등차수열을 이룸)의 갯수 를 구하는 것이다. 본 문제를 풀기위해서는 두가지 아이디어가 필요하다. 1. 99 이하의 숫자들은 무조건 한수이다. 2. 세자리 숫자 값 을 각 자리별 값을 구하기 위해서 modulation 연산을 이용한다. 간단하게 코드를 살펴보면 아래와 같다. #include #include using namespace std; bool isSameDiffNum(int n) { vector arr; int nClone = n; // 숫자의 각 자리별 값을 vector 로 변환한다. while (n) { arr.push_back(n % 10); n /= 10; } int firstDiff; // 각 자리별 차이값이 등차 여부를 확인한다. .. 이전 1 2 3 4 다음
