코딩테스트

[python] 백준 - 16234. 인구 이동(삼성 SW 역량 테스트 기출 문제)

🤔문제 해결 G5 | 시뮬레이션, BFS 1. 연합을 찾는다. 현재위치와 인접한 위치의 값의 차이가 조건에 맞으면 연합리스트에 넣어줬다. (BFS) 2. 만약 연합이 없으면 끝 3. 연합이 있으면 연합 내에서 인구 이동을 한다. 연합의 모든 인구의 평균값으로 바꿔준다. 4. (1,2,3)을 반복한다. while문으로 2번이 나올때까지 돌린다. 💨 시간초과가 나서 pypy로 돌렸더니 통과!!! 파이썬은 항상 느려서 이젠 그러려니 한다. 아니면 뭔가 더 좋은 방법이 있는 것 같다. 찾아보니 인접리스트를 활용해서 하는 방법도 있지만.... 나중에 도전해보겠다. 💻소스 코드 from _collections import deque def move_population(union_list): for union in ..

[python] 프로그래머스 - 3 x n 타일링

🤔문제 해결 Lv4 | dp 2 x n 타일링 문제와 마찬가지로 dp 문제. 완전 탐색으로 초반 몇 가지 경우의 수를 구한다.(손이나 코드로...) 몇 가지 경우의 수를 가지고 점화식을 세운다. 나는 1번 부분을 하다가 수가 너무 커져 시간이 오래걸릴까봐... 다른데서 가져왔다 나같은 사람을 위해 이제 위의 경우의 수를 가지고 식을 세우면 된다. 규칙성은 무조건 있다 💨 💻소스 코드 def solution(n): answer = 0 dp = [0] * (n + 1) dp[0] = 1 # 아무것도 두지 않는 경우도 1가지 sub = 0 for i in range(2, n + 1, 2): dp[i] = dp[i - 2] * 3 + sub * 2 sub += dp[i - 2] answer = dp[n] % 1..

[python] 프로그래머스 - 지형 편집

🤔문제 해결 Lv4 | 이분탐색 or 완전탐색(?) 이분탐색으로 코드를 구현했더니 효율성에서 실패했다. 그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다. 먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. [[4, 4, 3], [3, 2, 2], [2, 1, 0]] ➡ [0, 1, 2, 2, 2, 3, 3, 4, 4] 다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다. 지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용) 빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다. 값은 21칸 * Q(지우는 값) = 63 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

[python] 프로그래머스 - 숫자 블록

🤔문제 해결 Lv4 구간(begin ~ end)이 정해져 있으므로 전부를 구할 필요는 없다. 선택한 구간만 잘라서 여기에 어떤 숫자가 들어가야 할지를 알아보자. 규칙을 잘 살펴보면 I 의 약수 중( 1 제외) 가장 작은 수로 나눈 몫이 해당 인덱스의 값이 된다. 10을 보면 2,5,10 중 2로 나누면 값은 5이다. 9의 경우 3,9 중 3으로 나누면 값은 3이다. 7의 경우 소수이므로 7로 나누면 값은 1이다. 위의 방법으로 코드를 짜면 정확도 테스트는 아주 쉽게 통과한다. 💡중요 이제 효율성 테스트가 문제인데 시간초과도 아니고 실패 라고 한다.이유는 전체 도로의 길이는 10^9 이지만 블록의 숫자는 10^7 까지이다.몫이 10^7을 넘어가게 된다면 사실상 해당블록은 존재하지 않는다!!그러므로 몫이 1..

[python] 프로그래머스 - 단어 퍼즐(2017 팁스타운)

🤔문제 해결 Lv4 | 다이나믹 프로그래밍 풀이 방법은 앞에서 부터 문자 하나하나 선택한다. 'b', 'a', 'n', ... 그 문자로 끝나는 단어가 strs에 들어있는지 확인한다. 있으면 현재까지 썼던 단어 개수(dp[i])와 그 문자를 사용했을 때의 단어 개수를 비교해서 최솟값으로 갱신 (말이 너무 어렵다...) ["ba", "na", "n", "a"] 와 "banana"로 테스트 해보면 맨처음 "b"로 끝나는 단어는 없으므로 pass 다음 "a"로 끝나는 단어는 "a"와 "ba"가 있다. - "na"는 조건에 맞지 않음 "a"를 선택했을 때는 아무일도 없다. why? 처음에 b로 끝나는 단어가 없어서 값이 무한대인 상태 "ba"를 선택하면 1로 갱신해준다. - (단어 하나만으로 "ba"를 만들었다..

[python] 프로그래머스 - 징검다리

🤔문제 해결 Lv4 | 이분 탐색 딱 보자마자 이분탐색인지는 모르겠다. 하지만 문제 카테고리에 써있다. 이분탐색을 하려면 어떤 값을 왔다 갔다 이분탐색할지 정해야 한다. 여기서는 답으로 구해야 하는 최댓값을 이분탐색 했다. 먼저 답을 정해놓고 시작한다. 0과 마지막 지점인 distance(25)를 가지고 가운데 값으로 12로 정했다. 이 문제에 답이 12라면 바위를 n개 제거했을 때 최소 거리가 12인 녀석이 있어야 한다. 처음 위치를 0으로 두고 다음 바위까지의 거리가 mid(12) 보다 작으면 제거 아니면 그 바위로 이동 0 에서 2 까지의 거리 2 12: 살려둠 and 14로 이동 14 에서 17 ..