문제 링크: https://school.programmers.co.kr/learn/courses/18/lessons/1878?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파이썬 zip() 함수 동일 개수로 이루어진 자료형을 묶어 주는 함수 반환값: 두 개 이상의 리스트의 값의 같은 인덱스 짝별로 묶어 튜플에 담아 반환해준다. 만약 짝이 안맞다면 짝이 맞는 부분만 return 된다. zip(*zip) 하게 되면 zipped 한 요소들을 unzip해준다. 문제풀이 from collections import Counter def..
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 배경지식 그래프(graphs)란 자료구조 정점(vertex, node)과 간선(edge, link) 유향(directed) 그래프와 무향(undirected) 그래프 스택(stack) 큐(queue) 깊이 우선 탐색(DFS; Depth First Search) 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점..
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 해결 방법 빈 문자열로 수를 초기화한다. 가장 크게 만들 수 있는 수를 고른다. 그 수를 현재 수에 이어 붙인다. 모든 수를 다 사용할 때까지 반복한다. (조금 나은) 문제의 해결 방법 빈 문자열로 수를 초기화한다. 수의 목록을(크게 만드는 것 우선으로) 정렬한다. 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다. 모든 수를 다 사용할 때까지 반복한다. 알고리즘 설계 -> 구현 ..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한 조건이 중요하다 보면 n의 수가 100000인데 이런 경우 보통 $O(n)$ 이나 $O(n\log n)$의 복잡도로 풀어야 한다.(파이썬은 1초에 대략 20000000만번의 연산 수행 이를 참고해 계산해 보면 편함) 자료구조(와 알고리즘) 의 선택 만약 이름 대신 번호가 주어졌다면? -> 선형 배열(linear array) 이름의 경우의수가 많아질 수 있으므로 적합하지 않음 📌..
문제 풀이) 문제에서 제시하는 풀이과정을 이해하는데 시간이 걸렸던 문제였다. 문자열을 분해하는 단계를 가만히 읽어보면 특정 과정을 반복하고 문자열을 또개 또 같은 과정을 반복하다 조건을 만족하지 못하면 종료하란 상황. 재귀적으로 시도해보겠다고 결정. 문제에서 말하는 과정은 다음과 같다. 첫번째 입출력 예의 경우 문자열을 'banana'다 첫번째로 x는 'b'가 되고 나머지 문자열은 'anana'가 된다. 이때 b의 갯수는 1개 이고 anana를 왼쪽에서 오른쪽으로 읽을때 첫번째로 b가 아닌 a의 갯수가 1개 이므로 ba를 분리하고 나머지 nana를 가지고 위의 과정을 되풀이합니다. 이번엔 n이 시작문자 이므로 n 1개 그 다음 ana를 왼쪽에서 오른쪽으로 읽어나가며 n인 경우와 n이 아닌 경우 각각 co..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 이 문제는 특별한 문제 풀이 방법이 있다기보다 반성하자는 의미에서 기록으로 남겨둔다. 문제에서 보면 굵은 글씨로 이렇게 적혀있다. 뭐 물론 굵긴 하지만 문제가 워낙 길어서 필요하다고 생각하는 내용들만 슥슥 보고 넘겼다가 괜히 달수를 더하려고 datetime 라이브러리를 가지고 머리를 싸메고 있었다.😐 전에도 카카오 기출을 풀면서 느낀건데 이런 문제가 종종 출제 되는것 ..
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/136798 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 이 문제에서 핵심은 각 기사단원의 약수의 시간복잡도를 어떻게 해결할 것인가였다. 일반적인 약수 구하기 방식을 구현하면 시간복잡도 O(N^2)이 된다. cnt = 0 for i in range(num+1): if num % i == 0: cnt += 1 이런식으로 구현하게 되면 만약 위에서 기사의 수 최대 범위인 100000이 되었을때 100000^2이 되어 제한시간을 초..
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17681 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 나는 십진법으로 된 숫자를 이진법으로 변환후 하나씩 비교를 하면서 맞으면 # 틀리면 ' '공백을 추가하도록 했지만 다른사람의 풀이를 보니 비트 OR 연산으로 한번에 끝낼수 있는 간단한 문제였다. 다음번엔 비트연산자 써서 풀어보기! def solution(n, arr1, arr2): def decode_query(num): temp = bin(num) binary = tem..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/67256 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 시뮬레이션 문제였던것 같다. 초반에 키패드를 저장할 자료구조를 잘 선택했다면 쉽게 해결할 수 있었을 것이나 단순히 left, mid, right 배열의 인덱스 값으로 문제를 처리하려고 해서 코드가 많이 지져분해졋다. def solution(numbers, hand): answer = '' left, right = 3, 3 keypad = {'l': [1, 4, 7], '..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) BFS를 이용해 해결할 수 있다. 발상을 뒤집어서 destination을 출발지점으로 선택해 역으로 탐색하면서 부대가 위치하 지점까지 도달할 수 있는지를 탐색하면 된다. 도달할 수 없는 경우도 있으므로 visit list를 -1로 초기화 시킨다. 이후 BFS를 수행하면 된다. from collections import deque def solution(n, roads,..
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/134239 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 특정 알고리즘이 필요한 문제는 아니었다. 말이 정적분이지만 사실은 사다리꼴의 넓이를 구하는 공식만 아는 정도면 해결할 수 있었던 문제 사다리꼴의 넓이 = (윗변 + 아랫변) x 높이 / 2 .... 근데 뭐든 국어가 문제인것 같다. 문제에서 말하는 오프셋의 의미를 정확히 파악하면 바로 해결할 수 있는 문제였다. 문제에 써있다. 그래프가 끝나는 점으로부터의 오프셋 즉 우박..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/142085 문제 풀이) heap을 이용해 풀수 있었다. 문제 풀이 과정은 다음과 같다. enenmy list의 원소들을 순서대로 탐색하며 다음과 같은 절차를 밟는다. 1) n(내가 보유하고 있는 병사수)가 enenmy[i](i번째 스테이지 적의 수) 수보다 많다면 내가 보유하고 있는 병사수에서 빼준다. 이러면 특정 스테이지에서 무조건 막히게 되있는데 이때 최대힙을 이용한다. 최대힙에서 heappop()을 하게 되면 내가 지나온 스테이지중 가장 많은 적의 수가 나오게 되있다. 힙에는 내가 스테이지를 클리어하며 소모된 병사의 수(=enemy수)가 저장되어 있다고 가정한다. 2) 이때 부터 ..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 다이나믹프로그래밍의 바텀업 방식을 이용해 풀었다. x, y가 100,0000 범위의 문제라 단순 구현으로 풀었어도 해결했을거라 생각했었지만 자연스럽게 DP로 풀어야 된다는 느낌을 받았다. 맨처음 직관적으로 떠오른 점화식은 다음과 같았다, x를 x를 구하기 위한 최소 연산 횟수라고 가정하면 이전항과 다음항들의 관계는 다음과 같을 것이다, DP[x] = min(DP[x -..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 스택의 LIFO(Last In First Out) 성질을 이용하여 해결할 수 있는 문제다. 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 뒷큰수가 됩니다. 스택에 저장하는것은 수가 아닌 그 수의 인덱스를 저장한다는게 이 문제풀이의 핵심이었던것 같다. 아래 그림을 보면 문제 푸는 과정을 이해할 수 있다. 문제에서 예시에서 numbers = [2, 3,..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) DFS를 이용해 문제를 풀었다. 해당 map에서 방문하지 않고 갈수있는 섬이면 방문 처리를 한후 스택에 할당 이후 재귀적으로 주변 섬들을 탐색해 만약 연결되어 있다면 식량들을 전부 합해 return해주도록 DFS 함수를 구현했다. def dfs(i, j, visited): if 0
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이) 시간을 분으로 바꿔 생각하는게 핵심인 문제였던 것 같다. [입실 시간, 퇴실 시간] HH:MM 포맷으로 적혀있는 시간을 분으로 환산하면 문제가 생각보다 간단해진다. 시간을 분으로 환산하기 위해 다음과 같은 함수를 구현했다. def convert_minute(start, end): start = int(start[:2]) * 60 + int(start[-2:]) end ..
문제 링크 : https://www.acmicpc.net/problem/1256 1) 문제 해결 a 가 n개 z가 m개 있다면 이 두개를 나열하는 순열의 개수를 생각해보면 이다. 근데 이 식을 다시 한번 생각해보면 M = (N + M) - N, N = (N +M) - M이므로, 실제 위 식은 n+mCn 이나 n+mCm 과 동일하다. 그런데 사전은 a부터 나오므로 a 부터 배치한다고 가정하면 남은 z의 개수를 이용해 점화식을 세우는 편이 더 편하다. 먼저 dp 테이블을 만들어 조합식에 관한 테이블을 미리 생성한다. 조합 테이블을 구하는 점화식은 다음과 같다. 위의 식에서 i, j 를 각각 i개에서 j개를 선택하는 경우의 수라고 생각을 해보자. 만약 데이터가 n개가 있다고 가정했을때 마지막 데이터 전까지 데..
