Algorithm Problem

[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] 백준 - 1931. 회의실 배정

🤔문제 해결 S2 | 정렬, 그리디 회의 시간이 긴 것과 상관 없이 회의가 끝나는 시각이 빠른것을 선택 회의가 끝나는 시각이 빠른 순으로 정렬 이전 회의가 끝난 시각과 비교하여 회의를 시작할 수 있으면 카운트 +1 없으면 통과 💨 끝나는 시각 뿐만 아니라 시작 시간도 두번 째로 정렬 해줘야 한다. 반례 [2,2], [1,2] 💨 sys.stdin.readline 과 input의 차이 (아래가 input()으로 받은 것) 💻소스 코드 import sys input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(key=lambda x: (x[1], x..

[python] 백준 - 1929. 소수 구하기

🤔문제 해결 S2 | 에라토스테네스의 체 소수: 1과 자기 자신 이외의 약수를 가지지 않는 1보다 큰 자연수 숫자 하나하나를 모두 for문을 돌려서 구할 수 있지만 비효율적임. 에라토스테네스의 체를 이용한다. 0부터 구하고자하는 값의 길이 만큼 0의 값을 가진 배열을 만든다. ex) dp = [0, 0, 0, 0, ..., 0] for문으로 2부터 배열의 끝까지 돌면서 자기 자신을 제외한 배수는 전부 1로 바꿔준다. 맨 위의 그림을 보면 이해하기 쉬움 배열에서 0인 녀석들을 print해준다. 💻소스 코드 def eratos(n): for j in range(n * 2, E + 1, n): dp[j] = 1 return S, E = map(int, input().split()) dp = [0] * (E +..

[python] 백준 - 1011. Fly me to the Alpha Centauri

🤔문제 해결 S1 | 수학 DFS로 구현해보려고 했으나 역시 시간초과로 실패했다. 알고리즘이 수학이다보니 역시 손으로 직접 패턴을 구해야 한다. 패턴을 보면 다음과 같다. 노란색으로 칠한 곳을 보면 뭔가 알 수 있다. . . . . 거리의 제곱근은 홀수 횟수가 끝나는 지점. 4: 2*2-1 = 3 9: 3*2-1 = 5 16: 4*2-1 = 7 25: 5*2-1 = 9 그렇다면 제곱근이 아닌 숫자는 어떻게 찾을까? 파란색을 보자. . . . . 거리의 제곱근만큼 다음 숫자가 있다. EX 예를 들어 거리가 7이다. 제곱근은: 2.xxxx 이므로 2이다. 2를 제곱하면 4 우리는 4부터 보면된다. 그렇다며 나머지는 거리 7에서 4를 빼면된다. 카운트는 2*2-1 이므로 3 제곱근은2, 시작은4, 나머지는3,..

[python] 프로그래머스 - 풍선 터트리기(월간 코드 챌린지 시즌1)

🤔문제 해결 Lv3 풍선이 살아남을 수 있는 조건: 내 풍선 기준 왼쪽 풍선 크기가 클 때 내 풍선 기준 오른쪽 풍선 크기가 클 때 만약 왼쪽과 오른쪽 둘다 크기가 작으면 풍선은 죽는다 이 문제에서 핵심은 풍선의 크기가 가장 작은 녀석들을 하나씩 뽑아주면 되는 것! 값을 기준으로 정렬을 해주면 크기가 가장 작은 풍선(5)은 무조건 살아남는다. - (모두 다 터트릴 수 있다) 크기가 두번째로 작은 풍선(6)도 무조건 살아남는다. - (자신보다 작은 풍선(5)을 터트릴 찬스가 1번 있기 때문) 크기가 세번째로 작은 풍선(7) 부터는 인덱스의 상황에 따라 결정된다. 만약 7이 앞의 두 풍선 사이에 있을 경우 자신의 양쪽이 모두 작기 때문에 풍선은 죽는다. 하지만 두 풍선 사이가 아니라면 ( 5 < 6 < 7 ..

[python] 백준 - 5014. 스타트링크

🤔문제 해결 G5 | BFS, 그래프 갈 수 있는 길이 2가지인 BFS 문제. 한 지점에서 올라가거나 내려가거나 하면서 원하는 층에 도착할 수 있는지 판별한다. 최초 시작점 S에서 올라가거나(U) 내려간다(D) 만약 올라갈 때 건물의 높이보다 높으면 못올라가고, 내려갈 때 1층보다 낮으면 못내려간다. 또 visited리스트를 만들어둬서 이미 방문했었는지 보고 방문을 안했던 층만 방문한다. BFS로 하기 때문에 이미 방문한 층에 한번 더 들르면 큰값이 들어가게 되므로 무조건 손해이다. 계속 방문을 하면서 원하는 지점(G)에 도착한다면 그 값을 리턴해주고, 도착하지 못한다면 'use the stairs' 를 리턴해준다. 💨 💻소스 코드 from collections import deque def bfs():..