본문 바로가기

코딩

백준알고리즘 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초 이내에 패스를 해야 하는 문제입니다. ​ 아무리 별의 별 방법을 동원해도 안되던 찰나에 백준 사이트에 질문 답변을 참조하고서야 "동적계획법"이라는 방법을 사용한 "이모제이션"이라는 기법을 알게되었고 관련 기술을 숙달한 후에 직접 코딩으로 짜서 풀었습니다 :) 내공이 하나 늘어난 느낌이라 뿌듯하더라구요 ㅎㅎ ​ 채점.. 더보기
백준 1003 피보나치 함수 문제풀이와 해설 은근히 헷갈리는 문제이긴 했는데, 헤메다가 결국 풀이했습니다 :) ​ 피보나치의 합계를 푸는거라면 좀 수월할텐데, 재귀호출에서 0과 1이 나오는 횟수를 풀라니 크레이에게는 좀 난해했습니다. ​ 피보나치 수열에서 재귀호출로 계산할 때 0과 1이 연산에 들어가는 횟수인지 숫자가 클수록 기하급수적으로 늘어나더라구요. ​ 이것 저것 고민하다가 인터넷 다른 분의 게시글도 참고하긴 했지만, 결국은 독자적으로 초고속으로 작동하도록 새로 만들었습니다. ​ long long 형 변수로 선언해서 60피보나치의 0과 1의 갯수까지도 계산할 수 있으며 ( 79로 시도해봤었는데 숫자 범위 초과로 엉뚱한 숫자가 구해지더라구요. 혼란드린점 죄송합니다 ) 60피보나치일 경우라도 연산시간은 10ms 이내인듯 합니다 :) 측정해보기는 .. 더보기
백준 알고리즘 4673번 풀이와 해설 백준 알고리즘 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... n을 d(.. 더보기
백준 알고리즘 첫번째 문제는 1000번 1번부터 시작할 줄 알았는데, 시작번호는 1000번부터군요. 첫문제는 음?.. 그냥 사용법을 익히는 연습문제 수준입니다. 온코더와 다른 점은 온코더는 풀이할 함수내부만 구현하면 되지만, 백준 알고리즘의 경우 문제를 풀때 완전히 공란으로 제공되기 때문에 전체 코드를 모두 구현해야 하는데, 다행히도 기본 샘플코드는 주어집니다. 문제 풀이에 들어가면 '여기'라고 표시된 부분이 있을 겁니다. 클릭하면 첫번째 문제는 정답 전체를 그대로 공개해줍니다. 앞으로 이런식으로 풀라는 것이지요. ​ 입력은 cin 으로 출력은 cout 으로 풀면 되는 것으로 보입니다. 다시 전 화면으로 돌아와서 제출 탭을 선택하면 정답을 제출할 수 있습니다. 소스코드에 그대로 코드를 넣어주시면 되는데요. 간단한 코드라 크레이는 복붙하지 않고.. 더보기
백준알고리즘?! 헉! 알고리즘 관련해서 블로그를 검색하다 보다 보니 "백준알고리즘 풀이" 이런 글들이 많이 보이길래 처음에는 알고리즘 기법인줄 알았습니다. 근데 이상하게 숫자가 뒤에 5자리 정도 붙길래 이게 뭘까 하고 검색해보니 ​ ! !! !!! ​ 일만개 이상의 알고리즘 문제를 풀어볼 수 있는 사이트가 있더라는 것이지요! 숫자는 바로 백준알고리즘 문제번호이구요! https://www.acmicpc.net Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 가입해보니 인사글이 나오는데 최백준이라는 분이 운영하는 사이트입니다. ​ 게다가 참가자가 무려 13만명 ! 무시무시한 개발자 랭킹 사이트지요. ​ 규모면.. 더보기