본문 바로가기

분류 전체보기

 (171)
[이진탐색] 깊이 우선 탐색[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개 코스마다 가장 많이 주문된 후보가 정답이다. ..
[회고] 3월 4일 보호되어 있는 글입니다.
[이진탐색] 하한선[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이 모두..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 파괴되지 않은 건물 문제를 정리해보자. N x M 크기의 행렬 모양의 게임 맵이 있다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있다. 1. 건물은 적의 공격을 받으면 내구도가 감소한다. 2. 건물은 내구도가 0이하가 되면 파괴된다. 3. 건물은 아군의 회복 스킬을 받으면 내구도가 증가한다. 4. 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 된다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수는 몇 개인가? 아래는 프로그래머스에 나온 예이다. 풀이를 생각해보자. 방법 1) 매번 적의 공격 혹은 아군의 회복 스킬을 기본 게임 맵의 내구도에 적용시킨다. 이 방법은 효율성 테스트에서 통과할 수 없다. skill의 행의 길이는 최대 250,000이다. b..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] k진수에서 소수 개수 구하기 문제를 정리해보자. 양의 정수 n이 주어진다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수가 몇 개인지 찾으면 된다. 조건은 아래와 같다. ( P는 소수[Prime Number]를 의미한다.) 1. 소수 양쪽에 0이 있는 경우 : 0P0 2. 소수 오른쪽에만 0이 있는 경우 : P0 3. 소수 왼쪽에만 0이 있는 경우 : 0P 4. 소수 양쪽에 아무것도 없는 경우 : P 단, P는 각 자릿수에 0을 포함하지 않는 소수이다. 예를 들어, 101은 P가 될 수 없다. 풀이를 생각해보자. 예를 들어, 437674을 3진수로 바꾸면 211020101011이다.먼저, 211020101011안에서 조건에 맞는지 확인할 수를 찾자. ( N는 수[Number]를 의미한다.) 0을 기준으로 좌우를 ..

티스토리툴바