bong-u/til

bong-u/til

🏠 home 🐈 repository

백준 - 1967 : 트리의 지름(G4)

🧠 Algorithm

1import sys 2sys.setrecursionlimit(10**6) 3M = int(input()) 4G = [[] for _ in range(M)] 5 6for _ in range(M-1): 7 a, b, c = map(int, input().split()) 8 G[a-1].append((b-1, c)) 9 G[b-1].append((a-1, c)) 10 11n1 = 0 12tmp = 0 13 14def dfs(node, length): 15 global n1, tmp 16 visit[node] = True 17 if length > tmp: 18 tmp = length 19 n1 = node 20 for child, v in G[node]: 21 if not visit[child]: 22 dfs(child, length+v) 23 24visit = [False]*M 25dfs(0, 0) 26tmp = 0 27visit = [False]*M 28dfs(n1, 0) 29print (tmp) 인터넷에서 접근 방법을 참고했다 해결 방법 아무 정점에서 가장 먼 어떤 정점을 N이라고 하자 정점 N에서 가장 먼 정점 사이의 거리가 트리의 지름과 같다 느낀 점 루트를 구할 필요가 없다는 것을 깨달았다

백준 - 1167 : 트리의 지름 (G2)

🧠 Algorithm

1import sys 2sys.setrecursionlimit(10**6) 3input = sys.stdin.readline 4 5V = int(input()) 6G = [[] for _ in range(V)] 7for _ in range(V): 8 token = list(map(int, input().split()))[:-1] 9 for i in range(1, len(token), 2): 10 G[token[0]-1].append((token[i]-1, token[i+1])) 11 12def dfs(node, dist): 13 global max_node, max_dist 14 visited[node] = True 15 if dist > max_dist: 16 max_node = node 17 max_dist = dist 18 for n_node, n_dist in G[node]: 19 if not visited[n_node]: 20 dfs(n_node, dist+n_dist) 21 22max_node = 0 23 24max_dist = 0 25visited = [False]*V 26dfs(0, 0) 27max_dist = 0 28visited = [False]*V 29dfs(max_node, 0) 30 31print (max_dist) 최근에 푼 “1967: 트리의 지름” 덕분에 쉽게 해결할 수 있었다 기억하자 트리의 지름 = (어떤 한 정점에서 가장 먼 점 P)에서 가장 먼 점 사이의 거리

백준 - 14938 : 서강그라운드 (G4)

🧠 Algorithm

1N, M, R = map(int, input().split()) 2 3item = list(map(int, input().split())) 4G = [[] for _ in range(N)] 5for _ in range(R): 6 a, b, c = map(int, input().split()) 7 G[a-1].append((b-1, c)) 8 G[b-1].append((a-1, c)) 9 10def dfs(node, dist): 11 global result 12 if dist > M: 13 return 14 if not visit[node]: 15 result += item[node] 16 visit[node] = True 17 18 for n_node, n_dist in G[node]: 19 dfs(n_node, dist+n_dist) 20 21max_result = 0 22 23for i in range(N): 24 result = 0 25 visit = [False]*N 26 dfs(i, 0) 27 max_result = max(max_result, result) 28 29print (max_result) 분류에 다익스트라, 플로이드-워셜로 되어있지만 DFS로 풀었다 풀이 방법 여기서는 재방문 했다고 해서 탐색을 하지 않으면 안된다 재방문했을때 전에 방문했을 때보다 더 짧은 통로로 들어왔다면 더 많은 아이템을 얻을 수 있기 때문이다 다만, 아이템은 방문할 때마다 얻을 수 있는 것이 아니기 때문에 주의하여야 한다 위의 내용을 질문게시판을 보다가 깨닫고 풀 수 있었다

백준 - 5639 : 이진 검색 트리 (G5)

🧠 Algorithm

풀이방법 1 : 직접 구현 1import sys 2 3sys.setrecursionlimit(10**6) 4class Node: 5 def __init__(self, value): 6 self.value = value 7 self.left = None 8 self.right = None 9 10class BinaryTree: 11 def __init__(self, root): 12 self.root = root 13 14 def insert(self, value): 15 cur_node = self.root 16 while True: 17 if value < cur_node.value: 18 if cur_node.left != None: 19 cur_node = cur_node.left 20 else: 21 cur_node.left = Node(value) 22 break 23 else: 24 if cur_node.

백준 - 1043 : 거짓말 (G4)

🧠 Algorithm

1N, M = map(int, input().split()) 2T = list(map(int, input().split())) 3T = set(T[1:]) 4 5member = [set() for _ in range(N)] 6party = [] 7visit = [False]*M 8 9def explore(n): 10 for i in member[n]: 11 if not visit[i]: 12 visit[i] = True 13 for j in party[i]: 14 explore(j-1) 15 16for i in range(M): 17 lst = list(map(int, input().split())) 18 lst = lst[1:] 19 for j in lst: 20 member[j-1].add(i) 21 party.

