반응형 프로그래밍85 백준 2512 : 예산 with 파이썬 / 이분탐색 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net # 포인트 1. 어려운 이진탐색은 단순히 값들과 mid값들을 비교하는 게 아니라, mid를 통해 구해진 값들을 이용해 비교해준다. 여기서는 2가지 비교가 이뤄졌는데 ⓐ 가상의 예산 상한선인 mid와 그 mid를 이용해 계산된 필요한 총 예산인 result ⓑ 가상의 총 예산인 result와 주어진 총 예산인 m 을 비교해주면 된다 2. result가 최대 예산인 m보다 적으면 상한선인 mid.. 2024. 2. 21. 백준 1463 : 1로 만들기 with 파이썬 / DP https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net # 포인트 1. if n==1: else : 로 처리해야 print()가 2번 나오지 않음 2. elif가 틀린 이유 : i%3==0이 false인 경우만 들어가기 때문에 6의 배수로 2를 나눌때 더 최솟값이 나오는 경우를 빠뜨릴 수 있기 때문에 ex) 642 ▶ 최소값이 나오는지 보장할수 없을 때는 다 해보고 min()으로 최소값 얻기 n=int(input()) if n==1: print(0) else: d=[0]*(n+1) for i in range(2, n+1): d[i]=d[i-1]+1 if i%3==0.. 2024. 2. 17. 백준 9095 : 1, 2, 3 더하기 / DP https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net DP : 이전값들을 저장해 빠르게 계산하는 방법 t=int(input()) for _ in range(t): n=int(input()) if n==1: print(1) elif n==2: print(2) elif n==3: print(4) else : d=[0]*(n+1) d[1]=1 d[2]=2 d[3]=4 for i in range(4,n+1): #n이 4보다 작으면 인덱스에러나므로, 위에서 예외처리 해줘야 d[i]=d[i-1]+d[i-2]+d[i-3] print(d[n]) 2024. 2. 16. [프로그래머스] 체육복 with 파이썬 / 복사 https://school.programmers.co.kr/learn/courses/30/lessons/42862 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 포인트 1. 반복문 동안 remove() 해야 하므로, 복사본을 만들어 그것을 보면서 remove() 2. lost를 기준으로 reseve에서 찾아 lost를 제거하면, [1,3], [2]와 같이 남은 여분이 잃어버린 학생 2명 모두를 지원해주는 경우가 생길수도 있기 때문에 reserve에서도 지워줘야 한다. def solution(n, lost, reserve): lost.sort() res.. 2024. 2. 16. [프로그래머스] 네트워크 with 파이썬 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. DFS : 재귀함수 # 포인트 - 재귀함수 dfs()로 연결된 점을 다 찾고나면 네트워크 수 추가 - 방문체크 : 방문체크를 하지 않는다면, 1-2 연결 찾을 후, 2-1에서 다시 1-2로 무한반복할 수 있기 때문에 방문체크해야 def solution(n, cs): def dfs(i): v[i]=1 for j in range(n): if not v[j] and cs[i][j]==1 : dfs.. 2024. 2. 15. 백준 2110 : 공유기 설치 with 파이썬 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net # 포인트 1. 그리디 : 최소구간이 최대가 되기 위해서는 공유기의 간격이 최대로 벌어져야 하므로 항상 첫번째 집에는 공유기가 설치되야 한다 2. 집의 좌표가 (0 ≤ x ≤ 1,000,000,000)이므로, 시간복잡도를 줄여주는 이분탐색을 사용 ⓐ탐색범위 : 최소거리(mid) ⓑ타겟 비교 : 설치할 공유기의 수(c)와 최소거리(mid)를 통해 .. 2024. 2. 13. 이전 1 2 3 4 ··· 15 다음 반응형