일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
- 킥스타트
- 브루트포스
- 동적 프로그래밍
- 파이썬
- nlp
- PYTHON
- kick start
- google coding competition
- 코딩테스트
- 코딩 테스트
- OS
- 백준
- 알고리즘
- 동적프로그래밍
- linux
- 딥러닝
- BFS
- 프로그래머스
- DFS
- 구글 킥스타트
- AI
- 네트워크
- 코딩
- 그래프
- 운영체제
- 순열
- dp
- 프로그래밍
- 리눅스
- CSS
- Today
- Total
목록프로그래밍 (15)
오뚝이개발자
문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 생각의 흐름 예컨대, 세 자리 수를 구할 때 끝자리가 2라면 앞의 두자리에 올 수 있는 수는 2보다 작거나 같은 수들 뿐이다. 이러한 생각에 착안하여 앞자리는 두 자리 수 중 끝자리가 2인수+1인수+0인수임을 알 수 있다. 이것이 바로 동적프로그래밍을..
문제 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 www.acmicpc.net 생각의 흐름 이전에 포스팅한 연산자 끼워넣기와의 차이점은 연산자의 갯수가 많아졌다는 점이다. 동일한 방법으로 짜도..
문제 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 생각의 흐름 처음에 리스트를 1부터 넣어 초기화해주고 이전에 포스팅했던 다음 순열의 알고리즘을 사용하면 된다 코드 def next_permutation(arr): n = len(arr)-1 if n==0: return -1 i = n while arr[i-1] > arr[i]: i -= 1 if i == 0: return -1 j = i-1 diff = 10000 position_to_switch = 0 for k in range(i, n+1): if arr[k]-arr[j] > ..
문제 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 생각의 흐름 다음 순열 문제의 대소비교 부분을 반대로 생각하면 된다. 코드 def next_permutation(arr): n = len(arr)-1 if n==0: return -1 i = n while arr[i-1] < arr[i]: i -= 1 if i == 0: return -1 j = i-1 diff = -10000 position_to_switch = 0 for k in range(i, n+1): if arr[k]-arr[j] < 0:..
문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 생각의 흐름 맨 마지막으로 더하는 수가 각각 1,2,3인 경우로 나누면 dp를 사용해야 함을 알 수 있다. dp[i] =..
문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 생각의 흐름 최댓값을 구하기 위해 필요한 규칙성이 없음을 발견 -> 즉, 브루트포스로 모든 경우를 계산해봐야 함 모든 경우란 ..
문제 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1 www.acmicpc.net 풀이 핵심 방법론은 브루트 포스다!!! 말 그대로 문제의 조건에 따라서 E,S,M에 1씩 더해주고 그 때마다 year도 1씩 더해..