전체 글
-
구현 알고리즘 : 왕실의 나이트 - 파이썬 (python)알고리즘/구현 2021. 4. 3. 21:19
- 입력 조건 첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다. - 출력조건 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오. * 방법 아이디어: 나이트는 2가지 경로로 움직일 수 있다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 나이트의 이동 경로를 steps 변수에 넣는다면, 이 2가지 규칙에 따라 steps = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)] 로 나타낼 수 있다. 나이트의 현재 위치가 주어지면 현재 위치에서 이..
-
백준 2437번 : 저울 - 파이썬 (python)알고리즘/그리디 2021. 4. 3. 18:21
www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net - 유사 문제 ssssol.tistory.com/50?category=956078 그리디 알고리즘 : 곱하기 혹은 더하기 - 파이썬 (python) - 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1= x (=1) 이므로 target = target + x = 1 + 1 = 2 ② target (=2) >= x (=1) 이므로 target = target + x = 2 + 1 = 3 ③..
-
백준 2217번 : 로프 - 파이썬 (python)알고리즘/그리디 2021. 4. 2. 01:02
www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net * 방법1 - 아이디어 문제가 이해가 안가는데 테스트케이스도 하나밖에 없어서 질문 게시판에서 반례 예시를 참고했다. (1) 입력받은 데이터를 내림차순으로 정렬한다. (2) data[0] / data[0], data[1] / data[0], data[1], data[2] / data[0], data[1], data[2],data[3] / data[0], data[1], data[2], data[3], d..
-
백준 11047번 : 동전 0 - 파이썬 (python)알고리즘/그리디 2021. 4. 1. 23:49
www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net * 방법1 - 아이디어 (1) 입력받은 동전의 가치를 내림차순으로 정렬한다. (2) 가치의 합 K 보다 작거나 같은 값의 인덱스를 찾는다. (3) K를 coin[i] (가치의 합 K 보다 작거나 같은 값)으로 나눈 몫을 result에 더한다. (4) K 값을 K - ((k // coin[i]) * coin[i]) 로 변경한다. - 테스트케이스 1 ..
-
백준 2839번 : 설탕 배달 - 파이썬 (python)알고리즘/그리디 2021. 3. 30. 00:55
www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net * 방법 1 아이디어: N을 5로 나누어 5kg 설탕의 최대 수를 계산하고 나머지 ( N - 5kg 설탕 수 * 5) 이 3으로 나누어 떨어지는지 확인한다. 나누어 떨어지지 않으면 5kg 설탕의 수를 1만큼 줄이고 과정을 반복한다. 5kg 설탕 수가 -1이 되면 이는 만들 수 없는 설탕의 무게이므로 -1을 출력한다. n = int(input()) # 배달해야 하는 설탕의 무게 result = 0 count3 = 0 # 3..
-
백준 4889번 : 안정적인 문자열 - 파이썬 (python)알고리즘/그리디 2021. 3. 25. 23:47
www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net * 방법1 → X 아이디어: '{' 가 있으면 다음에 '}' 가 존재하는 것이 최소값이라고 가정한다. 0부터 시작해서 짝수 인덱스가 '{' 가 아니면 result 값을 1 증가시키고 홀수 인덱스가 '}' 가 아니면 result 값을 1 증가시키는 방법을 처음 생각했다. ⑴ }{ 인 경우 : 인덱스 0번의 경우 {가 아니므로 result+1 인덱스 1번의 경우 }가 아니므로 result+1 ⑵ {}{}인 경우..
-
백준 16953번 : A → B - 파이썬 (python)알고리즘/그리디 2021. 3. 25. 20:34
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net * 아이디어 B에서 A로 가는 방법을 생각한다. 2 → 4 → 8 → 81 → 162 의 경우 162를 2로 나누었을 때 나머지가 0이다. 나머지가 0인 경우 b를 2로 나누고 그 값을 b에 저장하고 result += 1을 수행한다. (문제에 따라 result의 초기값은 1) 81을 2로 나눈 경우 나머지는 1이다. 나머지가 1이면 81를 10으로 나눈 몫인 8을 b에 저장하고 result += 1을 수행한다. 8을 2로 나누면 나머지가 0이므로 8을 2로 나눈 값을 b에 저장하고 result += 1을 수행한다. 4 (= 8//2) ..