Algorithm

[프로그래머스] 성격 유형 검사하기 - 파이썬

2022 KAKAO TECH INTERNSHIP - 118666. 성격 유형 검사하기 [Lv. 1] https://school.programmers.co.kr/learn/courses/30/lessons/118666 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제에서 요구하는 대로 구현하면 되는 간단한 문제. score = {i:0 for i in ["R", "T", "C", "F", "J", "M", "A", "N"]} def scoring(survey, choice): if choice == 4: return elif choice > 4: s..

[백준] 13904. 과제 - 파이썬

[Gold III] https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 Greedy와 Priority Queue를 적절히 이용해 풀 수 있었던 문제. 입력된 과제를 점수(value) 순으로 정렬하고, 점수가 높은 것부터 Greedy하게 몇일차에 풀 지 배치. 7 4 60 4 40 1 20 2 50 3 30 4 10 6 5 와 같은 예제 입력에서는, 점수 순으로 정렬했을 때 아래와 같아진다. 4 60 2 50 4 40 3 30 1 20 4 10 6 5 맨 위(점수가 가장 높은것)부터 하나..

[백준] 2295. 세 수의 합 - 파이썬

[Gold IV] https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 일단 초견에서 생각한 것은 - x, y, z를 pointer로, two pointer처럼 풀이하면 되려나? 집합을 Set이나 List로 저장한다면, 세 수의 합이 집합에 포함되는 지 확인하는 Time Complexity가 O(N)이고, 포함 여부 확인은 반복문 안에서 계속해서 하게 될 텐데. => Hashing이 가능한 Dic..

[백준] 14939. 불 끄기 - 파이썬

[Platinum V] https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 백조의 호수 이후로 오랜만에 풀어보는 플래티넘 문제. ^ㅁ^ 풀이 우선, 10x10 배열 - 100칸이기에, 너무 무모한 Brute-Forcing만 아니면, TLE는 나오지 않겠거니 하고 생각했다. 처음 보자마자 떠올린 것은, 한 번 누른 칸은 다시 누를 일이 없지 않을까? 라는 것. 한 번 눌린 칸을 다시 누르게 되면, 5칸이 결국 누르기 전의 상태와 같아지는 ..

[백준] 2342. Dance Dance Revolution - 파이썬

[Gold III] https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 1 DP 문제라는 것은.. 보자마자 알겠음. [백준] 2281. 데스노트 가 생각이 나, 비슷한 방식으로, Top-Down 방식으로 풀려고 시도했으나.. line 12~13 부분에서 2의 제곱 형식으로 recursion이 계속 생길 거라.. 당연히 MLE나 TLE가 날 것이라고 예상했음. TLE. import sys sys.setrecur..

[백준] 1644. 소수의 연속합 - 파이썬

[Gold III] https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 1 보자마자, Prefix Sum 문제라고 생각했다. 먼저 에라토스테네스의 체를 이용해 입력값인 N까지의 수 중 소수를 구하고, 그 소수들의 리스트를 이용해 prefix sum 리스트를 만든 후, Two Pointer 기법을 이용해 부분합의 값이 N과 동일한 지 확인하는 방법. 시간은 충분했으나, MLE. (Memory Limit Exceed.) N = int(input()) nums = {i: 0 for i in range(2, N+1)} # 에라토스테네스의 체 for i in nums: ..

[백준] 1043. 거짓말 - 파이썬

[백준] 1043. 거짓말 - 파이썬 [Gold IV] https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제.. 풀고 보니 Union-Find(Disjoint Set)을 이용해 풀 수 있는 문제였다. 근데 그냥 Set 이용해서 풀린 문제.. ^ㅁ^ 최대 수가 50이라 TLE가 날 일이 별로 없었기에 가능하지 않았나 싶다. 아마 Set의 intersection()과 union()을 이용해서 시간 단축이 좀 된 것 같다. Union-Find를 이용한 풀이..

[백준] 2143. 두 배열의 합 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 부 배열의 합.. -> Prefix Sum! 우선 prefix sum을 구현하기 위해.. Sk (1~k번째 합)를 저장할 배열을 각각 생성. 그 다음이 문제인데... 우선 배열의 원소 조건이 절댓값이 1,000,000을 넘지 않는 정수 이기 때문에.. A[k+1] >= A[k] 가 아니다. 따..