문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 DFS를 활용한 풀이 : 시간 초과 문자 조합을 구성하기 위해서 DFS를 활용했다. 조합 구성 시, 순서를 유지하기 위해서 start 변수를 도입해 탐색 범위를 제한했다. 시간 초과가 발생했다. 풀이의 시간 복잡도는 ${n \choose k}$ 인데, n과 k가 최대 100만 까지 가능하기 때문이다. 더보기 DFS 함수의 시간 복잡도 T(dfs) = (n-k) choose (k-1) + (n-k+1) choose (k-1) + ... + n choose (k-1) = (n+1) choos..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 쿼드 압축은 매 시행 마다 압축이 가능한 지 확인하고, 불가능하다면 4개의 동일한 부분을 나눠서 다시 확인한다. 압축 시도 → 분할 후 압축 재 시도의 과정이 반복되기 때문에 재귀 함수를 활용할 수 있다. 압축의 형태를 비교하는 과정에서, 2차원 리스트 슬라이싱이 필요했다. 리스트를 2차원 슬라이싱 하려면, 다음과 같이 리스트 컴프리헨션을 사용하면된다. [row[j : j + n // 2] for row in arr[i : i + n // 2]] # (0의 개수, 1의 개수) # 재귀? ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 문자열을 구성하기 위한 방법으로는 순열, 백트래킹을 활용한 DFS가 있다. DFS 과정에서 각 종이(숫자)가 한 번만 활용돼야 하기 때문에 is_used 라는 변수를 활용했다. # 가능한 문자열 구성하기 def dfs(numbers, n_len, num): global cnt, is_used, num_uniq # 문자열 길이 최대일 경우 if n_len == len(numbers): return for i in range(len(numbers)): if not is_used[i]:..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 섹션이 이미 순서대로 정렬돼 있다. 그래서 앞에서부터(뒤에서부터) 차례로 칠하기만 해도 최소 덧칠 횟수가 만족된다. # N 개의 구역 (1 ~ N 라벨) # M 미터 -> 구역 초과 X # 반복해도 되지만, 최소화해야 함 # 끝에서 부터 확인하면 될 듯 -> 윈도우가 범위 안 넘어가면 색칠 # 순서 유지돼야 함 -> 윈도우 내 최소 값 보다 마지막 성분이 큰 경우 pop() def solution(n, m, section): cnt = 0 # 모든 영역을 다 칠할 때 까지 반복 while..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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): # 경..

문제 상황 코딩 테스트 문제를 풀다 보면, 다음과 같은 조건이 있을 때가 있다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 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 # 최종 값에만 나머지 연산을 적용할 경우 이럴 땐 연산 과정 중간 중간 나머지 ..

원인Python 3.8 이후 부터, 윈도우는 타 운영체제랑 다른 EventLoop를 기본 값으로 활용한다고 한다.타 OS 기본 : SelectorEventLoop윈도우 기본 : ProactorEventLoop 해결 방법아래 코드를 입력해, 윈도우의 EventLoop를 SelectorEventLoop로 변경하면 된다.asyncio.set_event_loop_policy(asyncio.WindowsSelectorEventLoopPolicy())주의 사항윈도우는 I/O Completion Ports를 활용해 비동기 처리 하기 때문에, SelectorEventLoop로 변경 시 아래와 같은 제약이 있다고 한다. 제약이 문제가 될 경우, Trio 라는 별도의 라이브러리를 사용하는 것이 좋다고 한다.Can't su..

사용 방법 git log --follow --patch 파일명 실행 결과 git log --follow 파일명 만 활용한 경우 파일 이름이 어떻게 변했는지 확인할 수가 없다. git log --follow 2_바이러스.py >> commit d2b40f8af3740a54298d2212a91e442ba84592df Author: ~ Date: Wed Feb 15 21:34:14 2023 +0900 [Rename] : solved, retry 폴더로 구분 commit e4929ce94ceae2f22d77f2a4ff0a21cff117691a Author: ~ Date: Tue May 17 16:52:44 2022 +0900 Add : 2_바이러스.py git log --follow --patch 파일명 을 활..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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..

사용 방법 Github의 주소의 일부분을 확인하고 싶은 시점의 commmit id로 변경한다. 변경은 blob/commit-id/파일명 형식으로 하면 된다. 기존 주소 : main 의 파일 확인 예시 : https://github.com/github/codeql/blob/main/README.md 주소 변경 : 이전 commit의 파일 확인 예시 : https://github.com/github/codeql/blob/b212af08a6cffbb434f3c8a2795a579e092792fd/README.md 원리? Git은 파일 변경 히스토리를 blob에 담고, 이를 Tree가 가리키는 방식으로 버전을 관리한다. 최종적으로 Tree를 사용자의 Commit이 가리키도록 하여 원하는 시점의 데이터를 확인할 수..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 파일명에서 HEAD, NUMBER, TAIL을 구분하기 위해서 GROUP을 활용했다. 필요 없는 0 제거하기 int(문자열)을 사용하면, 앞에 있는 필요 없는 "0"을 자동으로 제거해준다. str.lstrip("0")을 활용할 경우, 숫자 "0"도 제거돼 오류가 발생한다. GROUPS 해당 GROUP에 패턴을 찾지 못했다면, group[i] 빈칸을 가지고 있다. 찾지 못한 경우를 위해 예외처리를 하지 않아도 된다. # 파일명에 포함된 숫자를 반영한 정렬 기능 구현 # 숫자 : 0 ~ 99..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 제거할 (2 x 2) 박스를 찾기 위해서, 박스의 왼쪽 상위 좌표를 기준으로 완전 탐색했다. 박스 안에 제거할 좌표가 중복되는 것을 방지하기 위해 set 자료형을 활용했다. 제거할 좌표의 성분은 0으로 바꿔주고, 블록을 순회하여 0을 가장 위로 보냈다. # (2 x 2) -> 한번에 제거 -> 판별을 어떻게 할 것인지??? # 왼쪽 상위 좌표 [i, j] 기준 완전 탐색 # 제거된 후 블럭이 내려옴 -> 어떻게 처리 -> 열 별로 맵 탐색 -> 0 나오면 swap... def soluti..