Skip to content

Commit d950b32

Browse files
SoniaCompSoniaComp
committed
week20
1 parent 1c31660 commit d950b32

File tree

5 files changed

+162
-26
lines changed

5 files changed

+162
-26
lines changed

‎python/week20/BOJ11758.py‎

Lines changed: 17 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,20 @@
11
'''
22
P1->P2 / P2->P3
3-
반시계방향: - - / - +
4-
시계방향:
3+
반시계방향: - - / - + // + - / + + // + + / - + // - + / - -
4+
시계방향: + - / - - // - - / - + // - + / + + // + + / + -
55
일직선: 기울기가 같다.
6-
'''
6+
'''
7+
8+
from operator import sub
9+
10+
# CCW : Counter-Clock-Wise
11+
# vector subtraction : tuple(map(sub, p1, p2))
12+
def ccw(a, b, c):
13+
a, c = tuple(map(sub, a, b)), tuple(map(sub, c, b))
14+
return a[0]*c[1]-a[1]*c[0]
15+
16+
# Main
17+
if __name__ == '__main__':
18+
p1, p2, p3 = [tuple(map(int, input().split())) for _ in range(3)]
19+
ans = ccw(p1, p2, p3)
20+
print(0 if ans==0 else -int(ans/abs(ans)))

‎python/week20/BOJ14425.py‎

Lines changed: 61 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,66 @@
1-
'''
2-
지금은 새벽 2시 30분.. 잘까말까 고민했당.. 그래두 스터디에서 내 몫을 다하쟝!
3-
서버에서도 제일 중요한 것중 하나인 CPU 사용률! 열씨미하장!
4-
'''
5-
61
# 이건 트라이가 좋을 듯
2+
import sys
3+
4+
5+
class Node(object):
6+
def __init__(self, key, data=None):
7+
self.key = key
8+
self.data = data
9+
self.children = {}
10+
11+
12+
class Trie(object):
13+
def __init__(self):
14+
self.head = Node(None)
15+
16+
def insert(self, string):
17+
curr_node = self.head
18+
19+
for char in string:
20+
if char not in curr_node.children:
21+
curr_node.children[char] = Node(char)
22+
curr_node = curr_node.children[char]
23+
24+
def search(self, string):
25+
curr_node = self.head
26+
27+
for char in string:
28+
if char in curr_node.children:
29+
curr_node = curr_node.children[char]
30+
else:
31+
return False
32+
33+
return True
34+
35+
# def solution(N, M):
36+
# trie = Trie()
37+
# stdin = sys.stdin
38+
# for i in range(N):
39+
# trie.insert(str(stdin.readline().strip()))
40+
# ans = 0
41+
# for j in range(M):
42+
# if trie.search(str(stdin.readline().strip())):
43+
# ans+=1
44+
# return ans
45+
46+
def solution(N, M):
47+
input = sys.stdin.readline
48+
strings = [input().rtrip() for _ in range(N)]
49+
ans = 0
50+
51+
for i in range(M):
52+
string = input().rstrip()
53+
if string in strings:
54+
ans += 1
55+
56+
return ans
57+
758

859
def main():
9-
pass
60+
stdin = sys.stdin
61+
N, M = map(int, input().split())
62+
print(solution(N, M))
63+
1064

1165
if __name__ == "__main__":
12-
main()
66+
main()

‎python/week20/BOJ15486.py‎

Lines changed: 34 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,36 @@
11
# 나도 백준이와 같은 마음
22

3-
# 예제가 많을 때는 예제를 많이 해본다. 귀납적인 거신가...?
3+
# 예제가 많을 때는 예제를 많이 해본다. 귀납적인 거신가...?
4+
5+
# 브루트 포스!?!?!? -> 범위가 너무 크다.
6+
# DP: 처음부터 쭉 하면서, 번 최대 금액 체크
7+
import sys
8+
9+
10+
def solution(N, T, P):
11+
dp = [0]*(N+1)
12+
for i in range(N):
13+
# if works[i][0] <= N-i: # 더 일 안하고! 딱 정해진 날짜에 퇴사!
14+
# dp[i+works[i][0]] = max(dp[i+works[i][0]], dp[i]+works[i][1])
15+
16+
# dp[i+1] = max(dp[i+1], dp[i])
17+
if i + T[i] < N+1:
18+
dp[i+T[i]] = max(dp[i]+P[i], dp[i+T[i]])
19+
dp[i+1] = max(dp[i+1], dp[i])
20+
return dp[N]
21+
22+
23+
def main():
24+
stdin = sys.stdin
25+
N = int(input()) # [T,P]
26+
# works = [list(map(int, input().split())) for _ in range(N)]
27+
T, P = [], []
28+
for i in range(N):
29+
tmp = [int(i) for i in sys.stdin.readline().split()]
30+
T.append(tmp[0])
31+
P.append(tmp[1])
32+
print(solution(N, T, P))
33+
34+
35+
if __name__ == "__main__":
36+
main()

‎python/week20/BOJ17085.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
dr = [(-1, 0), (1, 0), (0, -1), (0, 1)]
44

55
# 기능 하나 분리
6-
6+
# 브루트포스
77

88
def range_check(y, x, r, N, M):
99
for i in range(-1, 2, 2):

‎python/week20/BOJ3015.py‎

Lines changed: 49 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -24,24 +24,59 @@
2424
2525
'''
2626
import sys
27-
27+
import collections
2828

2929
# 우선 N^2 복잡도로 풀어본다.
30+
# def solution(N, arr):
31+
# ans = 0
32+
# for idx in range(N-1):
33+
# if arr[idx] < arr[idx+1]:
34+
# ans += 1
35+
# continue
36+
# count = 1
37+
# max_height = arr[idx+1]
38+
# for i in range(2, N-idx):
39+
# if arr[idx+i] >= max_height:
40+
# count += 1
41+
# max_height = arr[idx+i]
42+
# if arr[idx] < max_height:
43+
# break
44+
# ans += count
45+
# return ans
46+
3047
def solution(N, arr):
48+
stack = [] # [키, 연속 몇명]
3149
ans = 0
32-
for idx in range(N-1):
33-
if arr[idx] < arr[idx+1]:
34-
ans += 1
35-
continue
36-
count = 1
37-
max_height = arr[idx+1]
38-
for i in range(2, N-idx):
39-
if arr[idx+i] >= max_height:
40-
count += 1
41-
max_height = arr[idx+i]
42-
if arr[idx] < max_height:
43-
break
44-
ans += count
50+
for i in range(N):
51+
height = arr[i]
52+
# 현재 사람의 키가 스택의 top에 있는 사람보다 크다면,
53+
# 현재 사람 이후 쌍을 이루지 못함
54+
while stack and stack[-1][0] < height:
55+
ans += stack[-1][1]
56+
del stack[-1]
57+
58+
# 맨앞에 사람을 세움
59+
if not stack:
60+
stack.append([height, 1])
61+
else:
62+
# 같은 키의 경우 따로 처리
63+
if stack[-1][0] == height:
64+
cur = stack[-1]
65+
del stack[-1]
66+
ans += cur[1]
67+
68+
# 스택 내 제일 큰 사람과 쌍을 이룸
69+
if stack:
70+
ans += 1
71+
72+
# 연속해서 같은 키가 나옴
73+
cur[1] += 1
74+
stack.append(cur)
75+
76+
# 더 작은 사람
77+
stack.append([height, 1])
78+
ans +=1
79+
4580
return ans
4681

4782

0 commit comments

Comments
 (0)