알고리즘

[프로그래머스 Lv.4] N으로 표현 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43236풀이아래와 같이 먼저 단순하게 생각할 수 있는 방법으로 풀이해 보았다. 하지만 역시나 시간 초과로 인해 실패하였고, 이는 아래 풀이처럼 완전 탐색을 사용했을 때 탐색해야 하는 데이터가 너무 많기 때문이다.징검다리를 이루는 돌의 수가 최대 5만개이고, 제외할 수 있는 돌의 수도 5만 개 이하기 때문에 최악의 경우 5만 개 중 2만 5천 개의 돌을 제외하는 조합을 모두 계산해야 한다. 이는 정말 말도 안 되는 수이다. (단순히 생각해 봐도 50000!/(50000-25000)! 이니까 50000부터 25000까지 곱한 값이다. 대충 3만을 25000번 곱했다고 봐도 (3*10^4)^2..

[프로그래머스 Lv.2] 순위 검색 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72412  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2 문제라는 레벨 분류가 무색하게 문제 풀이를 위한 방법을 고민하는 게 너무나 어려웠다. 구현 난이도로만 따지면 레벨 2가 맞지만 문제 해결을 위한 방법을 생각해 내는 것 자체가 어려워 체감 난이도가 훅 올라가지 않았나 싶다. 처음에는 간단히 생각해서 전체 데이터를 순회하면서 조건에 일치하는 사람들의 수를 카운트하는 방법을 고민했으나, 데이터의 수를 보고 다른 방법을 생각해야 한..

[프로그래머스 Lv.2] 가장 큰 수 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이주어진 숫자들을 가지고 가장 큰 수를 만들면 되는 문제이다. 그렇기에 가장 큰 수를 만들 수 있는 방법을 먼저 고민해야 한다.쉽게 생각할 수 있듯이 높은 자릿수에 큰 수가 위치하면 된다. 그렇기에 배열 내의 숫자를 가장 높은 자릿수의 내림차순으로 정렬하고, 이를 하나로 합치면 된다.10, 7, 3이 있는 상황을 예로 들어보자. 그렇다면 높은 자릿수에 가장 큰 수가 위치한 7, 3, 10..

[프로그래머스 Lv.2] 수식 최대화 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2 문제치고는 구현하는데 조금 어려움이 있었다. 개인적으로 레벨 3 정도는 되어야 하지 않나라는 생각이 들 정도로 어려움이 있었다.우선 문제 풀이는 아래와 같은 순서로 진행하였다.주어진 문자열을 피연산자와 연산자로 분리하여 배열에 저장, 동시에 사용되는 연산자들을 순열로 조합하기 위해 연산자들만 따로 저장연산자들로 이루어진 조합을 permutation을 사용하여 생성조합을 순회하며..

[프로그래머스 Lv.3] 불량 사용자 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이간단하게 *가 나오면 체크를 하지 않고, 그 외의 문자가 나오는 경우에는 같은 자리에서 문자가 일치하는지 확인하고 아니라면 체크를 종료하는 방식으로 풀이하였다.처음에는 전체 회원 아이디 중 각 banned_id와 일치하는 경우를 뽑아놓고, 이 중에서 선택하여 조합을 만드려고 하였으나 구현이 복잡하여서 처음에 순열을 먼저 만들어두고 순열 전체를 체크하는 방식으로 변경하였다.from ite..

[프로그래머스 Lv.2] 소수 찾기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이문자열을 이루는 각 숫자를 조합하여 특정 숫자를 만들고 이 수가 소수인지 체크하면 되는 간단한 문제이다.풀이 순서는 다음과 같다.문자열을 한 자리씩 잘라서 한 자리의 정수로 만든다.한 자리 정수들을 사용하여 만들 수 있는 수들을 permutation을 사용해 모두 알아낸다.2번에서 만든 수들이 소수인지 체크하고 소수의 수를 기록한다.from itertools import permuta..

[프로그래머스 Lv.2] 카펫 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이문제 해결을 위해 성립해야 할 조건은 아래와 같다.카펫의 가로, 세로의 곱은 카펫의 총 넓이이기에 갈색과 노란색 부분을 합친 넓이이다.가장자리를 제외한 카펫의 넓이, 즉 가로와 세로에서 2를 뺀 값들의 곱은 카펫의 노란색 부분과 같다.완전 탐색으로 위의 조건들을 체크하면서 모든 조건을 만족하는 가로와 세로의 길이를 찾아가면 된다.def solution(brown, yellow): ..

[프로그래머스 Lv.4] 호텔 방 배정 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 4의 난이도를 자랑하는 문제답게 정말 아이디어를 떠올리기가 어려운 문제였다.우선 필자는 처음에 배열에다가 배정 여부를 저장하고 이를 사용하여 문제를 해결하고자 하였다. 하지만 이렇게 하면 k의 크기가 최대 "1조"이기 때문에 시간 초과는 물론이고, 어마무시한 배열의 크기 때문에 메모리 부족으로 인한 런타임 에러가 발생한다. (int를 담는 배열이라고 가정하면 int형이 4바이트이므..

[프로그래머스 Lv.2] 모음사전 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 단순히 수학적으로 개수를 계산해 푸는 방법이나 등비수열의 합을 이용해 해당 자리에 어떤 모음이 위치하는지에 맞춰 풀이할 수도 있으나 쉽게 생각하기 어려운 방법이었다.그래서 재귀를 활용하여 실제로 A, E, I, O, U를 사용한 모음사전을 생성하고 이를 전체적으로 순회하면서 일치하는 단어가 나타나는 그 인덱스 + 1을 반환하는 방식으로 문제를 풀이하였다. 물론 이 방법은 앞서..

[프로그래머스 Lv.2] 하노이의 탑 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이그 유명한 하노이의 탑을 풀기 위한 방법을 순서대로 배열에 넣어 출력하면 되는 문제이다.재귀를 활용해 풀이하면 되는 문제인데, 재귀 문제가 모두 그렇듯이 재귀 과정에서 어떤 연산을 거쳐야 하는지 정의해야 하고, 종료 조건도 정의해야 한다.우선 재귀 과정을 거치면서 어떤 연산을 거쳐야 하는지 고민을 해봐야 한다. 연산에서의 규칙을 찾을 수 있게 "/"로 단계를 분리해서 적어보면 아래와 같..