본문 바로가기

풀이

백준 알고리즘 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까지 이런 식으로 센다면 숫자 갯수는 몇개나 될까요? 컴퓨터 없이.. 더보기
백준알고리즘 1149번. RGB거리 풀이 최근에 익힌 동적분할 메모이제이션으로 2번만에 성공했습니다 :) 최대 1000개의 직선으로 늘어선 건물을 빨강, 녹색, 파랑색으로 칠하면서 각 건물당 드는 비용을 최소화하는 경로를 찾는 문제인데요. 각 이어진 건물은 같은 색으로 칠해서는 안되는 제약이 있습니다. ​ 문제링크 https://www.acmicpc.net/problem/1149 ​ 크레이는 동적분할로 풀었습니다. 소스 설명보다는 그냥 원리 설명을 드릴텐데요. 간편화를 위해 빨강은 R, 녹색은 G, 파랑은 B로 표현해보도록 하겠습니다. ​ 1번째 색상을 R로 칠하고, 2번째 이후에는 G, B 로 칠하기 시작하는 경로중 작은 값을 구합니다. 1번째 색상을 G로 칠하고, 2번째 이후에는 R, B 로 칠하기 시작하는 경로중 작은 값을 구합니다. 1번.. 더보기
백준알고리즘 1005번. ACM Craft 시간제한 때문에 꽤 까다로운 문제였습니다만, 결국 동적계획법 알고리즘을 숙달해서 풀었습니다. 지난번 피보나치 수열 때 유사 기술을 숙달했던게 도움이 되었군요 :) ​ 문제와 조건은 그냥 링크로 걸어드리구요. https://www.acmicpc.net/problem/1005 ​ 처음에는 트리를 구성해서 큐로 풀어보려 했습니다만, 시간제한으로 문제가 안 풀리더라구요. 어떤 경우가 주어지더라도 1초 이내에 패스를 해야 하는 문제입니다. ​ 아무리 별의 별 방법을 동원해도 안되던 찰나에 백준 사이트에 질문 답변을 참조하고서야 "동적계획법"이라는 방법을 사용한 "이모제이션"이라는 기법을 알게되었고 관련 기술을 숙달한 후에 직접 코딩으로 짜서 풀었습니다 :) 내공이 하나 늘어난 느낌이라 뿌듯하더라구요 ㅎㅎ ​ 채점.. 더보기
백준 1003 피보나치 함수 문제풀이와 해설 은근히 헷갈리는 문제이긴 했는데, 헤메다가 결국 풀이했습니다 :) ​ 피보나치의 합계를 푸는거라면 좀 수월할텐데, 재귀호출에서 0과 1이 나오는 횟수를 풀라니 크레이에게는 좀 난해했습니다. ​ 피보나치 수열에서 재귀호출로 계산할 때 0과 1이 연산에 들어가는 횟수인지 숫자가 클수록 기하급수적으로 늘어나더라구요. ​ 이것 저것 고민하다가 인터넷 다른 분의 게시글도 참고하긴 했지만, 결국은 독자적으로 초고속으로 작동하도록 새로 만들었습니다. ​ long long 형 변수로 선언해서 60피보나치의 0과 1의 갯수까지도 계산할 수 있으며 ( 79로 시도해봤었는데 숫자 범위 초과로 엉뚱한 숫자가 구해지더라구요. 혼란드린점 죄송합니다 ) 60피보나치일 경우라도 연산시간은 10ms 이내인듯 합니다 :) 측정해보기는 .. 더보기
백준 알고리즘. 10809번. 알파벳 찾기 문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. ​ 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. ​ 출력 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. ​ 예제입력 baekjoon 예제출력 1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 .. 더보기