본문 바로가기

알고리즘

 (138)
[BOJ] [Python] 1914: 하노이 탑 전형적인 하노이 탑 구현 문제이다. def honoi_tower(n, start, tmp, end): if n == 1: print(start, end) else: honoi_tower(n-1, start, end, tmp) print(start, end) honoi_tower(n-1, tmp, start, end) num = int(input()) print(2 ** num - 1) if num
[복잡도] 시간 복잡도와 공간 복잡도 시간 복잡도 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 알고리즘을 위해 필요한 메모리의 양
[최단 경로 트리] 플로이드-워셜 알고리즘[Floyd-Warshall] 플로이드-워셜 알고리즘에 대해 알아보자. 플로이드-워셜 알고리즘은 '거쳐 가는 기점'를 기준으로 최단 거리를 구한다. 예를 들어보자. 아래와 같은 그래프가 있다. 이차원 배열의 형태로 출력하면 다음과 같다. 위 상태의 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. 이제 이 배열을 '거쳐 가는 기점'을 기준으로 반복적으로 갱신할 것이다. 그렇게 한다면 결국엔 모든 A에서 B의 최소 비용을 구해진다. 거쳐 가는 기점이 1인 경우 이렇게 거쳐 가는 기점이 1, 2, ... N인 경우를 모두 확인한다. 다익스트라 알고리즘 vs 플로이드-워셜 알고리즘 공통점 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 차이점 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구한다. 플로이드-워..
[이진탐색] 깊이 우선 탐색[DFS]과 백트래킹[Backtracking] 차이점 DFS와 Backtracking의 차이점을 알아보자. DFS 완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로를 탐색한다. 불필요한 경로를 사전에 차단하는 행동이 없다. 따라서 자원 소모가 심하다. Backtracking 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로가 갔다면 더 가지 않고 되돌아온다. 이는 가지치기라고 불린다. 불필요한 경로를 조기 차단하기 때문에 확인해야 하는 경로 수를 줄일 수 있다. 위와 같은 트리가 있다. ALT라는 단어를 찾아보자. DFS는 ALT라는 단어를 찾기 전까지 모든 노드를 방문한다. Backtracking은 ALT라는 단어를 찾는 과정에서 ALT라는 단어가 될 수 없을 것 같은 경로에 갔다면 더 가지 않고 돌아온다.
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 메뉴 리뉴얼 문제를 정리해보자. 이전에 각 손님이 주문할 때 가장 많이 함께 주문했던 단품 메뉴들을 코스요리 메뉴로 구성한다. 1) 코스요리 메뉴는 최소 2가지 이상의 단품 메뉴로 구성된다. 2) 최소 2명 이상의 손님으로부터 주문된 단품 메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다. 입출력 1. orders: 각 손님이 주문한 단품 메뉴들이 문자열 형식으로 담긴 배열 2. course: "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품 메뉴들의 개수가 담긴 배열 풀이를 생각해보자. 첫 번째 예로 생각해보자. ABCFG로 만들 수 있는 2, 3, 4개 코스의 후보는 아래와 같다. 이렇게 orders의 메뉴 구성마다 N개 코스의 후보를 구한다. 최종적으로 N개 코스마다 가장 많이 주문된 후보가 정답이다. ..
[이진탐색] 하한선[Lower bound], 상한선[Upper bound] 개념 이진탐색의 상한선, 하한선은 이진탐색 알고리즘에서 약간 변경된 것이다. 중복된 자료가 있을 때 유용하게 사용된다. 1. 하한선[Lower bound] 데이터내에서 원하는 값보다 '같거나 큰 값' 중에 가장 앞에 있는 원소의 위치를 리턴한다. 위 이미지에서 lower_bound(3)은 index 3이다. 2. 상한선[Upper bound] 데이터내에서 원하는 값보다 '큰 값' 중에 가장 앞에 있는 원소의 위치를 리턴한다. 위 이미지에서 upper_bound(3)은 index 6이다. + 만약 모든 데이터가 원하는 값보다 작을 경우? 데이터 범위밖의 값을 리턴해야 한다. 그래서 일반적인 이분탐색과 달리 high를 len(array)-1이 아니라 len(array)로 한다. ​구현 # 이진탐색 def b..
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 순위 검색 문제를 정리해보자. 카카오는 하반기 경력 개발자 공개채용을 진행 중이다. 현재 지원서 접수와 코딩테스트가 종료되었다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였다. 항목은 아래와 같다. 개발언어: cpp, java, python 지원 직군: backend, frontend 지원 경력: junior, senior 소울푸드: chicken, pizza 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에게 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인지 쉽게 알 수 있는 도구를 만들어보자. 개발팀에서 궁금해하는 내용: '[조건]을 만족하는 사람 중 코딩테스트 점수 X점 이상 받은 사람은 모두 몇 명인가?' 예) 코딩테스트에 ja..
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 신규 아이디 추천 문제를 정리해보자. 카카오 아이디가 주어진다. 규칙에 맞지 않는 아이디라면 규칙에 맞는 아이디로 바꿔야 한다. 다음은 카카오 아이디의 규칙이다. 1. 아이디의 길이는 3자 이상 15자 이하여야 한다. 2. 아이디는 알파벳 소문자, 숫자, 빼기, 밑줄, 마침표 문자만 사용할 수 있다. (단, 마침표는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없다.) 규칙 맞는 아이디로 처리하는 과정은 아래와 같다. 1단계: 모든 대문자를 대응되는 소문자로 변환한다. 2단계: 알파벳 소문자, 숫자, 빼기, 밑줄, 마침표를 제외한 모든 문자를 제거한다. 3단계: 마침표가 2번 이상 연속된 부분을 하나의 마침표로 치환한다. 4단계: 마침표가 처음이나 끝에 위치한다면 제거한다. 5단계: 빈 문자열이라면, "a"를 ..
[프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 다단계 칫솔 판매 문제를 정리해보자. 위 판매망은 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태이다. 각각은 자신을 조직에 참여시킨 추천인에게 연결되어 피라미드식의 구조를 이루고 있다. 조직의 이익 분배 규칙은 다음과 같다. 1. 이익에서 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가진다. + 모든 판매원은 자신이 칫솔 판매에서 발생한 이익뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10%까지 자신에 이익이 된다. + 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배된다 2. 단, 10%를 계산할 때는 원 단위에서 절사한다. 그리고 10%를 계산한 금액이 1원 미만인 경우에는 이득을 분배하지 않고 자신이 ..
[프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 로또의 최고 순위와 최저 순위 문제를 정리해보자. 로또는 1부터 45까지 숫자 중에서 6개를 찍어서 맞히는 대표적인 복권이다. 아래는 로또의 순위를 정하는 방식이다. 민우는 로또를 구매했다. 하지만 숫자 몇 개는 알아볼 수 없게 됐다. 민우의 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보자. (0은 알아볼 수 없는 숫자이다.) 예) 민우의 번호 : 44, 1, 0, 0, 31, 25 당첨 번호 : 31, 10, 45, 1, 6, 19 최고 순위 : 3등 (4개 번호가 일치) 최저 순위 : 5등 (2개 번호가 일치) 풀이를 생각해보자. 먼저, 민우가 구매한 로또의 번호와 당첨 번호가 몇 개가 일치하는지 확인한다. 그리고 최고 순위와 최저 순위를 구한다. 최고 순위 : 0이 모두 당첨 숫자가 일 때이다. 최저 순위 : 0이 모두..

티스토리툴바