알고리즘

[프로그래머스 Lv.2] 오픈채팅방 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이회원의 uid와 회원의 닉네임을 항상 매핑하고 있는 딕셔너리를 관리하면서, 닉네임 변경이나 채팅방을 들어오고 나가는 내역을 로그로 쌓아놓고, 이를 닉네임과 매칭하여 출력하면 되는 간단한 문제이다.def solution(records): logs = [] # 닉네임 변경이나 채팅방을 들어오고 나가는 내역을 저장할 배열 members = {} # {회원id: 닉네임}을 저장할 딕..

[프로그래머스 Lv.3] 징검다리 건너기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이문제를 풀기 위한 가장 단순한 방법을 생각해 보면, 단순히 사람이 한 명씩 지나갈 때마다 돌의 밟을 수 있는 횟수를 1 줄이고, 더 이상 밟을 수 없는 돌이 연속적인지 체크하면서 더 이상 지나갈 수 없을 때까지 반복하였을 때 최댓값을 알아내는 방법이다. 하지만 이는 데이터의 수 때문에 불가능하다. 만약 20만 개의 돌을 2억 번까지 밟을 수 있다고 하면 반복문의 수가 20만 * 2억 =..

[프로그래머스 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바이트이므..