study_data_structure
[Tips]
- def 줄 빼고 다 지워도 됨. 문제에서
- ~인지 아닌지 확인하라고 했으면 [return 조건문].
- 출력하라고 했으면 print.
- 단순히 반환 하라고 했으면 [return 코드]만, print하면 안됨.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"89396 (6)
87956 (7, 1016)
77424 (8, 1025)
- 3w 수업내용 : greedy (그리디)
- 거스름돈
- 1이 될때까지
- 곱하기 혹은 더하기
- 모험가 길드 문제
--
- 3w 실습
- 주식 매매 최대이득
- 아이에게 원하는 쿠키 주기
74820 (9, 1028)
72352 (10, 1031)
67743 (11, 1037)
60415 (12, 1049)
58852 (13, 1052)
55131 (14, 1060)
데이터 마이닝 시간에 한 문제 풀었음. (교수님 풀이 보기 전에 주신 시간 (15분)내에 풀었음.)
52129 (15, 1067)
교수님께서 참고하신 듯한 자료...
50339 (16, 1072)
50080 (17, 1073)
요새 점수 잘 받다가 갑자기 1점 받으니까 좀 기부니가 좀 그르네,,, - 자릿수별로 나눠서 더하는 방법이 있었다니...
46910 (18, 1082)
... 완전탐색은 구현문제.. 시간에 구애받지 않음. 문제나 잘 읽을 것...
나도 진짜 잘 풀었는데 딕셔너리 아닌 리스트로 푸는 방법도 있었음.
43122 (19, 1094)
PaGe 3 ClEaR!!!!!~!!!!
42265 (20, 1097)
아... 다른 사람들 풀이보니까 조건에 메여있을게 아니라 조건을 적절히 활용할 줄 알았어야...
3000번이 아니라 그냥 n번만 돌리는 방법이.... 그치...
40348 (21, 1104)
ord라는 함수에 대해 알아볼것,,,,(문자열 순서대로 만드는 함수인듯,,, 알파벳 순서 반환)
39858 (22, 1006)
어제 약수 문제 풀었던 기억이 남아있었고, 시간제약이 없었어서 막힘 없이 풀어버림...
(근데 이중 for loop에 for loop 하나 더는 좀 심하긴 했음.)
39593 (23, 1007)
다른 사람 풀이 보고 나는 대체 그 생각에 접근까진 해놓고 왜 이렇게 푼 걸까 싶었음.
39338 (24, 1008)
다른 사람 풀이 보니까 -일 때, +일 때로 나눠서 하는게 좋을 것 같음.
꺅 스택문제를 풀었다?!?!?!?!?!?!!!!!?!?!? 세상에. 심지어 혼자 풀었다????!?!?!?!
그런데 오늘 수업 많이 졸았음... 킹킹,,~
- 스택
- 후입 선출 (선입 후출, LIFO)
a. 기억하고 있어야 할 때
b. 가장 최근에 들어오는게 가장 먼저 나가야할 때 씀.
c. 후입일 수록 우선순위가 높음. (가장 마지막에 들어온 원소를 top이라고 부름.)
d. 입구, 출구 하나
- 예시
stack = []
## 스택 처리 코드
stack.append(5) # stack 상태 : [5]
stack.append(2) # stack 상태 : [5,2]
stack.append(3) # stack 상태 : [5,2,3]
stack.append(7) # stack 상태 : [5,2,3,7]
stack.pop() # stack 상태 : [5,2,3] # 가장 나중에 들어온 7이 삭제 됨.
stack.append(1) # stack 상태 : [5,2,3,1]
stack.append(4) # stack 상태 : [5,2,3,1,4]
stack.pop() # stack 상태 : [5,2,3,1] # 가장 나중에 들어온 1이 삭제 됨.
## 결과
stack = [5,2,3,1]- tips
a. 못하겠으면 손으로 먼저 풀어보기!
b. pop()은 뽑아서 삭제하는 코드
c. [-1]로 인덱싱 해서 마지막 꺼 뽑아서 조건검사 하는 것도 잊으면 안됨.
d. 짝 맞춰야하는 문제는 dic에 짝 지어주는게 핵심.
--- {후입:선입}식으로,
key로 value 찾는 기능 이용.
e. stack은 연산을 효율적으로 하기 위해 하는 것. (속도 면...)
- 큐
- 선입선출 (FIFO)
들어온 순서 그대로 기억해야할 때
a. 입구, 출구 각각
- BFS 문제에서 활용
- queue 구현을 위한 라이브러리 (.pop(0) 성능이 나쁘기 때문에 사용.)
from collections import deque
queue = deque(list) # 이런식으로 받아서 사용.
## .pop(0)대신 .popleft() 사용. 성능 훨씬 좋음.37447 (25, 1116)
- 소수 찾기문제
원 풀이법: 에라토스테네스의 체
응용한 풀이법: 배수를 계속 차집합
37331 (26, 1117)
- list에서도 index 쓰임.
36683 (27, 1120)
for loop 돌리다가 다 돌기 전에 먼저 조건 만족하면 그냥 리턴 하는...
- dfs 깊이 우선 탐색
- 모두방문
a. 재귀함수
그니까,, 뭔가 질문을 전혀 또 안꼬아서 하시니까... 내가 생각한 대답이 오답일까봐 답을 못하겠던 날이었...
while 옆에는 종료 조건임. 조건 불충족시 종료됨.
36894 (28, 1122)
24799 (29, 1132)
34502 (30, 1135)
좌우 '.' 지우기가 됨.
내장함수를 built in 함수라고 함.
filter 대신 for loop의 enumerate 사용 가능.
- 2개 이상의 문자에 대해서는 인덱싱이 안됨.
참고1
참고2 - 딱 필요한 부분만 적혀있음.
참고3 - 자세한 설명
sub라는 함수가 있었음.
정규식이라는게 있었음... (re 모듈을 사용하는...)
re 모듈은 Regular Expressions의 약어
정규식
(뭔가 당장은 몰라도 될 것 같은 느낌... 이상한 문자들이 코드인듯., 수준 내에서는 충분히 잘 풀었음.)
- 함수 parameter로 쓰인 수 +1만큼의 길이의 0으로만 구성된 dp 테이블을 만든다. (dp테이블 초기화)
- 초기값을 설정해준다.
a0, a1, a2,...
a0은 버리는(생각 안하는) 경우가 많음.
보통 a1, a2에 초기값 설정해줌.
** 창고문제는 a0에도 값이 있어서 안버림. (초기값 설정해줌.)
** 1로 만드는 문제는 a2부터 구해야해서, 그리고 a1은 어차피 0이라 초기값 설정 따로 안해줘도 됨.
- for문으로 dp 테이블을 채운다.
- 점화식을 이용한다.
** 뭔가 여러 개의 계산한 값들이 필요한데, 특정 조건일 때만 필요하다 싶으면 공리스트를 만들어 추가한다!!!
매번 들어있어야하는 값이라면 그 매번 들어있어야할 값을 추가해놓은 리스트에다가 추가한다.무슨 말인지 모르겠.... 그냥 1 만들기 c list가 충격적이었어서 남긴 말...
근데 1만들기 했었는데 (그 때도 내 손으론 못풀었음) 수업 때 못 푼거 킹받네...
근데 또 막상 다이나믹 프로그래밍이라서 못풀었다고하면 위안이 되기도 하고...
- reverse는 sorted(문자열, 리스트, ...) 안에 옵션으로 들어가는 것. 35278 (31, 1137)
- 같은 ~~는 싫어! 문제 tip
stack & append, pop 이용.