728x90 TIL - 프로그래밍/Python 알고리즘198 [백준] 2580. 스도쿠 - Python https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 생각 스도쿠 풀어야 하는 부분 체크!! 하나하나 해결해보기 그 위치에 들어갈 수 없는 숫자 체크 가로, 세로, 3*3 확인 들어갈 수 있는 숫자를 for문 돌려서 재귀로 해보기 숫자를 넣었더니 더이상 스도쿠를 풀 수 없으면 되돌리기 스도쿠를 다 풀었으면 출력하기 코드 from sys import stdin def lookForNumList(r,c): nums = [0] * 10 # 이 위치에 들어.. 2022. 6. 28. [백준] 15638. 감시 - Python https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 생각 카메라 위치와 카메라 번호 체크!! CCTV 감시해야 할 구역 수 구하기 사각지대 = CCTV 감시해야 할 구역 수 - CCTV 감시 구역 수 각 카메라 번호가 감시할 수 있는 방향! 1,3,4 : 4가지 2 : 2가지 5 : 1가지 각각의 카메라가 방향에 따라 감시할 수 있는 구역 리스트 구하기 각각 카메라 구역 리스트에서 1개씩 뽑는 경우 구하기 cartesian product.. 2022. 6. 27. 알고리즘 - DP / [백준] 11726. 타일링 - Python DP : Dynamic Programming 이전의 값을 재활용 하는 알고리즘 예시 : 1~10 숫자 중, 각각 이전 값들을 합한 값 구하기 이전의 값을 활용해서 시간 복잡도를 줄일 수 있음 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 생각 n이 1이면 1 n이 2이면 2 n이 3이면 1+2 A(n) = A(n-1) + A(n-2) 코드 from sys import stdin input = stdin.readline # 2Xn 크기의 직사각형 n = int(in.. 2022. 6. 26. [백준] 2110. 공유기 설치 - Python 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 생각 공유기 사이의 거리를 기준으로 이진탐색 start = 1, end = 첫번째 집과 마지막 집 거리 mid = (start + end)//2 거리가 mid 이상이면 뽑기 첫번째 집부터 순서대로 거리 계산 만약 공유기 설치한 집 수가 원하는 집 수보다 적으면 mid를 줄여야함 같다면 가장 인접한 두 공유기 사이의 최대 거리를 구하는 것이므로 m.. 2022. 6. 25. [백준] 2579. 계단 오르기 - Python https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 생각 DP 계단이 1칸짜리면 1칸 오르고 끝 2칸 이상일 때 1번 계단 : 1번계단 오르기 점수 2번 계단 : 1번계단 오르기 점수 + 2번계단 오르기 점수 3번 계단 : max(1번계단 오르기 점수 + 3번계단 오르기 점수, 2번계단 오르기 점수 + 3번계단 오르기 점수) 1번 -> 2번 -> 3번 : 불가능 1번 -> 3번 : 가능 2번 -> 3번 : 가능 i번( 4이상) : 두 가지 경우 중 최대값 한 .. 2022. 6. 24. [백준] 1654. 랜선 자르기 - Python https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 생각 길이를 이분 탐색으로 찾기 처음에는 길이 합을 필요한 랜선의 개수로 나눈 그 숫자부터 찾으려고 했으나 시간초과를 우려해 이분탐색으로 바꿨다. 이전에 '나무 자르기' 문제를 푼 것이 많이 도움이 되었다. 코드 input = stdin.readline # 이미 가지고 있는 랜선의 개수, 필요한 랜선의 개수 K,N = map(int,input().split()) # 가.. 2022. 6. 23. 이전 1 ··· 10 11 12 13 14 15 16 ··· 33 다음 반응형
