본문 바로가기

분류 전체보기

 (109)
[Python | 파이썬] 백준 2565 전깃줄 [Python | 파이썬] 백준 2565 전깃줄 dp 배열에는 지우지 않을 수 있는 최대 전깃줄 개수를 저장한다. A 전봇대에 위치하는 전봇대들의 인덱스를 i라고 하면, i번째 인덱스까지 존재할 수 있는 최대 전깃줄의 개수는 0번부터 i-1번까지의 전깃줄 중에서 그 전깃줄의 B 전봇대에서의 인덱스가 i번째 인덱스의 값보다 작거나 같은 전깃줄 수의 합 + 1 (i번째 전깃줄) 이다. for i in range(1, n): for j in range(i): if arr[j][1] < arr[i][1]: dp[i] = max(dp[i], dp[j] + 1) 그리고 문제에서 삭제해야하는 전깃줄의 최소 갯수를 물어봤으므로 n - max(dp) 를 출력하면 된다. 더보기 n = int(input()) arr = [..
[Python | 파이썬] 백준 2156 포도주 시식 [Python | 파이썬] 백준 2156 포도주 시식 포도주는 연속으로 3잔을 마실 수 없다. 만약 4번째 포도주를 마신다고 하면 2가지 경우가 가능하다. 1 2 3 4 o o x o => dp[1] + grape[2] + grape[4] => dp[i-3] + grape[i-2] + grape[i] o x o o => dp[1] + grape[3] + grape[4] => dp[i-3] + grape[i-1] + grape[i] 4번째 포도주를 안마신다고 하면 3번째 포도주를 마셨을 때까지의 경우가 최대의 경우이다. 1 2 3 4 o o x x o x o x x o o x ~~ 앞에가 어떻든 간에 3번째 까지의 최대의 값이 4번째로 이어져 온다. dp[4] = dp[3] => dp[i-1] 따라서 3가..
[Python | 파이썬] 백준 1147 RGB 거리 [Python | 파이썬] 백준 1147 RGB 거리 dynamic programming을 이용해 푸는 문제이다. 1번부터 N번 집까지 각각 빨간색, 초록색, 파란색을 색칠하였을 경우 그 다음 번호의 집이 색칠할 수 있는 경우의 수는 2가지가 존재한다. arr[0][0]을 첫번째 집을 빨간색, arr[0][1]을 초록색, arr[0][2]를 파란색을 색칠했을때의 비용이라고 생각한다. 그리고 arr[n-1][0]은 n번째 집을 빨간색, arr[0][1]을 초록색, arr[0][2]를 파란색을 색칠했을때의 비용이라고 생각한다. 1부터 n-1까지 차례대로 반복문을 통해 arr[house][i]에 대해서 i == 0(현재 집을 빨간색으로 칠할때) i == 1(초록) i == 2 (파랑) 각각의 경우의 수에대해서..
[Python | 파이썬] 여행 경로 (프로그래머스 DFS/BFS) [Python | 파이썬] 여행 경로 (프로그래머스 DFS/BFS) 더보기 def solution(tickets): tickets.sort(reverse=True) routes = dict() for t1, t2 in tickets: if t1 in routes: routes[t1].append(t2) else: routes[t1] = [t2] st = ['ICN'] answer = [] while st: top = st[-1] if top not in routes or len(routes[top]) == 0: answer.append(st.pop()) else: st.append(routes[top].pop()) answer.reverse() return answer https://programmers..
[Python | 파이썬] 단어 변환 (프로그래머스 DFS/BFS) [Python | 파이썬] 단어 변환 (프로그래머스 DFS/BFS) 내가 해결한 방법 더보기 answer = int(1e9) def solution(begin, target, words): global answer wdict = {} for word in words: wdict[word] = False if not target in words: return 0 n = len(begin) def dfs(rst, tmp, target): global answer if tmp == target: answer = min(answer, rst) return wdict[tmp] = True for word in words: cnt = 0 for i in range(n): if tmp[i] != word[i]: cn..
[Python | 파이썬] 네트워크 (프로그래머스 DFS/BFS) [Python | 파이썬] 네트워크 (프로그래머스 DFS/BFS) 각 묶음의 번호를 지정해준다고 생각하면된다. 번호가 할당되지 않은 컴퓨터를 만날때마다 BFS를 실행한다. 현재 컴퓨터에서 도달 가능한 컴퓨터들에 한해서는 같은 묶음이니까 같은 번호를 할당해주고, 현재 위치에서 도달 가능한 컴퓨터들을 다 탐색하면 번호를 1증가 시켜서, 번호를 할당하지 않은 새로운 컴퓨터를 만나게 되면 다시 BFS를 실행해준다. visited배열에 방문한 노드의 번호에 해당하는 visited[i]를 True로 갱신해준다. 백준 16234 인구이동 문제의 핵심 아이디어랑 동일하다. https://www.acmicpc.net/problem/16234 더보기 from collections import deque def soluti..
[Python | 파이썬] 타겟넘버 (프로그래머스 DFS/BFS) [Python | 파이썬] 타겟넘버 (프로그래머스 DFS/BFS) 더보기 answer = 0 def solution(numbers, target): n = len(numbers) def dfs(cnt, n, now, target): global answer if cnt == n: if now == target: answer += 1 return # return answer dfs(cnt+1, n, now+numbers[cnt], target) dfs(cnt+1, n, now-numbers[cnt], target) dfs(1, n, numbers[0], target) dfs(1, n, -numbers[0], target) return answer https://programmers.co.kr/learn/c..
[Python | 파이썬] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT) [Python | 파이썬] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT) 유저마다 유저아이디와 닉네임을 갖는데, 유저아이디는 반드시 고유하지만 닉네임은 중복될 수 있다. 따라서 유저아이디를 key로 하고 닉네임을 value로 하는 dictionary를 생성하고 문제에서 주어진 입력대로 answer 배열에 추가하면 된다. 나는 우선 answer배열에 userid + '님이 들어왔습니다.' 형식으로 닉네임 대신 유저아이디를 넣어서 배열을 채워줬다. (만약 처음부터 닉네임 + '님이 들어왔습니다.' 형식으로 배열을 채운다면 중복이 있기 때문에 일단 answer 배열에 추가하고 나중에 수정하는 것이 불가능하다. 닉네임을 변경한 작업이 있었다면 변경해줘야하기 때문에 ) 그리고 answer 배열..

티스토리툴바