Problem solving
-
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가로 - 세로 길이가 정해져 있기 때문에 DP로 풀 수 있었던 문제다. N 번째 위치에서 가능한 타일링은 가로가 1인 경우(N - 1)와 가로가 2인 경우(N - 2), 총 2가지 이다. 이를 점화식으로 나타내면 아래와 같다. DP[n] = DP[n - 1] + DP[n - 2] 추가로 오버 플로우를 방지하기 위해서, 연산 중간마다 나머지 연산을 진행했다. 이는 나머지 연산의 분배 법칙을 통해 가능하다. # (n x 2) 바닥 채우기 # n 번째 바닥 def solution(n): # 경..
[Python] 프로그래머스 2 x n 타일링 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가로 - 세로 길이가 정해져 있기 때문에 DP로 풀 수 있었던 문제다. N 번째 위치에서 가능한 타일링은 가로가 1인 경우(N - 1)와 가로가 2인 경우(N - 2), 총 2가지 이다. 이를 점화식으로 나타내면 아래와 같다. DP[n] = DP[n - 1] + DP[n - 2] 추가로 오버 플로우를 방지하기 위해서, 연산 중간마다 나머지 연산을 진행했다. 이는 나머지 연산의 분배 법칙을 통해 가능하다. # (n x 2) 바닥 채우기 # n 번째 바닥 def solution(n): # 경..
2023.03.04 -
문제 상황 코딩 테스트 문제를 풀다 보면, 다음과 같은 조건이 있을 때가 있다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 위와 같은 조건은 숫자가 너무 커져 발생하는 오버 플로우를 방지하기 위함이다. 하지만 최종 값에만 나머지 연산을 적용할 경우 여전히 오버 플로우가 발생할 때가 있다. # (n x 2) 바닥 채우기 # n 번째 바닥 def solution(n): # 경우의 수 저장 DP = [1, 2] for i in range(2, n): DP.append(DP[i - 2] + DP[i - 1]) return DP[n - 1] % 1000000007 # 최종 값에만 나머지 연산을 적용할 경우 이럴 땐 연산 과정 중간 중간 나머지 ..
Overflow(오버 플로우) 방지하기 : 나머지 연산 활용문제 상황 코딩 테스트 문제를 풀다 보면, 다음과 같은 조건이 있을 때가 있다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 위와 같은 조건은 숫자가 너무 커져 발생하는 오버 플로우를 방지하기 위함이다. 하지만 최종 값에만 나머지 연산을 적용할 경우 여전히 오버 플로우가 발생할 때가 있다. # (n x 2) 바닥 채우기 # n 번째 바닥 def solution(n): # 경우의 수 저장 DP = [1, 2] for i in range(2, n): DP.append(DP[i - 2] + DP[i - 1]) return DP[n - 1] % 1000000007 # 최종 값에만 나머지 연산을 적용할 경우 이럴 땐 연산 과정 중간 중간 나머지 ..
2023.03.04 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 단어의 최대 길이가 5 이하라서, 가능한 모든 단어를 모아 미리 사전을 구성해도 시간 초과가 발생하지 않을 것이라고 판단했다. 경우의 수 : $6^5 = 7776$ 단어 사전을 구성하기 위해서 중복 순열 product를 이용했고, 중복을 방지하기 위해서 set 자료형을 활용했다. # 길이 5 이하의 단어 # 중복 순열 만들어도 시간 초과 X from itertools import product def solution(word): word_dic = set() for p in product..
[Python] 프로그래머스 모음사전 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 단어의 최대 길이가 5 이하라서, 가능한 모든 단어를 모아 미리 사전을 구성해도 시간 초과가 발생하지 않을 것이라고 판단했다. 경우의 수 : $6^5 = 7776$ 단어 사전을 구성하기 위해서 중복 순열 product를 이용했고, 중복을 방지하기 위해서 set 자료형을 활용했다. # 길이 5 이하의 단어 # 중복 순열 만들어도 시간 초과 X from itertools import product def solution(word): word_dic = set() for p in product..
2023.02.23 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 파일명에서 HEAD, NUMBER, TAIL을 구분하기 위해서 GROUP을 활용했다. 필요 없는 0 제거하기 int(문자열)을 사용하면, 앞에 있는 필요 없는 "0"을 자동으로 제거해준다. str.lstrip("0")을 활용할 경우, 숫자 "0"도 제거돼 오류가 발생한다. GROUPS 해당 GROUP에 패턴을 찾지 못했다면, group[i] 빈칸을 가지고 있다. 찾지 못한 경우를 위해 예외처리를 하지 않아도 된다. # 파일명에 포함된 숫자를 반영한 정렬 기능 구현 # 숫자 : 0 ~ 99..
[Python] 프로그래머스 [3차] 파일명 정렬 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 파일명에서 HEAD, NUMBER, TAIL을 구분하기 위해서 GROUP을 활용했다. 필요 없는 0 제거하기 int(문자열)을 사용하면, 앞에 있는 필요 없는 "0"을 자동으로 제거해준다. str.lstrip("0")을 활용할 경우, 숫자 "0"도 제거돼 오류가 발생한다. GROUPS 해당 GROUP에 패턴을 찾지 못했다면, group[i] 빈칸을 가지고 있다. 찾지 못한 경우를 위해 예외처리를 하지 않아도 된다. # 파일명에 포함된 숫자를 반영한 정렬 기능 구현 # 숫자 : 0 ~ 99..
2023.02.22 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 제거할 (2 x 2) 박스를 찾기 위해서, 박스의 왼쪽 상위 좌표를 기준으로 완전 탐색했다. 박스 안에 제거할 좌표가 중복되는 것을 방지하기 위해 set 자료형을 활용했다. 제거할 좌표의 성분은 0으로 바꿔주고, 블록을 순회하여 0을 가장 위로 보냈다. # (2 x 2) -> 한번에 제거 -> 판별을 어떻게 할 것인지??? # 왼쪽 상위 좌표 [i, j] 기준 완전 탐색 # 제거된 후 블럭이 내려옴 -> 어떻게 처리 -> 열 별로 맵 탐색 -> 0 나오면 swap... def soluti..
[Python] 프로그래머스 [1차] 프렌즈4블록 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 제거할 (2 x 2) 박스를 찾기 위해서, 박스의 왼쪽 상위 좌표를 기준으로 완전 탐색했다. 박스 안에 제거할 좌표가 중복되는 것을 방지하기 위해 set 자료형을 활용했다. 제거할 좌표의 성분은 0으로 바꿔주고, 블록을 순회하여 0을 가장 위로 보냈다. # (2 x 2) -> 한번에 제거 -> 판별을 어떻게 할 것인지??? # 왼쪽 상위 좌표 [i, j] 기준 완전 탐색 # 제거된 후 블럭이 내려옴 -> 어떻게 처리 -> 열 별로 맵 탐색 -> 0 나오면 swap... def soluti..
2023.02.22 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 "출발 - 도착", "도착 - 출발" 모두 목적지와 시작점은 다르지만, 같은 길을 지난다. 이 점을 이용해서, 매번 방문 시 마다 "출발 - 도착", "도착 - 출발" 정보를 저장하는 방식을 통해, 처음 걸어본 길의 길이를 파악했다. 다루기 쉽게 시작점을 (5, 5)라고 생각하고 코드를 작성했다. # 이동 처리 def move(d, x, y): if d == "U": if x - 1 >= 0: x -= 1 elif d == "D": if x + 1
[Python] 프로그래머스 방문 길이 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 "출발 - 도착", "도착 - 출발" 모두 목적지와 시작점은 다르지만, 같은 길을 지난다. 이 점을 이용해서, 매번 방문 시 마다 "출발 - 도착", "도착 - 출발" 정보를 저장하는 방식을 통해, 처음 걸어본 길의 길이를 파악했다. 다루기 쉽게 시작점을 (5, 5)라고 생각하고 코드를 작성했다. # 이동 처리 def move(d, x, y): if d == "U": if x - 1 >= 0: x -= 1 elif d == "D": if x + 1
2023.02.21 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 모든 경우의 수를 완전 탐색할 경우, 대략 $4^{100,000}$ 정도의 연산이 필요해 시간 초과가 발생한다. 따라서 다른 방법을 활용해야하고, 나는 DP를 활용했다. 매번 새로운 열만 밟을 수 있기 때문에, 현재 K 번째 열을 밟았다면, 이전엔 [K - 1, K - 2, K - 3]의 열만 밟을 수 있다. 결국 N 행의 K 번째 열을 밟았을 때의, 최대 값을 DP 테이블에 저장하면 문제를 풀 수 있다. DP[n][k] = land[n][k] + max(DP[n - 1][k - 1] +..
[Python] 프로그래머스 땅따먹기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 모든 경우의 수를 완전 탐색할 경우, 대략 $4^{100,000}$ 정도의 연산이 필요해 시간 초과가 발생한다. 따라서 다른 방법을 활용해야하고, 나는 DP를 활용했다. 매번 새로운 열만 밟을 수 있기 때문에, 현재 K 번째 열을 밟았다면, 이전엔 [K - 1, K - 2, K - 3]의 열만 밟을 수 있다. 결국 N 행의 K 번째 열을 밟았을 때의, 최대 값을 DP 테이블에 저장하면 문제를 풀 수 있다. DP[n][k] = land[n][k] + max(DP[n - 1][k - 1] +..
2023.02.21 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 스킬 트리만 만족하면 되기 때문에, 관련 없는 다른 스킬들은 확인하지 않아도 된다. 스킬 트리에 포함되는 스킬만 추출해서, 스킬을 찍은 순서를 확인하고 이것이 스킬 트리와 동일한 지 확인하면 된다. # 선행 스킬? 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬 # 중복이 없으니까, 필요없는 문자열 제거하면 될듯! import re def solution(skill, skill_trees): # 가능한 스킬 트리 개수 cnt = 0 # 확인할 스킬 정보 : 스킬 트리만 만족하면 되기 때문..
[Python] 프로그래머스 스킬트리 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 스킬 트리만 만족하면 되기 때문에, 관련 없는 다른 스킬들은 확인하지 않아도 된다. 스킬 트리에 포함되는 스킬만 추출해서, 스킬을 찍은 순서를 확인하고 이것이 스킬 트리와 동일한 지 확인하면 된다. # 선행 스킬? 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬 # 중복이 없으니까, 필요없는 문자열 제거하면 될듯! import re def solution(skill, skill_trees): # 가능한 스킬 트리 개수 cnt = 0 # 확인할 스킬 정보 : 스킬 트리만 만족하면 되기 때문..
2023.02.20 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 10일 동안의 할인 품목이, 원하는 품목과 동일할 경우에만 멤버십에 가입한다. 할인 품목의 개수 정보를 얻기 위해서 Counter를 사용했다. # 10일 동안 회원 자격 # 회원 : 하루 1 개만 # 10일 연속 일치할 경우에 가입 ! from collections import Counter def solution(want, number, discount): best_day = 0 want_number = dict(zip(want, number)) # 언제 가입하면 좋을 지 확인 for ..
[Python] 프로그래머스 할인 행사 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 10일 동안의 할인 품목이, 원하는 품목과 동일할 경우에만 멤버십에 가입한다. 할인 품목의 개수 정보를 얻기 위해서 Counter를 사용했다. # 10일 동안 회원 자격 # 회원 : 하루 1 개만 # 10일 연속 일치할 경우에 가입 ! from collections import Counter def solution(want, number, discount): best_day = 0 want_number = dict(zip(want, number)) # 언제 가입하면 좋을 지 확인 for ..
2023.02.20 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 마지막에 설정한 이름에 따라 기존 메시지는 전부 바뀌게 된다. 반복문을 통해 uid와 마지막 이름 사이 Hash를 구성하고, 이후 f-string을 통해서 출력했다. $2 * O(N)$ 정도의 시간 복잡도를 가지기 때문에, 시간 초과 없이 처리할 수 있다. # 입장 : 닉네임이 들어옴 -> 퇴장 : 닉네임님이 나감 # 닉네임 변경 방법 : 채팅방 나간 후, 새로운 닉네임으로 다시 들어감 / 채팅방에서 닉네임 변경 # 변경 -> 기존 출력 메시지 닉넴도 변경 # 유저 구분 -> uid 활용..
[Python] 프로그래머스 오픈채팅방 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 마지막에 설정한 이름에 따라 기존 메시지는 전부 바뀌게 된다. 반복문을 통해 uid와 마지막 이름 사이 Hash를 구성하고, 이후 f-string을 통해서 출력했다. $2 * O(N)$ 정도의 시간 복잡도를 가지기 때문에, 시간 초과 없이 처리할 수 있다. # 입장 : 닉네임이 들어옴 -> 퇴장 : 닉네임님이 나감 # 닉네임 변경 방법 : 채팅방 나간 후, 새로운 닉네임으로 다시 들어감 / 채팅방에서 닉네임 변경 # 변경 -> 기존 출력 메시지 닉넴도 변경 # 유저 구분 -> uid 활용..
2023.02.19 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 들어온 차는 나가지 않으면 23 : 59에 나간 것으로 가정한다. 이 경우 들어오고, 나간 시간의 차이를 구하는 것은 23:59 분과 현재 시각 사이 차를 구하는 것과 동일해진다. OUT과 IN을 서로 다른 기호를 가지도록 더해주면 결국 주차장에 머무른 총 시간을 구할 수 있다. # 차량별 주차 요금 계산 # 00:00 ~ 23:59 까지 누적으로 처리 -> 요금 일괄 정산 # 다음날 출차는 고려 X # 요금 계산 시 '올림' 처리 # 차량 번호가 작은 자동차부터, 차례대로 return!..
[Python] 프로그래머스 주차 요금 계산 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 들어온 차는 나가지 않으면 23 : 59에 나간 것으로 가정한다. 이 경우 들어오고, 나간 시간의 차이를 구하는 것은 23:59 분과 현재 시각 사이 차를 구하는 것과 동일해진다. OUT과 IN을 서로 다른 기호를 가지도록 더해주면 결국 주차장에 머무른 총 시간을 구할 수 있다. # 차량별 주차 요금 계산 # 00:00 ~ 23:59 까지 누적으로 처리 -> 요금 일괄 정산 # 다음날 출차는 고려 X # 요금 계산 시 '올림' 처리 # 차량 번호가 작은 자동차부터, 차례대로 return!..
2023.02.17 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 숫자들을 미리 N 진법으로 변환한 뒤, 대답 여부는 1 글자 씩 읽어서 확인했다. 튜브가 대답할 순서는 나머지를 통해서 확인했다. # 10 이상 부터는, 한 자리씩 말하기! # 자신이 말해야할 번호만 출력하면 됨 # n 진법으로 변환하기 def get_nbase(n: int, i: int) -> str: nbase = "" over_10 = {10 : "A", 11 : "B", 12 : "C", 13 : "D", 14 : "E", 15 : "F"} while i: q, r = divmod..
[Python] 프로그래머스 [3차] n 진수 게임 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 숫자들을 미리 N 진법으로 변환한 뒤, 대답 여부는 1 글자 씩 읽어서 확인했다. 튜브가 대답할 순서는 나머지를 통해서 확인했다. # 10 이상 부터는, 한 자리씩 말하기! # 자신이 말해야할 번호만 출력하면 됨 # n 진법으로 변환하기 def get_nbase(n: int, i: int) -> str: nbase = "" over_10 = {10 : "A", 11 : "B", 12 : "C", 13 : "D", 14 : "E", 15 : "F"} while i: q, r = divmod..
2023.02.17