Devlog_by_0giru

https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 문제 설명은 무진장 긴데 실상은 별거 없던 문제 for loop로 각 progress에 speed를 더해주면서 100보다 큰 0번째 인덱스가 생기면 카운트를 증가시키고 배열에서 삭제해 주는 방식으로 풀었다. def solution(progresses, speeds): count = 0 answer = [] while progresses: for i in ..

https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 따로 어려웠던 내용이 없는 간단한 문제였다. 노란색은 항상 중앙에 모여있으므로 n개가 주어질 때 약수 쌍을 구분하는 것이 포인트다. ex) 노란색이 24개 일 때, 가로 세로가 1줄-24줄 or, 2줄-12줄 or 3줄-8줄 ... 등등 해당하는 약수 쌍이 나왔을 때, 큰 값 - 작은 값 순으로 정렬해서 리턴해주었다. def getBrown(col, row)..

programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr DFS/BFS 분류로 되어있지만 문제를 풀 때에는 어떻게 풀어야 할지 참 난감했던 문제다. 각 숫자 앞에 -, + 두 가지의 연산자가 올 수 있어 시간복잡도는 최악의 경우 O(2^n)이 나오는데, 입력의 수가 최대 20개였기 때문에 그냥 완전탐색으로 시도해 해결했다. from itertools import combinati..

programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 순열을 활용해볼 수 있었던 문제였다. 처음에는 문제를 잘못 이해해서 중복순열을 사용했다가, 문제를 다시 읽어보니 사용한 카드를 다시 사용할 수 없어 순열을 이용해 해결할 수 있었다. 소수를 판별하는 로직을 기억해두는 것이 좋을 것 같다. from itertools import permutations def Prime(toTest): if toTest == 0 o..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 어떻게 풀지 어떻게 풀지 이게 왜 실버문젤까 하면서 꽤 오래 고민했던 문제다. BFS문제는 격자 혹은 좌표형태의 문제만 풀어봐서 그런지 어떻게 BFS로 푼다는 말인가 오랫동안 이해가 안갔었지만 큐를 이용해 갈 좌표들을 하나 씩 점검해주는 방식으로 푸니 이게 결국 BFS였다. 문제의 TC로 나온 예를 이용해 설명해보면, 처음에는 위와 같은 형태의 계층 구조가 있고 빈 큐를 이용한다. 우리는 3과 ..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2차원 다이나믹 프로그래밍을 활용하는 대표적인 문제다. 원래는 '안녕_1535' 문제를 풀기 위해 먼저 풀어본 문제인데, 백트래킹을 이용한 재귀함수 호출로 풀려고 시도해봤지만 시간 초과로 통과하지 못했다. pypy3로도 안되더라. 처음 내가 시도했던 방법을 그림으로 그렸다. 물건이 A B C D 네 가지가 있다고 가정한 후 각 물건을 넣느냐, 마..

www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N( result: result = cur_joy return # 현재 사람을 선택할 경우 Recursion(idx+1, cur_joy+joys[idx], cur_life-costs[idx]) # 현재 사람을 선택하지 않을 경우 Recursion(idx+1, cur_joy, cur_life) Recursion(0, 0, life) print(result) 2차원 다이나믹 프로그래밍을 이용한 풀이 (체력을 깎아가는 방식이 아닌 0에서 채우는 방식으로 풀었다.) """ 2차원 DP를 이용한 풀이 """ n = int(input()) costs = [0] joys = [0] cost = list(map(int, inpu..

완전 이진 트리, 힙 힙은 우선순위 큐를 위해 사용하는 자료구조이다. 완전 이진 트리 형태를 가진다. 우선순위 큐로 사용하기 위해 만들어지는 자료구조이기 때문에, 트리의 값 중 최댓값 혹은 최솟값을 구하기 위해서 사용한다. 힙은 루트로 갈수록 큰 값을 가지는 경우(루트가 트리의 최댓값을 가지는 경우)와 루트로 갈수록 작은 값을 가지는 경우(루트가 트리의 최솟값을 가지는 경우)로 나눌 수 있는데, 전자를 Max Heap, 후자를 Min Heap이라고 한다. 이 글에서는 Min Heap을 기준으로 설명하겠다. Max Heap의 경우에는 단순히 작은 값을 찾는 것을 큰 값을 찾는 방식으로 거꾸로 진행한다고 생각하면 된다. Min Heap은 부모의 노드 값이 항상 자식의 노드 값보다 작기만 하면 된다. 즉, 하..