목록알고리즘 (18)

철갑이의 이모저모

[백준] 1759번(암호 만들기) with Python

문제 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 배열을 정렬한 후 itertools 라이브러리에서 combinations 이터레이터를 사용해서 문제를 풀었다. 그리고 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성이 되었는지 카운트 해서 결과를 도출했다. docs.python.org/ko/3/library/itertools.html#itertools.combinations itertools — 효율적인 루핑을 위한 이터레이터..
알고리즘 2020. 10. 13. 22:16
[백준] 11727번(2xn 타일링 2) with Python

문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 dp문제는 처음 풀어봐서 하나하나 그려서 규칙을 찾은 후 점화식을 구했다. 위의 그림과 같이 N이 3 이상 이면 N-1에서 2x1 타일이 붙고, N-2에서 1x2 타일 두 개, 2x2 타일이 한 개 붙는 규칙이 계속된다. 따라서, dp[n] = dp[n - 1] + dp[n - 2] * 2 dp[1]과 dp[2]를 미리 구해서 시작. 답 a = int(input()) dp = [0,1,3] for i in range(3, a + ..
알고리즘 2020. 10. 7. 23:25
[백준] 2003번(수들의 합 2) with Python

문제 www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 시간초과가 나서 투포인터를 공부해 문제를 풀어보았다. 합이 M보다 작은 경우 end 1 증가 시키고, M과 같으면 카운트, M보다 커지면 start 값을 1 증가시킨다. (반복) 답 N, M = map(int, input().split(' ')) A = list(map(int, input().split(' '))) cnt = 0 x = 0 end = 0 for start i..
알고리즘 2020. 10. 2. 20:46
[백준] 18406번(럭키 스트레이트) with Python

문제 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 풀이 len()으로 받아온 값의 자릿수를 구해주고 절반씩 나눠 누적값을 구해줬다. 누적값의 경우, 예를 들어 a에서 123402를 받아오면 ['1', '2', '3', '4', '0', '2']처럼 요소로 이루어진 리스트처럼 여겨지기 때문에 a[i]로 인덱싱해서 누적해주었다. 답 a = input() b = 0 c = 0 if len(a) % 2 == 0 : for i in range(0,len(a) // 2) : b += int(a[i]) for i in range(len(a) // 2, len(a)) : ..
알고리즘 2020. 10. 2. 15:13
[백준] 1057번(토너먼트) with Java

문제 www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 토너먼트 표를 그려서 규칙을 찾아 보았다. 김지민의 경우 8 -> 4 -> 2 -> 1 번째로 즉, 현재번호/2 + 0 로 표현할 수 있다. 임한수의 경우 9 -> 5 -> 3 -> 1 번째로 즉, 현재번호/2 + 1 로 표현할 수 있다. 짝수일 때 홀수일 때로 나누기엔 복잡해지는 것 같아 둘 다 (현재번호/2 + 현재번호/2의 나머지) 로 처리하였다. 답 import java.util.Scanner; pu..
알고리즘 2020. 9. 27. 18:07
[백준] 8958번(OX퀴즈) with Java

문제 www.acmicpc.net/problem/8958 8958번: OX퀴즈 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수�� www.acmicpc.net 풀이 O가 나올때마다 count 값을 누적해주고 result 배열에 저장 해준다. O가 안나오면 count를 0으로 초기화 한다. result 배열 값을 전부 더한 값을 arr에 넣어주고 출력. 좀 더 시간을 단축해볼 것. 답 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..
알고리즘 2020. 9. 27. 17:48
[백준] 2525번(오븐시계) with Python

문제 www.acmicpc.net/problem/2525 2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net 풀이 C를 받아 시와 분으로 나눠 각각에 더해준다. 더한 결과 값으로 B(분) 값이 60이 넘어가면 A(시)에 1을 더해주고, B(분)에 60을 뺀다. 23시 59분에서 1분이 지나면 0시 0분이 되는 부분을 처리하기 위해 A(시)가 24와 같거나 커지면 24를 빼준다. 아직 파이썬이 익숙하지 않음. 문제를 더 많이 풀어봐야겠다. 답 A, B = map(int,input().split()) C..
알고리즘 2020. 9. 27. 17:31
[백준] 2163번(초콜릿 자르기) with Python

문제 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿� www.acmicpc.net 풀이 그림을 그려가면서 규칙을 찾아봤는데 N*M 초콜릿 자르는 횟수는 (N-1)+N(M-1) = N*M-1 로 정리할 수 있었다. 답 N, M = map(int,input().split()) print(N*M-1)
알고리즘 2020. 9. 27. 11:48
이전 Prev 1 2 Next 다음