본문 바로가기

알고리즘

백준 알고리즘 1022번. 소용돌이 예쁘게 출력하기 소스 및 해설 빙글 빙글~ 세상은 어지럽지만 그가운데 고요하고 돌지 않는 곳이 있지요. 마치 태풍의 눈처럼 말입니다. 비록 저 높은 절벽으로부터 폭포가 쏟아지는 가운데 있지만, 그 뒷편에 아주 안전한 장소에서 보살핌을 받는 어린 새처럼 하나님을 신뢰하고 의지하는 사람들 또한 하나님께서 지키시고, 하나님께서는 그러한 사람들을 끝까지 포기하지 않고 저 천국으로 인도하실 수 있는 분이심을 믿습니다 :) 여호와께서 그를 황무지에서, 짐승의 부르짖는 광야에서 만나시고 호위하시며 보호하시며 자기 눈동자같이 지키셨도다 ( 성서 신명기 32장 10절 말씀 ) 이번 백준 알고리즘 문제는 빙글 빙글 소용돌이가 돌아가는 순서대로 숫자를 매겨서 표시하는 문제인데요. 은근히 함정들이 있더라구요. ​ https://www.acmicpc.net.. 더보기
백준 알고리즘 5567. 결혼식 빰빠빠바~ 빰빠빠바~ 화려한 음악소리와 함께 결혼식이 시작되었습니다. ​ https://www.acmicpc.net/problem/5567 5567번: 결혼식 문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m www.acmicpc.net 상근이라는 친구가 결혼식에 친구도 초대하고 친구의 친구까지는 초대.. 더보기
백준 알고리즘 1748. 수 이어쓰기 원본문제 링크 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 만약 1 2 3 4 5 6 7 8 9 10 11 12 ... 이렇게 숫자를 계속 써내려갈때 1부터 100까지의 숫자를 하나하나씩 센다면 숫자 갯수는 총 몇개일까요? 예를 들면 12라는 숫자는 1과 2를 각각 세어서 2개로 셉니다. ​ 그러면 총 192개입니다. 어떻게 그렇게 되냐구요?? 0~9 : 9개 10~99 : 90개 X 2자리 = 180개 100 : 1개 X 3자리 = 3개 모두 합치면 192개가 딱 나오지요. ​ 그렇다면 1부터 12345까지 이런 식으로 센다면 숫자 갯수는 몇개나 될까요? 컴퓨터 없이.. 더보기
백준 알고리즘 1934번. 최소공배수 초등학교 산수(요새 말로는 수학) 시간에 "최소공배수"를 구해본 기억이 있으신가요? 기억이 가물가물한 분들이 더욱 많을듯 해서 다시 상기시켜드립니다. ​ 2개의 수의 배수중 가장 작은 수가 바로 최소공배수입니다. 이를 테면 12과 20의 배수이면서 그중 가장 작은 배수는 12x20=240이 아니라, 60인 것이지요. 60이란 숫자는 12의 배수인 동시에 20의 배수이기도 합니다. ​ 이런 최소공배수를 구하는 방법이 있습니다. 알고리즘 풀이로 널리 알려진 유클리드 호제법이란 방법도 있지만, 크레이는 그냥 클래식한 방법으로 설명 및 풀이를 진행하도록 하겠습니다. ​ 수학 시간의 배운 내용을 그대로 펼쳐볼까요? 맨 처음 2개의 숫자를 나란히 씁니다. 두 수를 동시에 나눌수 있는 숫자를 왼쪽에 적어줍니다. 그리.. 더보기
백준알고리즘 1149번. RGB거리 풀이 최근에 익힌 동적분할 메모이제이션으로 2번만에 성공했습니다 :) 최대 1000개의 직선으로 늘어선 건물을 빨강, 녹색, 파랑색으로 칠하면서 각 건물당 드는 비용을 최소화하는 경로를 찾는 문제인데요. 각 이어진 건물은 같은 색으로 칠해서는 안되는 제약이 있습니다. ​ 문제링크 https://www.acmicpc.net/problem/1149 ​ 크레이는 동적분할로 풀었습니다. 소스 설명보다는 그냥 원리 설명을 드릴텐데요. 간편화를 위해 빨강은 R, 녹색은 G, 파랑은 B로 표현해보도록 하겠습니다. ​ 1번째 색상을 R로 칠하고, 2번째 이후에는 G, B 로 칠하기 시작하는 경로중 작은 값을 구합니다. 1번째 색상을 G로 칠하고, 2번째 이후에는 R, B 로 칠하기 시작하는 경로중 작은 값을 구합니다. 1번.. 더보기
백준 알고리즘. 팩토리얼 0개 개수 풀이 및 해설 n팩토리얼은 1부터 n까지의 곱을 의미하지요. ​ 예를 들면 10팩토리얼은 1x2x3x4x5x6x7x8x9x10 입니다. 10팩토리얼의 값은 얼마일까요? 3628800 입니다. 그렇다면 20팩토리얼의 값은 얼마일까요? 2432902008176640000 입니다. 컴퓨터가 얼마나 빠른지 이 숫자를 0.001초 이내에 계산합니다. 엄청나지요. ​ 그렇지만 컴퓨터는 계산할 수 있는 자릿수 제한이 있어서 무한정 계산을 할 수 있는 것은 아니고 그 자릿수 이내에서만 계산이 가능합니다. ​ 만약 500팩토리얼을 계산한다면 1x2x3x4x...x500 어마어마한 숫자가 됩니다. 10팩토리얼은 뒤에 붙는 0의 갯수만 2개이고 ( 3628800 ) 20팩토리얼은 뒤에 붙는 0의 갯수가 4개이지만, ( 2432902008.. 더보기
백준 1181번. 단어정렬 문제풀이와 해설 요새 '초라기 습격' 이란 문제를 풀어보고 있는데 시간제한으로 난이도가 장난 아니라서, 이런 저런 고민 아닌 고민을 하고 있습니다. ​ 풀이에 성공하신 분들이 소스를 공개하긴 했지만 크레이는 어디까지나 혼자 힘으로 100% 이해해서 푸는 걸 목적으로 하기 때문에 며칠째 끙끙거리고 있습니다 ㅎㅎ ​ 우선 쉬운 문제 풀어보면서 머리를 좀 식힐겸사~ ​ 단어정렬 문제 링크 주소는 아래와 같습니다. ​ https://www.acmicpc.net/problem/1181 ​ 이번 문제의 목적은 짧은 단어순 정렬, 동일한 글자수라면 알파벳순 정렬, 그리고 중복출력을 제거하는 부분인데요, 아주 간단한 방법으로 해결 가능합니다. ​ 아래와 같은 단어 목록을 메모리에 저장할 때, but i wont hesitate 앞에 .. 더보기
백준알고리즘 1005번. ACM Craft 시간제한 때문에 꽤 까다로운 문제였습니다만, 결국 동적계획법 알고리즘을 숙달해서 풀었습니다. 지난번 피보나치 수열 때 유사 기술을 숙달했던게 도움이 되었군요 :) ​ 문제와 조건은 그냥 링크로 걸어드리구요. https://www.acmicpc.net/problem/1005 ​ 처음에는 트리를 구성해서 큐로 풀어보려 했습니다만, 시간제한으로 문제가 안 풀리더라구요. 어떤 경우가 주어지더라도 1초 이내에 패스를 해야 하는 문제입니다. ​ 아무리 별의 별 방법을 동원해도 안되던 찰나에 백준 사이트에 질문 답변을 참조하고서야 "동적계획법"이라는 방법을 사용한 "이모제이션"이라는 기법을 알게되었고 관련 기술을 숙달한 후에 직접 코딩으로 짜서 풀었습니다 :) 내공이 하나 늘어난 느낌이라 뿌듯하더라구요 ㅎㅎ ​ 채점.. 더보기