IT/알고리즘 해설
-
백준. 11047 동전0 | 파이썬, 그리디 알고리즘IT/알고리즘 해설 2021. 10. 28. 00:31
문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 해설 이 문제는 그리디 알고리즘을 사용한다. 그리디 알고리즘이란, 말그대로 "탐욕적"으로 문제를 해결하는 방식인데, 해결해나가는 과정에서 가장 최선의 선택을 해서 풀어나가는 알고리즘이다. 그렇기 때문에 항상 가장 올바른 답을 도출하지는 않는다. 그러나 속도 면에서 다른 그래프 탐색 알고리즘보다 빠르다는 장점이 있다. 준규는 동전을 총 N종류를 가지고 있고, 이 동전들을 사용해서 K원만큼 만들려고 한다. K원을 만들기 위해서 가장 큰 동전부터 선택해나가면서, K원이 될 때까지 동전을 찾으면 된다...
-
프로그래머스. 메뉴 리뉴얼 파이썬 풀이IT/알고리즘 해설 2021. 10. 22. 18:49
해설 이 문제는 모든 조합을 다 구한 뒤, 조합들 중에 가장 최선인 답을 도출하는 문제다. 파이썬으로 엄청 간단하게 풀 수 있다. from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for c in course: t = [] for o in orders: com = combinations(sorted(o), c) t.extend(com) count = Counter(t).most_common() max = -1 for c in count: if c[1] >= max and c[1] > 1: max = c[1] answer.append("".join(c[0])) e..
-
백준 1707. 이분 그래프 (파이썬)IT/알고리즘 해설 2021. 10. 8. 22:05
문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 해설 진짜 역대급으로 삽질했던 문제인 것 같다. 결론부터 말하면 이분 그래프는 dfs나 bfs로 풀 수 있다. 여기서는 dfs로 풀어보기로 한다. 먼저, 이분 그래프가 무엇인지와 dfs가 무엇인지부터 짚고 넘어가보자. 1) 이분 그래프란? - 문제만 보고서는 솔직히 무슨 소리인지 이해가 되질 않았다. 그래서 한참을 문제를 보고 이해하려고 하다가, 결국은 검색으로 해결하였다. (앞으로 문제가 조금 더 친절해졌으면 좋..
-
프로그래머스. 2021 KAKAO BLIND RECRUITMENT. 신규 아이디 추천(파이썬)IT/알고리즘 해설 2021. 9. 29. 23:27
문제 설명 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다. 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다. "네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이..
-
백준 1038. 감소하는 수 (파이썬)IT/알고리즘 해설 2021. 9. 23. 22:06
문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 해설 이 문제는 제대로 안 읽으면 헷갈릴 수 있다. 난이도가 solved.ac 기준 골드 5인데, 문제 자체가 어렵게 쓰여서 골드 5인듯하다. 알고리즘 자체는 어렵지 않다. N번째 감소하는 수란, 0부터 시작해서 감소하는 수 집합에서 N번째 수는 무엇인지 묻는 문제이다. 여기서 감소하는 수란, 주어진 숫자의 맨 첫자리부터 끝자리까지 계속해서 감소하는 수..
-
프로그래머스 2020 카카오 인턴 - 키패드 누르기 해설 (파이썬)IT/알고리즘 해설 2021. 9. 14. 14:14
문제 설명 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4..
-
백준 1010. 다리 놓기 (파이썬)IT/알고리즘 해설 2021. 9. 12. 18:50
문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지..
-
백준 1157번. 단어공부 (파이썬)IT/알고리즘 해설 2021. 7. 3. 18:04
문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. word = input() word = word.upper() from collections import Counter c = dict(Counter(word).most_common()) if len(list(filter(lambda x: x == max(c.val..