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