프로그래머스 탐욕법(Greedy) - 체육복, 문제 확인 1차원적으로 문제를 이해해서는 테스트케이스 중 여러 문제를 통과할 수 없다. 테스트케이스를 알 수 없어 대체 뭐가 문제인지 난항에 빠졌었는데 '질문하기'를 이것저것 찾아보다가 겨우 해결할 수 있었다. 실전에서는 스스로 모든 예외를 생각해봐야 할텐데 아직 그런 스킬이 많이 부족한 것 같다. 문제 설명은 아래와 같다. 일부 학생의 체육복이 도난당함 여벌 체육복이 있는 학생이 체육복을 빌려줄 수 있음 하로 앞번호 학생이나 뒷번호 학생에게만 체육복을 빌려줄 수 있음 최대한 많은 학생이 체육수업을 들을 수 있게 해야 함 여벌 체육복을 가져온 학생이 체육복을 도난당했을 경우 하나만 도난당했다고 가정, 다른 학생에게 빌려줄 수 없음 n: 전체 학생 수 lost..
프로그래머스 완전탐색 - 소수찾기, 문제 확인 숫자 조합에 관한 모든 케이스를 구한 후, 그 중 소수가 몇개인지 찾는 문제이다. numbers는 길이 1 이상 7 이하인 문자열 numbers는 0~9까지 숫자만으로 이루어져 있음 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지, 개수를 리턴 프로그래머스 완전탐색 - 소수찾기, 문제 풀이 (파이썬) 모든 수의 조합을 찾는 것은 itertools의 permutations를 임포트하여 구하였다. "17"의 경우 길이가 1인 경우의 조합과 2인 경우의 조합을 전부 구해야 하기 때문에 1부터 numbers 길이까지 반복문을 돌면서 모든 조합을 구해 num_case에 추가해주었다. 그리고 nu..
프로그래머스 완전탐색 - 모의고사, 문제 확인 정렬 문제를 끝내고 이제 완전탐색 문제이다. 아래와 같이 답을 찍는 1,2,3번의 수포자가 있을 때 누가 제일 답을 많이 맞췄는지 리스트로 리턴하면 된다. 만약 답을 맞춘 수가 5,5,5 라면 [1,2,3]을 리턴하면 된다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 프로그래머스 완전탐색 - 모의고사, 문제 풀이 (파이썬) 문제 수가 최대 10000개라고 해..
프로그래머스 정렬 - H-Index, 문제 확인 처음 읽었을 때는 쉽다고 생각했는데 풀면 풀수록 문제가 난해했다. 처음부터 확실히 이해하고 넘어가면 금방 풀수 있는데 제대로 이해한 줄 알았던게 완전 아니었어서 삽질을 좀 했다. "어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면, h의 최댓값이 H-Index가 됨" 즉, [3,0,6,1,5] 에서 3회 이상 인용된 논문은 3,5,6 으로 3편 이상이고 나머지 논문 0,1이 3회 이하 인용되었기 때문에 리턴값은 3이 된다. 처음엔 3회 이상 인용된 논문이 3편이고 3회 이하 인용된 논문이 3편이기 때문에 3인 것으로 착각했다. 따라서 [22,42]의 경우 2번 이상 인용된 논문은 22,42로 ..
처음 문제를 읽을 때에는 쉬워보이는데 막상 풀어보면 이것저것 예외도 많고 어떤 방식을 써야할지 난감해 생각보다 어려웠다. 정렬 - 가장 큰 수, 문제 확인 문제 자체는 간단한데 양의 정수가 담긴 배열 numbers가 주어질 때, 가장 큰 수의 조합을 구하는 문제이다. 0 또는 양의 정수가 담긴 배열 numbers가 주어짐 순서를 재배치해 만들 수 있는 가장 큰 수를 문자열로 바꾸어 리턴 정렬 - 가장 큰 수, 문제 풀이 처음에는 별생각 안하고 자리수를 0으로 채워 맞춘 후에 큰 수대로 정렬, 하나씩 붙이면 된다고 생각했다. 그 중에 3, 30과 같이 같은 크기가 되는 경우는 실제 수 3, 30을 비교하는 방식으로 예외처리를 하는 방식으로 했다. 그런데 이렇게 하니 주어진 테스트케이스는 통과했지만 코드 채..
정렬 - K번째수, 문제 확인 이번 문제는 정말 간단하다. 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때 k번째있는 수를 구해야 함 배열 array와 [i,j,k]를 원소로 갖는 2차원 배열 commands가 주어짐 정렬 - K번째수, 문제 풀이 commands를 기준으로 반복문을 돌면서 먼저 array를 tmp에 복사한다. 그리고 i(v[0]), j(v[1])대로 tmp를 자른 후 정렬하고 k번째(v[2]-1) 값을 answer 리스트에 추가해주면 된다. def solution(array, commands): answer=[] for v in commands: tmp=array tmp=tmp[v[0]-1:v[1]] tmp.sort() answer.append(tmp[v[2]-1]..
힙(Heap) - 라면공장, 문제확인 개인적으로 우선순위 큐를 어떻게 활용해야 하는지 전혀 감이 잡히지 않아 헤맸던 문제이다. 일단, 문제 설명은 아래와 같다. 라면 공장은 하루에 밀가루 1톤 사용 k일 이후에 밀가루 공급 가능, 해외 공장에서 수입해야 함 해외 공장에서는 밀가루 공급이 가능한 날짜와 수량을 알려줌 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고자 함 현재 공장에 남아있는 밀가루 수량 : stock 밀가루 공급 일정 :dates (dates[i] " i번째 공급 가능일) 해당 시점에 공급 가능한 밀가루 수량 : supplies (supplies[i] : dates[i] 날짜에 공급 가능한 밀가루 수량) 원래 공장으로부터 공급받을 수 있는 시점 : k 밀가루가 떨어지..
힙(Heap) 자료구조에 대해 자료구조에서 힙(Heap)은 최대힙과 최소힙이 있는데 최대힙의 경우 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같은 값을 갖는 이진 트리를 말한다. 이런 힙을 배열을 통해 표현하게 되는데 힙 배열에서의 부모 노드와 자식 노드의 관계는 부모의 인덱스를 x라고 했을 때, 왼쪽 자식의 인덱스는 x*2, 오른쪽 자식의 인덱스는 (x*2)+1이 된다. 그리고 이러한 힙의 특징을 사용하면 우선순위 큐를 구현할 수 있게 되는데, 스택이 제일 마지막에 들어온 값을 먼저 꺼내는 자료구조고 큐가 제일 먼저 들어온 값을 꺼내는 자료구조라면 우선순위 큐는 가장 우선순위가 높은 값이 먼저 꺼내지는 자료구조이다. 즉, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조라고 ..
프로그래머스 스택/큐 마지막 문제인 주식가격문제를 풀어보도록 한다. 스택/큐 - 주식가격, 문제확인 문제 설명은 아래와 같다. 초 단위로 기록된 주식가격이 담긴 배열 prices가 변수로 주어짐 가격이 떨어지지 않은 기간이 몇초인지를 리턴 요번 문제 설명은 심플한 편이다. 예를 들어 [1,2,3,2,3] prices 배열이 주어졌을 때, 리턴값이 [4,3,1,1,0]이 되는 과정은 아래와 같다. 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았..
스택/큐 - 쇠막대기, 문제 확인 처음보는 신기한 유형의 문제이다. 문제 설명은 아래와 같다. 쇠막대기를 아래에서 위로 겹쳐놓고 레이저를 위에서 수직으로 발사해 쇠막대기를 자르려 함 짧은 쇠막대기가 긴 쇠막대기 위에 오도록 배치 각 쇠막대기를 자르는 레이저는 적어도 하나 존재 레이저는 어떤 쇠막대기의 양끝점과도 겹치지 않음 레이저는 ()로 표현함 쇠막대기의 왼쪽 끝은 (로, 오른쪽 끝은 )로 표현 쇠막대기, 레이저의 배치를 표현한 문자열 arrangement가 주어질 때, 잘린 쇠막대기 조각의 총 개수를 return 스택/큐 - 쇠막대기, 문제 풀이 먼저 레이저 ()를 전부 *값으로 변경해주었다. def solution(arrangement): answer = 0 arrangement = arrangem..
스택/큐 - 프린터, 문제 확인 문제 설명은 아래와 같다. 대기목록의 가장 앞에 있는 문서의 중요도보다 높은 문서가 있다면, 해당 문서를 대기목록의 맨뒤로 보냄 없다면, 인쇄함 priorities : 대기목록에 있는 문서의 중요도가 담긴 배열 lcoation: 인쇄를 요청한 문서가 대기목록의 어떤 위치에 있는지 내가 요청한 문서가 몇 번째로 인쇄되는지 return 예를 보면, [2,1,3,2]의 경우 아래의 순서대로 인쇄가 진행되고 lcoation이 2인 경우, 3을 의미하므로 가장 첫번째로 뽑히는 것을 알 수 있다. 따라서 return 값은 1이다. 초기) priorities=[2,1,3,2] 1) priorities=[1,3,2,2] 2) priorities=[3,2,2,1] 3) priorities..
프로그래머스 스택/큐 - 기능개발, 문제 확인 문제 설명은 아래와 같다. 각 기능은 진도가 100%일 때, 서비스에 반영할 수 있음 각 기능의 개발속도는 모두 다름 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발되면, 앞에 있는 기능이 배포될 때 함께 배포됨 progress : 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 speeds : 각 작업의 개발 속도가 적힌 정수 배열 배포는 하루에 한번 할 수 있음 예를 들어 진도율이 95%인 작업의 개발속도가 4%라면 배포는 2일 뒤에 이루어짐 각 배포마다 몇개의 기능이 배포되는지를 리턴 문제 설명만 봐서는 잘 이해가 가지 않으니 예시를 함께 보자. 첫 기능의 경우 93% 완료되어있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 된다..