백준 - 2448 : 별 찍기 - 11 (G4)

🧠 Algorithm

1import math 2 3N = int(input()) 4K = int(math.log2(N//3)) 5arr = [[' '] * (2*N-1) for _ in range(N)] 6 7 8def solve(depth, bx, by): 9 if depth == 0: 10 for i in range(3): 11 for j in range(i*2+1): 12 arr[by+i][bx+(2-i)+j] = '*' 13 arr[by+1][bx+2] = ' ' 14 else: 15 px = 2**(depth)*3 16 py = 2**(depth-1)*3 17 solve(depth-1, bx+px//2, by) 18 solve(depth-1, bx, by+py) 19 solve(depth-1, bx+px, by+py) 20solve(K, 0, 0) 21for i in arr: 22 print (''.

백준 - 12851 : 숨바꼭질 2 (G4)

🧠 Algorithm

1from collections import deque 2 3position_a, position_b = map(int, input().split()) 4 5q = deque() 6visited = [False]*100001 7result = 0 8cnt = 1 9 10q.append((0, position_a)) 11while q: 12 time, cur = q.popleft(); 13 visited[cur] = True 14 15 if cur == position_b: 16 result = time 17 for i in q: 18 if i == (time, cur): 19 cnt += 1 20 break 21 if cur-1 >= 0 and not visited[cur-1]: 22 q.

백준 - 17144 : 미세먼지 안녕! (G4)

🧠 Algorithm

1R, C, T = map(int, input().split()) 2L = [list(map(int, input().split())) for _ in range(R)] 3 4dx = [0, 1, 0, -1] 5dy = [-1, 0, 1, 0] 6dx2 = [0, 1, 0, -1] 7dy2 = [1, 0, -1, 0] 8 9pur_a = (0, 0) 10pur_b = (0, 0) 11 12for i in range(R): 13 if L[i][0] == -1: 14 pur_a = (i, 0) 15 pur_b = (i+1, 0) 16 break 17 18def diffuse(L): 19 L_ = [[0]*C for _ in range(R)] 20 21 for i in range(R): 22 for j in range(C): 23 if L[i][j] > 0: 24 cnt = 0 25 for k in range(4): 26 px = j+dx[k] 27 py = i+dy[k] 28 29 if 0 <= px < C and 0 <= py < R and L[py][px] !

백준 - 11003 : 최솟값 찾기 (P5)

🧠 Algorithm

1from collections import deque 2N, L = map(int, input().split()) 3A = list(map(int, input().split())) 4 5Q = deque([(A[0], 0)]) 6result = [A[0]] 7 8for i in range(1, N): 9if Q[0][1] == i-L: 10Q.popleft() 11while Q and Q[-1][0] >= A[i]: 12Q.pop() 13Q.append((A[i], i)) 14result.append(Q[0][0]) 15 16print(*result) 문제 N개의 수 A1, A2, …, AN 과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. TC input 12 3

백준 - 1976 : 여행 가자 (G4)

🧠 Algorithm

1N = int(input()) 2M = int(input()) 3 4parent = [i for i in range(N)] 5 6def find(node): 7 if parent[node] != node: 8 parent[node] = find(parent[node]) 9 return parent[node] 10 11def union(a, b): 12 a = find(a) 13 b = find(b) 14 if a < b: 15 parent[b] = a 16 else: 17 parent[a] = b 18 19for i in range(N): 20 for j, item in enumerate(map(int, input().split())): 21 if item: 22 union(i, j) 23 24path = list(map(int, input().

백준 - 11444 : 피보나치 수 6 (G2)

🧠 Algorithm

1def multiply(m1, m2): 2 result = [0, 0, 0, 0] 3 result[0] = (m1[0]*m2[0] + m1[1]*m2[2]) % 1000000007 4 result[1] = (m1[0]*m2[1] + m1[1]*m2[3]) % 1000000007 5 result[2] = (m1[2]*m2[0] + m1[3]*m2[2]) % 1000000007 6 result[3] = (m1[2]*m2[1] + m1[3]*m2[3]) % 1000000007 7 return result 8 9def power(m, n): 10 if (n > 1): 11 m = power (m, n//2) 12 13 m = multiply (m, m) 14 if n % 2 == 1: 15 m = multiply(m, [1,1,1,0]) 16 return m 17 18N = int(input()) 19 20mat = power ([1,1,1,0], N) 21print (mat[1]%1000000007) 문제 n이 주어질 때 n번째 피보나치 수를 구하여라.

백준 - 2638 : 치즈 (G3)

🧠 Algorithm

1from collections import deque 2 3dx = [0, 0, -1, 1] 4dy = [-1, 1, 0, 0] 5 6N, M = map(int, input().split()) 7L = [list(map(int, input().split())) for _ in range(N)] 8 9def check(): 10 q = deque() 11 q.append((0, 0)) 12 13 visited = [[0]*M for _ in range(N)] 14 visited[0][0] = 1 15 16 while q: 17 curX, curY = q.popleft() 18 19 for i in range(4): 20 nX = curX + dx[i] 21 nY = curY + dy[i] 22 23 if 0 <= nX < N and 0 <= nY < M: 24 if L[nX][nY] == 0 and visited[nX][nY] == 0: 25 q.

백준 - 11000 : 강의실 배정 (G5)

🧠 Algorithm

1import heapq 2 3N = int(input()) 4 5L = [] 6for _ in range(N): 7 L.append(tuple(map(int, input().split()))) 8 9L.sort() 10q = [] 11 12heapq.heappush(q, L[0][1]) 13for i in L[1:]: 14 if q[0] > i[0]: 15 heapq.heappush(q, i[1]) 16 else: 17 heapq.heappop(q) 18 heapq.heappush(q, i[1]) 19 20print (len(q)) 문제 강의 개수와 강의 당 시작시간, 종료시간이 주어진다 필요한 강의실 개수를 구하라 (연강 가능)) TC input 3 1 3 2 4 3 5

HackerRank - The Minion Game

🧠 Algorithm

1def minion_game(string): 2 stuart = 0 3 kevin = 0 4 5 for i in range(len(string)): 6 for j in range(i+1, len(string)+1): 7 if string[i] in ['A', 'E', 'I', 'O', 'U']: 8 kevin += 1 9 else: 10 stuart += 1 11 12 if stuart > kevin: 13 print ('Stuart', stuart) 14 elif stuart < kevin: 15 print ('Kevin', kevin) 16 else: 17 print ('Draw') 문제 Kevin과 Stuart가 The Minion 게임을 한다 게임의 규칙은 다음과 같다 문자열 S가 주어질때, 서로 부분 문자열을 만든다 이때, Kevin은 모음으로, Stuart는 자음으로 시작하는 문자열을 만든다 하나 만들때마다 점수를 +1 얻고 점수가 높은 사람이 이긴다 “{게임에서 이긴 사람이름} {이긴 사람의 점수}“를 출력하라 동점이면 “Draw"를 출력하라 TC input BANANA

HackerRank - Merge the Tools

🧠 Algorithm

1def merge_the_tools(string, k): 2 for i in range(0, len(string), k): 3 temp = [] 4 for j in range(i, i+k): 5 if not string[j] in temp: 6 temp.append(string[j]) 7 print (''.join(temp)) 문제 문자열 S와 정수 k가 주어졌을 때, S를 k 길이의 부분 문자열로 나누고, 각 부분 문자열에서 중복되는 문자를 제거한 뒤 출력한다 TC input s = ‘AABCAAADA’, k = 3 ouput AB CA AD

HackerRank - Time Delta

🧠 Algorithm

1from datetime import datetime 2 3def time_delta(t1, t2): 4 5 DATE_FORMAT = '%a%d%b %Y %H:%M:%S %z' 6 7 start = datetime.strptime(t1, DATE_FORMAT) 8 end = datetime.strptime(t2, DATE_FORMAT) 9 10 return str(int(abs(start-end).total_seconds())) 문제 정수 T가 주어지고, “Sun 10 May 2015 13:54:36 -0700"과 같은 형식의 두 시간이 T개 주어진다 두 시간의 차이를 초 단위로 출력한다 이때, 마지막 +0530, -0700과 같은 숫자는 UTC와의 차이를 나타낸다 TC input 2 Sun 10 May 2015 13:54:36 -0700

[모각코24하계] 05 : 계획

👨‍💻 모각코

오늘의 목표 Nginx에서 HTTPS 설정하기

[모각코24하계] 03 : 계획

👨‍💻 모각코

오늘의 목표 RabbitMQ, Celery, Fastapi 연동 정리

[모각코24하계] 02 : 계획

👨‍💻 모각코

오늘의 목표 RAG 이론 정리 OpenSearch를 활용한 Rag 적용

프로그래머로 산다는 것 (리더의 생각) - 쏘카 류석문 CTO님

🏫 학과 공부

개발자는 항상 변화하면서 성장해야 한다 개발자의 지속적인 성장 방법 깔끔한 코드 적절한 논리력 (= 문제 해결 능력) 개발이 완료 됐는지 검증하는 방법 ATDD (Acceptance Test Driven Development) : 고객, 개발자, 테스터 간의 커뮤니케이션을 기반으로 하는 개발 방법론 사용하는 코드만 만들기 (Celler Create) 리팩토링 (Refactoring) 코드 읽기 (Code Review) 알고리즘과 데이터 구조 (Don’t Reinvent The Wheel) 단순한 디자인 (Simple Design) 진화적 디자인 (Evolutionary Design) 협업 (Cooperative Design Design Review) 기술 벤치마킹 (Benchmarking) 이력서에 git repo 제출할 때, 꾸준히 개선하기 위해 고민하고 관리한 repo를 제출하자

6
7
8
9
10