일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- 리눅스
- nlp
- OS
- CSS
- 그래프
- 코딩 테스트
- 구글 킥스타트
- PYTHON
- 프로그래머스
- kick start
- 코딩테스트
- 딥러닝
- 킥스타트
- 프로그래밍
- AI
- google coding competition
- 동적 프로그래밍
- 파이썬
- DFS
- 브루트포스
- 순열
- BFS
- 코딩
- linux
- 동적프로그래밍
- dp
- 네트워크
- 운영체제
- 백준
- 알고리즘
- Today
- Total
목록전체 글 (312)
오뚝이개발자
문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 dp를 이용해 d[i][j]에는 i개를 더해 j가 되는 경우의 수를 저장한다. 그런데 생각을 해보면 d[i][j]=d[i][j-1]+d[i-1][j]라는 걸 알 수 있다. dp를 직접 표로 그려 계산해보면 이해가 좀 더 쉬울 것이다. 코드 # 백준 2225 n, k = list(map(int, input().split())) dp = [[0]*(n+1) for _ in range(k+1)] for i in range(n+1): dp[1][i]=1 for i in range(2, k+1): for j in ..
문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 생각의 흐름 이전에 포스팅한 적이 있는 가장 긴 감소하는 수열과 유사하다. 차이점은 길이 뿐 아니라 수열까지도 출력한다는 것인데 이 때 뒤에서부터 순차적으로 출력해야한다는 것만 유념하면 된다. 코드 # 백준 14002 N = int(input()) arr = list(map(int, inpu..
문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. www.acmicpc.net 생각의 흐름 각 자리에 있는 수를 선택하였을 때 올 수 있는 가장 큰 합을 dp 리스트에 저장한다. 예를 들어, 문제에서 예시로 주어진 arr = [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]의 경우 dp = [1, 10..
OS란 무엇인가? OS란 컴퓨터 자원을 효율적으로 "관리"해서 사용자에게 "서비스"를 제공하는 것 HW란? 1. 프로세서 1) 주 역할 : "계산" 2) Ex) CPU, GPU(그래픽카드) 2. 메모리 1) 주 역할 : "저장" 2) Ex) 주기억장치, 보조기억장치 3. 주변장치 프로세서란? => 컴퓨터의 두뇌로 연산 수행, 컴퓨터 장치의 동작 제어 1. 레지스터 => 프로세서 내부의 메모리 1) 프로세서가 사용할 데이터 저장 2) 컴퓨터에서 가장 빠른 메모리 2. 레지스터의 종류(중요한 것들만 정리) 1) PC : 다음에 실행할 명령어 주소 저장 2) IR(명령어 레지스터) : 현재 실행하는 명령어 저장 3) ACC(Accumulator) : 데이터를 일시적으로 저장 3. OS와 프로세서 1) OS는 ..
문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 생각의 흐름 예컨대, 세 자리 수를 구할 때 끝자리가 2라면 앞의 두자리에 올 수 있는 수는 2보다 작거나 같은 수들 뿐이다. 이러한 생각에 착안하여 앞자리는 두 자리 수 중 끝자리가 2인수+1인수+0인수임을 알 수 있다. 이것이 바로 동적프로그래밍을..
분명 .gitignore에 추가를 했는데 계속 반영되지 않고 변경사항에 포함되는 경우가 있다. 이 경우 git의 cache에 데이터가 남아있어서인데 아래와 같이 cache를 지워주고 다시 add all 해주면 된다. git rm -r --cached . git add . git commit -m "fixed untracked files"
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 생각의 흐름 동적프로그래밍의 핵심 1) 전체 과정 중 반복되는 작은 단계 찾기 2) 해당 단계에서의 최대 혹은 최소값 찾기 3) 갱신..
문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 생각의 흐름 동적 프로그래밍을 사용하여 dp[i]에 2xi를 채우는 경우의 수를 계산하여 넣으면 된다. 점화식은 dp[i]=dp[i-2]*2+dp[i-1]이 되는데 이유는 다음과 같다. (i-1) 개 2x1 (i-2)개 2x1 2x1 (i-2)개 1x2 1x2 (i-2)개 2x2 위의 그림과 같은 경우가 있는데, 이 중 두번째 경우는 첫번째 경우에 포함이 될 수 있다. 따라서 dp[i-2]*3이 아닌 dp[i-2]*2가 ..