본문 바로가기

PS

[백준 16637번] 괄호 추가하기 (파이썬/python) 2021. 6. 19. https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 처음에 여러 시도를해봤다. + - * 사이의 우선순위를 내가 임의로 지정하면되지않을까? 싶었지만 불가능했다. 이 문제는 모든 경우를 완전탐색해서 답을 도출해야됐다. 내가 임의로 연산자 우선순위를 주고 싶지만 그럴경우 처리하지 못 하는 변수가 생긴다. 내가 푼 풀이법은 우선 사용할 연산자의 인덱스를 리스트 안에 넣어주고 그 리스트에 넣은대로 선 연산을 하고 그 후 선 연산한 상태의 숫자..
[프로그래머스 LV 3] 스티커 모으기 (파이썬/python) 2021. 6. 17. https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 재귀 돌려서 완전탐색으로 풀었는데 시간초과가 퍼퍼퍼퍼펑 터져버린다. LV3 부터는 더이상 잔재주가 통하지 않는다는걸 느꼈음.... 좀 더 효율적인 풀이법을 생각해보자 완전탐색으로 실패했고 dp로 견적이 나온다는 생각이 들었다. 바텀업으로 생각을 해보면 i번째 스티커를 뽑았을 경우 i-1번쨰는 뽑을 수 없고 i-2번째는 뽑거나 안 뽑거나 의 경우가..
[프로그래머스 LV 3] 야근 지수 (파이썬/python) 2021. 6. 17. https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr (맨 처음 풀이) n번의 반복문을 돌며 works 안에 있는 값 중에 가장 최대인 값에서 1씩 빼주는 식으로 만들었다. 그랬더니 테스트케이스는 잘 풀리는데 효율성 테스트에서 시간초과가 난다. 내가 짠 코드의 시간복잡도는 max( len(works) , n ) 이다. 이 뜻은 뭐냐.. 로직은 맞는데 효율적으로 풀지 못 했단 소리다 효율적으로 푸는 방..
[프로그래머스 LV 3] 멀리 뛰기 (파이썬/python) 2021. 6. 17. https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 처음에 완전탐색으로 풀었고 시간 초과가 났다. 더 효율적인 풀이법을 생각하다 메모이제이션을 통해 기존에 구한 값은 더 이상 계산하지 말고 바로 반환할 수 있게 동적계획법을 사용했다. 나는 탑다운으로 푸는게 편해 일단 탑다운으로 풀고 바텀업으로 같은 로직을 한번 더 작성해봤다. 탑다운은 뒤에서부터 결과값을 ..
[프로그래머스 LV 3] 최고의 집합 (파이썬/python) 2021. 6. 16. https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 계속 종이에 써보고 계속 숫자들 바꿔가며 사례를 찾아봤다. 일단 S // N 의 값을 최대한 많이 쓰는게 좋다. 몫은 S를 N개로 구성할 수 있는 가장 중간의 값이 되는데 주변으로 퍼지지 않고 가운데로 집중될수록 곱했을떄 값이 크다는걸 알았다. S//N을 N개만큼 리스트에 넣어주고 S%N 만큼 각각의 요소에 +1을 해주면 정답이 나온다...
[프로그래머스 LV 2] [1차] 프렌즈4블록 (파이썬/python) 2021. 6. 16. https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 일단 삭제 후 블록이 아래로 내려오는 방법을 구현하는데 애 먹었다. 원래 행렬을 오른쪽으로 90도 돌린 행렬을 사용했다. 리스트는 가운데 값이 사라지면 알아서 크기가 조정된다. 그렇기 때문에 전치행렬을 사용하면 삭제시 블록 재배치 되는 과정을 따로 구현해줄 필요가 없다. 하지만 배열의 크기가 유지돼야 반복문 구성이 수월하기 때문에 뒤에 "..
[백준 1300번] K번째 수 (파이썬/python) 2021. 6. 16. https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 와 어려웠다... 진짜어려웠다 어제 자기전에 침대에 누워서 이거 생각하다 잠 안와서 늦잠잤다 사실 풀고 나서도 와 이게 이분탐색으로 되네? 라고 느꼈음 이분탐색 문제를 거의 안 풀어보다 싶이 했다 보니 이분탐색 알고리즘을 떠올리는 로직이 아직 너무 불확실한듯... 이분탐색 문제를 두어문제 더 풀어봐야겠다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
[백준 12015번] 가장 긴 증가하는 부분 수열 2 (파이썬/python) 2021. 6. 16. https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS 문제는 종만북에서 보고 까먹을라 하니까 만나서 복습하는 좋은 기회가 됐다. DP를 사용하지만 거기에 추가로 탐색절차에 이진탐색(lower bound)를 추가한다. https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4 생각보다 나무위키에 정리가 잘 돼있다 ㅋㅋㅋ 저..
[백준 12865번] 평범한 배낭 (파이썬/python) 2021. 6. 16. https://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 https://suri78.tistory.com/2 [백준알고리즘] 12865번: 평범한 배낭 -Python [백준알고리즘] 12865번: 평범한 배낭 -Python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무..

티스토리툴바