[2302] 극장 좌석
d[n] : VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수
- 소스코드
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 | #include <stdio.h> int vip[41], d[41]; int go(int k) { int ret; if(k == 0 || k == 1) return 1; if(d[k]) return d[k]; if(vip[k]) return d[k] = go(k-1); ret = go(k-1); if(!vip[k-1]) ret += go(k-2); return d[k] = ret; } int main() { int n, m, k; scanf("%d%d", &n, &m); while(m--) { scanf("%d", &k); vip[k] = 1; } printf("%d\n", go(n)); return 0; } | cs |
>> n이 n번에 앉았을 때의 경우의 수 : d[n-1]
>> n이 n-1에 앉았을 때의 경우의 수 : d[n-2]
>> 여기서는 10번 라인을 쓰지 않으면, n-1번이 vip석이 아닌경우 n번이 vip석이여도 n-1과 n번이
바꿔 앉는 경우를 세어 중복이 발생한다.
'BOJ > DP' 카테고리의 다른 글
| [11048] 이동하기 (0) | 2018.02.18 |
|---|---|
| [9184] 신나는 함수 실행 (0) | 2018.02.16 |
| [1937] 욕심쟁이 판다 (0) | 2018.02.01 |
| [1309] 동물원 (0) | 2018.02.01 |
| [1932] 숫자삼각형 (0) | 2018.02.01 |
<1-7> 정규표현식 with Python
### Day_01_05_re.py
동영상 강의 : http://pythonkim.tistory.com/notice/77
- import re 를 해주어야 한다.
- Google 에서 "3412 bob 123" 검색
>> http://www.linuxfocus.org/Korean/July1998/article53.html 에서 db 데이터 가져올 수 있음.
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 | import re db = '''3412 Bob 123 3834 Jonny 333 1248 Kate 634 1423 Tony 567 2567 Peter 435 3567 Alice 535 1548 Kerry 534''' print(db) # 3412 Bob 123 # 3834 Jonny 333 # 1248 Kate 634 # 1423 Tony 567 # 2567 Peter 435 # 3567 Alice 535 # 1548 Kerry 534 ns = re.findall(r'[0-9]', db) # 숫자 print(ns) # ['3', '4', '1', '2', '1', '2', '3', '3', '8', '3', '4', '3', '3', '3', '1', '2', '4', '8', '6', '3', '4', '1', '4', '2', '3', '5', '6', '7', '2', '5', '6', '7', '4', '3', '5', '3', '5', '6', '7', '5', '3', '5', '1', '5', '4', '8', '5', '3', '4'] ns = re.findall(r'[0-9]+', db) # 숫자 한개 이상 print(ns) # ['3412', '123', '3834', '333', '1248', '634', '1423', '567', '2567', '435', '3567', '535', '1548', '534'] | cs |
# 문제
# 이름만 찾아보기
1 2 3 4 5 6 7 | # 문제 # 이름만 찾아보기 # names = re.findall(r'[a-zA-Z]+', db) names = re.findall(r'[A-Z][a-z]+', db) # 처음 대문자 한글자 + 소문자 한개 이상. print(names) # ['Bob', 'Jonny', 'Kate', 'Tony', 'Peter', 'Alice', 'Kerry'] | cs |
>> [A-Za-z]+ 와 [A-Z][a-z]+ 는 다르다..!!
# 문제
# T로 시작하는 이름
# T로 시작하지 않는 이름
1 2 3 4 5 6 7 8 9 10 11 12 | # 문제 # T로 시작하는 이름 # T로 시작하지 않는 이름 Tname = re.findall(r'T[a-z]+', db) print(Tname) # ['Tony'] nTname = re.findall(r'[^T][a-z]+', db) # bug print(nTname) # ['Bob', 'Jonny', 'Kate', 'ony', 'Peter', 'Alice', 'Kerry'] nTname = re.findall(r'[A-SU-Z][a-z]+', db) print(nTname) # ['Bob', 'Jonny', 'Kate', 'Peter', 'Alice', 'Kerry'] | cs |
>> T로 시작하지 않는 단어 중 [^T][a-z] 로 했을 때 문제가 있었다.
>> 바로 'ony' 라는 단어까지 검색이 되어버렸다.
# raw string
r'string' : raw
- 파이썬에서 사용하는 문자열로 일반 문자열과 충돌을 막기 위해 제공하는 것 같다 .
- 정규표현식 외에 쓸일은 없다고 한다.
'Language > Python' 카테고리의 다른 글
| <2-2> 리스트, 튜플 (0) | 2018.02.15 |
|---|---|
| <2-1> 제어문과 반복문의 연결고리 (0) | 2018.02.06 |
| <1-6> 정규표현식 (Regular Expression) (0) | 2018.02.02 |
| <1-5> 함수(function) (0) | 2018.02.01 |
| <1-4> 제어문(if) (0) | 2018.01.31 |
<1-6> 정규표현식 (Regular Expression)
### 정규표현식
- 특정한 규칙을 가진 문자열의 집합을 표현
- 문자열의 검색과 치환을 위해 지원.
POSIX 기본 및 확장 표준 문법
| 메타문자 | 기능 | 설명 |
|---|---|---|
| . | 문자 | 1개의 문자와 일치한다. 단일행 모드에서는 새줄 문자를 제외한다. |
| [ ] | 문자 클래스 | "["과 "]" 사이의 문자 중 하나를 선택한다. "¦"를 여러 개 쓴 것과 같은 의미이다. 예를 들면 [abc]d는 ad, bd, cd를 뜻한다. 또한, "-" 기호와 함께 쓰면 범위를 지정할 수 있다. "[a-z]"는 a부터 z까지 중 하나, "[1-9]"는 1부터 9까지 중의 하나를 의미한다. |
| [^ ] | 부정 | 문자 클래스 안의 문자를 제외한 나머지를 선택한다. 예를 들면 [^abc]d는 ad, bd, cd는 포함하지 않고 ed, fd 등을 포함한다. [^a-z]는 알파벳 소문자로 시작하지 않는 모든 문자를 의미한다. |
| ^ | 처음 | 문자열이나 행의 처음을 의미한다. |
| $ | 끝 | 문자열이나 행의 끝을 의미한다. |
- 양의 지정
?물음표는 0번 또는 1차례까지의 발생을 의미한다. 이를테면 colou?r는 "color"와 "colour"를 둘 다 일치시킨다.*별표는 0번 이상의 발생을 의미한다. 이를테면 ab*c는 "ac", "abc", "abbc", "abbbc" 등을 일치시킨다.+덧셈 기호는 1번 이상의 발생을 의미한다. 이를테면 ab+c는 "abc", "abbc", "abbbc" 등을 일치시키지만 "ac"는 일치시키지 않는다
출처 : Wiki (https://ko.wikipedia.org/wiki/정규_표현식)
### Regex Crossword (https://regexcrossword.com/) ###
- Regular Expression 을 crossword 퍼즐을 통해 익힐 수 있게 도와주는 사이트
- Tutorial Play 을 통해 기본적인 학습을 할 수 있다.
Ex)
- (A)\1 에서 ( )\ 는 한 쌍..!! 여기서 \ 의 뜻은 ( )의 인덱스. ( )는 9개까지 쓸 수 있다.
- A{2, } : 두 번 이상.
- A{1} : 한 번.
- \s 는 공백
- Beginner 등을 통해 연습을 할 수 있다.
Ex)
- .* : 아무 글자. 있어도 되고 없어도 되고.
- M? : M이 하나 있거나 없거나.
- / 는 문자. \ 는 의미가 있다.
- *가 [] 안에 들어가면 단순 문자. >> [*]
- \d : 숫자, [0-9] 와 동일
- \D : 숫자가 아닌 것들.
'Language > Python' 카테고리의 다른 글
| <2-1> 제어문과 반복문의 연결고리 (0) | 2018.02.06 |
|---|---|
| <1-7> 정규표현식 with Python (0) | 2018.02.03 |
| <1-5> 함수(function) (0) | 2018.02.01 |
| <1-4> 제어문(if) (0) | 2018.01.31 |
| <1-3> 연산자 (0) | 2018.01.30 |
[1937] 욕심쟁이 판다
d[r][c] : (r, c)에서 대나무를 먹기 시작했을 때, 판다가 살 수 있는 최대 일수.
- 소스코드
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 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <stdio.h> int n; int g[505][505]; int d[505][505]; int dr[]={1, 0, -1, 0}; int dc[]={0, 1, 0, -1}; int max(int a, int b) { return a > b ? a : b; } int go(int r, int c) { int i, ret=1; if(d[r][c]) return d[r][c]; for(i=0; i<4; i++) { int nr = r+dr[i]; int nc = c+dc[i]; if(g[r][c] < g[nr][nc]) { ret = max(ret, go(nr, nc)+1); } } return d[r][c] = ret; } int main() { int i, j, ans = 0; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d", &g[i][j]); for(i=1; i<=n; i++) for(j=1; j<=n; j++) ans = max(ans, go(i, j)); printf("%d\n", ans); return 0; } | cs |
>> 오타때문에 두번 틀렸다...ㅜㅜ
>> 좌표를 (1,1) 부터 시작하고 사이즈를 505로 넉넉하게 잡으면, 좌표를 벗어날 일이 없다.
'BOJ > DP' 카테고리의 다른 글
| [9184] 신나는 함수 실행 (0) | 2018.02.16 |
|---|---|
| [2302] 극장 좌석 (0) | 2018.02.05 |
| [1309] 동물원 (0) | 2018.02.01 |
| [1932] 숫자삼각형 (0) | 2018.02.01 |
| [1149] RGB 거리 (0) | 2018.01.30 |
[1309] 동물원
d[n][k] : n번째 줄에 상태가 k일 때, n번째 줄까지 사자를 배치할 수 있는 경우의 수
- 소스코드
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 | #include <stdio.h> #define MOD 9901 int d[100001][3]; int go(int n, int k) { int a, b; if(n == 0) return 1; if(d[n][k]) return d[n][k]; a = go(n-1, (k+1)%3); b = go(n-1, (k+2)%3); if(k == 0) a += go(n-1, 0); return d[n][k] = (a+b)%MOD; } int main() { int n; scanf("%d", &n); printf("%d\n", go(n, 0)); return 0; } | cs |
>> k = 0 인 경우는 둘 다 비워있는 상태.
>> k = 1 인 경우는 사자를 왼쪽에 배치, k = 2 인 경우는 사자를 오른쪽에 배치한 상태
'BOJ > DP' 카테고리의 다른 글
| [2302] 극장 좌석 (0) | 2018.02.05 |
|---|---|
| [1937] 욕심쟁이 판다 (0) | 2018.02.01 |
| [1932] 숫자삼각형 (0) | 2018.02.01 |
| [1149] RGB 거리 (0) | 2018.01.30 |
| [1463] 1로 만들기 (0) | 2018.01.26 |
[1932] 숫자삼각형
d[n][k] : n번째 줄의 k번째 숫자를 선택 했을 때,
1층부터 n층까지 아래로 내려오면서 더한 합의 최대값.
- 소스코드
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 32 33 34 35 36 37 38 39 40 41 | #include <stdio.h> #include <string.h> int g[505][505]; int d[505][505]; int max(int a, int b) { return a > b ? a : b; } int go(int n, int k) { int L, R; if(n == 0 || k == 0) return 0; if(d[n][k] != -1) return d[n][k]; L = go(n-1, k-1); R = go(n-1, k); return d[n][k] = g[n][k] + max(L, R); } int main() { int i, j, n; int ans=0; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d", &g[i][j]); memset(d, -1, sizeof(d)); for(i=1; i<=n; i++) ans = max(ans, go(n, i)); printf("%d\n", ans); return 0; } | cs |
>> 위의 줄 오른쪽 대각선의 k값은 현재 줄의 k값과 동일하며,
>> 위의 줄 왼쪽 대각선의 k값은 현재 줄의 k-1값과 동일.
>> k는 1부터 시작, g[n][0] = 0 인점을 이용.
- 아래 코드는 바텀업
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 | #include <stdio.h> int n, g[501][501], d[501][501]; int main() { int i, j, ans; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d", &g[i][j]); d[1][1] = g[1][1]; for(i=2; i<=n; i++) { for(j=1; j<=i; j++) { d[i][j] = d[i-1][j-1] > d[i-1][j] ? d[i-1][j-1] : d[i-1][j]; d[i][j] += g[i][j]; } } ans = d[n][1]; for(i=2; i<=n; i++) if(ans < d[n][i]) ans = d[n][i]; printf("%d\n", ans); return 0; } | cs |
>> 1년전에 푼 코드이고, 분명 직접 생각해내서 푼 기억은 있다.
>> 근데 보통 DP를 풀때 대부분의 문제를 탑다운으로 푸는데,,, 바텀업으로 풀려있다.
>> 코드의 원리는 위에서 설명한 아이디어와 동일하다.
'BOJ > DP' 카테고리의 다른 글
| [2302] 극장 좌석 (0) | 2018.02.05 |
|---|---|
| [1937] 욕심쟁이 판다 (0) | 2018.02.01 |
| [1309] 동물원 (0) | 2018.02.01 |
| [1149] RGB 거리 (0) | 2018.01.30 |
| [1463] 1로 만들기 (0) | 2018.01.26 |
<1-5> 함수(function)
동영상 강의 : http://pythonkim.tistory.com/notice/77
# Day_01_04_Function.py
# Function
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 32 33 34 35 36 37 38 39 40 41 42 43 | # 함수의 핵심 : 데이터를 넘겨주고 넘겨받기 # 매개변수 : 넘겨주는 데이터 # 리턴값 : 넘겨받는 데이터 # 매개변수 없고, 반환값도 없고. def f1(): print('f1') f1() # f1 # 매개변수 있고, 반환 값 없고 def f2(a, b): print('f2', a, b) f2(23, 'abc') # f2 23 abc # 매개변수 없고, 반환 값 있고. def f3(): # pass # 아직 코딩 전이라는 뜻.. print('f3') return 17 a = f3() print(a) # 17 print(f3()) # 17 # 매개변수 있고, 반환 값 있고. # 두 자리 양수를 거꾸로 뒤집는 함수 만들기 def f4(num): return num%10*10 + num//10 print(f4(25)) # 52 | cs |
# 문제
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | # 문제 # 두 개의 정수 중에서 큰 숫자를 찾는 함수 def max2(a, b): if(a > b): return a return b print(max2(3, 7)) # 7 print(max2(7, 3)) # 7 # 문제 # 네 개의 정수 중에서 큰 숫자를 찾는 함수 def max4(a, b, c, d): x, y = max2(a, b), max2(c, d) return max2(x, y) print(max4(3, 9, 1, 7)) | cs |
>> 함수의 목적은 재사용..!!
'Language > Python' 카테고리의 다른 글
| <1-7> 정규표현식 with Python (0) | 2018.02.03 |
|---|---|
| <1-6> 정규표현식 (Regular Expression) (0) | 2018.02.02 |
| <1-4> 제어문(if) (0) | 2018.01.31 |
| <1-3> 연산자 (0) | 2018.01.30 |
| <1-2> 파이썬 입문 (0) | 2018.01.29 |
[ARTIK530] ubuntu로 시작하기
### Mac 에서 ARTIK530 접속 확인.
터미널에서
$ ls /dev/tty* 통해서 시리얼 인터페이스 확인
$ ls /dev/tty.usbserial-A504RVLK 115200 통해서 접속 가능.
>> 여기서 115200은 통신속도로 같이 입력은 안해주면 접근을 못함.
초기 id : root // 초기 pw : root
### Ubuntu OS Image 설치(탑재) ###
1. Image File 다운로드 (https://developer.artik.io/documentation/artik/getting-started/up-to-date.html)(https://developer.artik.io/documentation/downloads.html#firmware)
2. Micro SD카드를 PC에 연결
3. Etcher 설치(https://etcher.io/)
4. Etcher(SD카드에 이미지를 구워주는 프로그램) 실행 후, 다운받은 Image File을 SD카드에 Flash
5. ARTIK 보드의 전원을 OFF
6. 리더기에 microSD card를 꺼내어 ARTIK 보드에 microSD slot에 삽입
7. boot switch SW402-4 ON 으로 설정
8. 보드의 전원을 켜고 전원버튼을 1초동안 누름
9. 보드의 업데이트가 완료됬을 때 eMMC를 재부팅하라는 메시지가 표시
10. 영구적 메모리로부터 ARTIK 재부팅
1) 보드를 끄고 난 후 microSD card를 제거
2) boot switch SW402-4 을 ON 에서 OFF로 원래대로 설정
3) 보드의 전원을 켜고 전원버튼을 1초 동안 누른다.
(정상적인 부팅 메시지와 로그인 prompt가 보이면 정상)
4) 정상적으로 업데이트 버전이 되어있는지 확인
(cat /etc/artik_release) => OFFICIAL_VERSION=A530_os_3.0.0
### WiFi 설정 ###
1. Console창에 명령어 입력
$ wpa_passphrase SSID PASSWORD >> /etc/wpa_supplicant/wpa_supplicant.conf)
2. /etc/wpa_supplicant/wpa_supplicant.conf 파일에서 #psk 부분 삭제
(암호화 되지 않은 WiFi 패스워드 부분)
3. wpa_supplicant 재실행
$ systemctl restart wpa_supplicant)
4. WiFi 연결 완료
5. $ dhclient wlan0
6. $ ifconfig wlan0 통해 확인 혹은 Ping 테스트 (명령어 : $ ping 8.8.8.8)
'Etc. > G2C' 카테고리의 다른 글
| [ARTIK530] aptitude 를 이용한 player 설치하기 (0) | 2018.02.07 |
|---|
<1-4> 제어문(if)
동영상 강의 : http://pythonkim.tistory.com/notice/77
# Day_01_03_if.py
- 들어가기 앞서, 파이썬은 인덴트에 민감하다..!!
- " : "(콜론) 이 나왔을 땐 들여쓰기가 있어야 한다.
# if: else:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | a = 13 print(a % 2) # 1 if a%2 == 1: print('홀수') # 홀수 else: print('짝수') if a%2: # 1 은 True print('홀수') # 홀수 else: print('짝수') if a: print(a) # 13 | cs |
# 문제
# 0 ~ 999 사이의 값을 입력 받아
# 몇 자리 숫자인지 맞춰보기
1 2 3 4 5 6 7 8 | # 문제 # 0 ~ 999 사이의 값을 입력 받아 # 몇 자리 숫자인지 맞춰보기 a = input("number : ") # 키보드로 부터 입력을 기다린다., input 안의 문자열은 프롬프트 if a >= 100: print("3자리 숫자") | cs |
- 하지만 위와 같이 작성하면 파이썬은 에러를 발생시킨다.
>> a 에는 str 타입이 저장되기 때문..!!
1 2 3 4 5 | a = input("number : ") print(type(a)) # <class 'str'> a = int(input("number : ")) print(type(a)) # <class 'int'> | cs |
- 지금까지 배운 내용으로는 이정도로..
1 2 3 4 5 6 7 | if a >= 100: print(3) else: if a >= 10: print(2) else: print(1) | cs |
# 공백 : space , enter, tab
- 파이썬 인터프리터가 무시하는 세가지.
1. 스페이스
2. 엔터
3. 탭
1 2 3 4 5 6 | print( 'Hello') print( 'Hello' ) print( 'Hello') | cs |
# elif
1 2 3 4 5 6 | if a >= 100: print(3) elif a >= 10: print(2) else: print(1) | cs |
'Language > Python' 카테고리의 다른 글
| <1-7> 정규표현식 with Python (0) | 2018.02.03 |
|---|---|
| <1-6> 정규표현식 (Regular Expression) (0) | 2018.02.02 |
| <1-5> 함수(function) (0) | 2018.02.01 |
| <1-3> 연산자 (0) | 2018.01.30 |
| <1-2> 파이썬 입문 (0) | 2018.01.29 |
<7> REST API & CRUD
# REST
- REpresentational State Transfer
- REST is an architecture style for designing networked applications.(wiki)
- 표면적인 실체는 '스타일' 또는 '패턴'이라고 할 수 있다고 한다.
# RESTful API
- REST한 방식의 API란, 아래와 같이 잘 설계된 API를 의미한다고 한다.
・ 웹을 근간으로 하는 HTTP Protocol 기반이다.
・ 리소스는 URI(Uniform resource Identifiers)로 표현하며, 말 그대로 '고유'해야한다.
・ URI는 단순하고 직관적인 구조여야 한다.
・ 리소스의 상태는 HTTP Methods를 활용해서 구분한다.
・ xml/json을 활용해서 데이터를 전송한다. (주로 json)
# CRUD
- 네트워크를 통해 웹 리소스(resource)를 다루기 위한 행위들.
- 각각의 행위를 처리하기 위한 HTTP methods(POST, GET, PUT, DELETE) 가 있다.
・ Create (POST)
・ Retrive (GET)
・ Update (PUT)
・ Delete (DELETE)
# API Design
- 복수명사를 사용 (/movies)
- 필요하면 URL에 하위자원을 표기함. (/movies/23)
- 필터조건을 허용할 수 있음 ( /movies?state=active)
# Example
URL |
Methods |
설명 |
/movies/ |
GET |
모든 영화 리스트 가져오기 |
/movies/ |
POST |
영화 추가 |
/movies/:title |
GET |
title 해당 영화 가져오기 |
/movies/:title |
DELETE |
title 해당 영화 삭제 |
/movies/:title |
PUT |
title 해당 영화 업데이터 |
/ movies?min=9 |
GET |
상영중인 영화 리스트 |
-
'H6 > backend (Node.js, tsc)' 카테고리의 다른 글
| <6> tsconfig.json 을 통한 컴파일 옵션 설정 (0) | 2018.01.31 |
|---|---|
| <5> node-mysql (Typescript) (0) | 2018.01.22 |
| <4> MySQL & node-mysql (0) | 2018.01.22 |
| <3> 에러처리.. (0) | 2018.01.22 |
| <2> app.ts 및 server.ts 만들기 (0) | 2018.01.22 |
