티스토리

개발자 도비

검색하기

블로그 홈

개발자 도비

louisus.tistory.com/m

Louisus 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

4883 with 파이썬(-) # 00 01 02 # 10 11 12 # 20 21 22 # 30 31 32 # # 최소값은 간선 한번이 최소임 # 왼쪽값: 10 = sum(01,10) # 중간값: 11 = sum(01,11) # 오른쪽값: 12 = sum(01,12) # 왼쪽값: 20 = min(sum(10,20), sum(11,20)) # 중간값: 21 = min(sum(10,21),sum(11,21),sum(12,21)) # 오른쪽값: 22 = min(sum(11,22),sum(12,22)) test_num = 1 while True: node_num = int(input()) if not node_num or node_num < 2: break # node_num을 1부터 시작하기 위해 routes = [[0]*3] + [li.. 공감수 0 댓글수 0 2020. 8. 13.
3044 with 파이썬 (-) # 1번시작 2번 끝 # 일방통행 # 1~N 마을 # M 개 일방통행 도로 # return 총 경로수 # 9자리 넘으면 뒤의 9자리만 출력 # 무한대 inf - 어떻게 가능?? # 시간 초과... # 메모리 초과... from collections import defaultdict import sys sys.setrecursionlimit(10**3) # n = 노드 개수 # m = 간선 개수 n, m = map(int, input().split()) case = 0 roads = defaultdict(list) inf_ck = False # A->B for _ in range(m): a, b = map(int, input().split()) roads[a].append(b) def dfs(n): glo.. 공감수 0 댓글수 0 2020. 8. 12.
1102 with 파이썬 (-) # 발전소 개수 1 공감수 0 댓글수 0 2020. 8. 12.
6416 with 파이썬 (-) from collections import defaultdict # 에러 # 루트 노드가 2개인 예외가 있을 수 있음 lst = [] while True: temp = list(map(int, input().split())) if temp: if temp[-1] == -1 and temp[-2] == -1: break else: lst.extend(temp) temp = defaultdict(list) cases = [] for i in range(0, len(lst), 2): if lst[i] == 0 and lst[i+1] == 0: cases.append(temp) temp = defaultdict(list) else: temp[lst[i+1]].append(lst[i]) for i, case in.. 공감수 0 댓글수 0 2020. 8. 12.
2629 with 파이썬 # BruteForce로 모든 조건 구하려 했지만 +, - 개수 부여 부분에서 막힘 from itertools import combinations n = int(input()) chu = list(map(int, input().split())) t = int(input()) target = list(map(int, input().split())) n = len(chu) for i in range(2, n+1): for j in combinations(chu, i): # + or - # 사용가능 총 부호 개수 m = len(chu)-1 for tg in target: pass # 1. 최대 무게까지 dp 만듬 # 2. 각 경우의 수에 대해 합 또는 빼기 n = int(input()) chu = list(m.. 공감수 0 댓글수 0 2020. 8. 12.
3101 with 파이썬 # 1. 배열판 만들기 # 2. 움직인 칸 합 # 3. 합 출력 ## 메모리 초과 n, k = map(int, input().split()) jumps = list(input()) fields = [[0]*n for _ in range(n)] # U D L R dirs = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)} answer = [1] def make_zigzag_list(fields, n): cnt = 1 fields[0][0] = cnt change_dir = 0 for i in range(1, n): a = list(range(i+1)) b = list(range(i, -1, -1)) .. 공감수 0 댓글수 0 2020. 8. 12.
거스름돈 with 파이썬 # 첫접근 # Brute Force로 하려했다... # 하지만 이후 조건에서 10, [1,2,3] 주어졌을 때 또 다시 조합을 늘려가야 했기 때문에 풀이 불가 # 5 # 1 * 5 # 1 + 2*2 # 1*3 + 2*1 # 5*1 # 10, [1,2,3,5,10] # 1,2,3,4,5 로 조합하는 방법 from itertools import combinations def solution(n, money): answer = 0 money.sort() for i in range(1, len(money)+1): for m in combinations(money, i): temp = 0 if sum(m) > n: break else: temp = n - sum(m) return answer % 100000000.. 공감수 0 댓글수 0 2020. 8. 8.
블록 이동하기 with 파이썬 from collections import deque def move(cur1, cur2, board): dirs = [(1,0), (0,1), (-1,0), (0,-1)] ret = [] for y, x in dirs: if board[cur1[0]+y][cur1[1]+x] == 0 and board[cur2[0]+y][cur2[1]+x] == 0: ret.append({(cur1[0]+y, cur1[1]+x), (cur2[0]+y, cur2[1]+x)}) rotate = [1,-1] # 가로로 위치해있는 로봇 회전 if cur1[0] == cur2[0]: for r in rotate: if board[cur1[0]+r][cur1[1]] == 0 and board[cur2[0]+r][cur2[1]] =.. 공감수 0 댓글수 0 2020. 8. 7.
외벽 점검 with 파이썬 # return 최소한의 친구들 투입 # 외벽 길이(1~200), 취약 지점 위치(길이:1~15, 원소:0~n-1), 한시간동안 이동가능 거리(길이:1~8, 원소:1~100) # 1. 시작점 선정 # 2. 각 시작점 별 시계 반시계 방향으로 갔을 때 다 들리는 값 구하기 from collections import deque from itertools import permutations # 친구 투입 후 다음 친구 투입 def nxt_idx(queue, d, start_idx=0): # 시작점 start_num = queue[start_idx] # i = 거리 for i in range(1, d+1): try: # 이동 가능 거리 안에서 다음 취약점 포함되는 경우 if queue[start_idx + 1].. 공감수 0 댓글수 0 2020. 8. 7.
정수 삼각형 with 파이썬 # 인덱스 범위 맞추는게 항상 헷갈린다.. # 인덱스 끝에 맞춰서 -1 방식이 마지막 인덱스 -1 경우 보다 인덱스 범위 맞추기 쉬운것같다. def solution(triangle): dp = [[] for _ in range(len(triangle))] dp[0].append(triangle[0][0]) # i = 다음 dp / i-1 = 이전 dp for i in range(1, len(triangle)): # 다음 dp의 범위 for j in range(i+1): # 맨 왼쪽끼리 더하기 if j == 0: dp[i].append(dp[i-1][0] + triangle[i][j]) # 맨 오른쪽끼리 더하기 elif j == i: dp[i].append(dp[i-1][-1] + triangle[i][j.. 공감수 0 댓글수 0 2020. 8. 7.
가장 먼 노드 with 파이썬 from collections import defaultdict, deque def bfs(graph, start, distances, visited): q = deque([start]) visited[start] = True while q: current = q.popleft() for adj in graph[current]: if not visited[adj]: visited[adj] = True q.append(adj) distances[adj] = distances[current] + 1 def solution(n, edge): # 그래프 만들기 graph = defaultdict(list) visited = [False] * (n+1) for x, y in edge: graph[x].append.. 공감수 0 댓글수 0 2020. 8. 6.
단속 카메라 with 파이썬 - 포함 관계에 대한 이해 필요 # return 최소 카메라 설치 갯수 # 차량: 1~ 10000 # [진입, 진출] # 진입, 진출 지점에 카메라 설치도 만난 것 # -30000 ~ 진입, 진출 ~ 30000 # 교점이 많은 부분에 설치하는게 이득 from copy import deepcopy def solution(routes): answer = 0 n = len(routes) check = [0] * n start = sorted(routes, key=lambda x: x[0])[0][0] end = sorted(routes, key=lambda x: x[1])[-1][1] checked = set() # 전체 구간 for idx in range(start, end+1): new_checked = .. 공감수 0 댓글수 0 2020. 8. 6.
추석트래픽 with 파이썬 def solution(lines): S, E = [], [] total_lines = 0 for line in lines: total_lines += 1 d, s, t = line.split(' ') t = float(t[:-1]) hh, mm, ss = s.split(':') seconds = float(hh) * 3600 + float(mm) * 60 + float(ss) E.append(seconds + 1) S.append(seconds - t + 0.001) S.sort() cur_traffic = 0 max_traffic = 0 cnt_E = 0 cnt_S = 0 while ((cnt_E < total_lines) and (cnt_S < total_lines)):.. 공감수 0 댓글수 0 2020. 8. 6.
2*n 타일링 with 파이썬 # 규칙 찾기 # 시간 초과... def solution(n): if n == 1: return 1 elif n == 2: return 2 dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] % 1000000007 # 나머지 연산 과정을 for문 안에서 미리 처리하니까 효율성 통과 def solution(n): if n == 1: return 1 elif n == 2: return 2 dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3,n+1): dp[i] = (dp[i-1] + dp[i-2]) % 1000000007 return dp[n] %.. 공감수 0 댓글수 0 2020. 8. 6.
섬 연결하기 with 파이썬 Kruskal 알고리즘 탐욕적인 방법을 이용해서 그래프의 모든 정점을 최소 비용으로 연결하는 방법 처음 시작하는 노드로 부터 하나의 간선을 선택해 간다. # 최소 비용으로 모든 섬 통행 # A -> B -> C # 오류 def solution(n, costs): total = 0 island = set() roots = [] costs = sorted(costs, key=lambda x: -x[2]) # 경로 리스트 while len(island) < n: r1, r2, c = costs.pop() if r1 in island and r2 in island: continue island.add(r1) island.add(r2) roots.append((r1,r2,c)) return total # 방문 리.. 공감수 0 댓글수 0 2020. 8. 6.
순위 with 파이썬 from collections import defaultdict def solution(n, results): answer = 0 win, lose = defaultdict(set), defaultdict(set) for result in results: # 키 = 패자 / 값 = 승자 lose[result[1]].add(result[0]) # 키 = 승자 / 값 = 패자 win[result[0]].add(result[1]) for i in range(1, n+1): for winner in lose[i]: # win[i]: 승자 i가 이긴 패자 추가 win[winner].update(win[i]) for loser in win[i]: # lose[i]: 패자 i가 진 승자 추가 lose[loser].u.. 공감수 0 댓글수 0 2020. 8. 6.
가장 긴 팰린드롬 with 파이썬 # 홀수만 가능 # 시간 초과오류 def solution(s): answer = 0 n = len(s) if n == 1: return 1 # 가장 긴 길이부터 시작 s_len = n while s_len > 1: if n-s_len == 0: v = s[:s_len] if palindrome_check(v): return s_len else: for i in range(n-s_len): v = s[i:s_len+i] if palindrome_check(v): return s_len s_len -= 1 return 1 def palindrome_check(v): mid = (len(v)//2) # 짝수 길이 if len(v)%2 == 0: if v[0:mid] == v[-1:mid-1:-1]: retur.. 공감수 0 댓글수 0 2020. 8. 6.
n으로 표현 with 파이썬 # 첫 접근 # +, -, * , // # 이전 경우의 수에 대해서만 다음 과정을 반복함... # 오답 def solution(N, number): answer = 1 dp = [[5]] while answer number: continue else: temp.append(v//N) temp.append(int(str(v)+str(N))) answer += 1 if number in temp: return answer dp.append(temp) return -1 def solution(N, number): dp = [0, {N}] if N == number: return 1 for i in range(2, 9): case_set = {int(str(N)*i)} for j in range(1, i//2+.. 공감수 0 댓글수 0 2020. 8. 6.
등굣길 with 파이썬 # m 열 n 행 # (1,1) (m,n) def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] # 웅덩이 체크 -> -1 for x, y in puddles: dp[y][x] = -1 # 세로줄 채우기 for y in range(1, n+1): # 이전 값이 웅덩이이면 종료 if dp[y-1][1] == -1: break else: dp[y][1] = 1 # 가로줄 채우기 for x in range(1, m+1): if dp[1][x-1] == -1: break else: dp[1][x] = 1 for i in range(2, n+1): for j in range(2, m+1): if dp[i][j] == -1: continue # 둘다 .. 공감수 0 댓글수 0 2020. 8. 6.
자물쇠와 열쇠 with 파이썬 def rotate(maps): return [list(reversed(i)) for i in zip(*maps)] def solution(key, lock): hole = 0 # hole 개수 총합 for y in range(len(lock)): for x in range(len(lock[0])): if lock[y][x] == 0: hole += 1 for _ in range(4): # 길이가 3 인경우 -2 ~ 5 for start_y in range(-len(key)+1, len(lock)): for start_x in range(-len(key)+1, len(lock[0])): # 자물쇠와 lock 일치하는 개수 ck = 0 match = True for y in range(start_y, st.. 공감수 0 댓글수 0 2020. 8. 6.
가장 큰 증가 부분 수열 [11055] with 파이썬 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net from copy import deepcopy n = int(input()) a = list(map(int, input().split())) # dp[i] : i 까지 왔을 때, 합의 최대 dp = deepcopy(a) rev = [i for i in range(n)] idx = 0 # 현재위치 # for i in range(1, n):.. 공감수 0 댓글수 0 2020. 6. 5.
2차원 배열의 합 [2167] with 파이썬 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 � www.acmicpc.net # 누적합 - 합들의 누적을 미리 구해놓는 것 a = [i for i in range(10)] print(a) for i in range(1, 10): a[i] = a[i-1] + a[i] print(a) # dp[i] = i 까지의 합 # i 부터 j 까지의 합은 dp[i] - dp[i-1] ------- 풀이: # 2 차원 배열의 누적합 n, m = map(in.. 공감수 0 댓글수 0 2020. 6. 5.
배열 돌리기 4 [17406] with 파이썬 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net from copy import deepcopy n, m, k = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(n)] q = [list(map(int, input().split())) for _ in range(k)] dx, dy = [1,0,-1,0], [0,-1,0,1] .. 공감수 0 댓글수 0 2020. 6. 5.
2048 (Easy) [12100] with 파이썬 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net from copy import deepcopy n = int(input()) board = [list(map(int, input().split())) for _ in range(n)] # logic 생각 # 상하좌우 이동이 아닌 맵의 방향을 바꿔가면서 한방향으로만 보내는 방식으로 생각 # 90도 회전 def rotate(b, n): nb = deepcopy(b) for.. 공감수 0 댓글수 0 2020. 6. 4.
Mooyo Mooyo [16768] with 파이썬 https://www.acmicpc.net/problem/16768 16768번: Mooyo Mooyo In the example above, if $K = 3$, then there is a connected region of size at least $K$ with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this: 0000000000 0000000300 0054000300 1054500030 220000 www.acmicpc.net # Flood Fill # Flood Fill 처리한 후 어떻게 처리할 것인가 # Flood Fill # Flood Fi.. 공감수 0 댓글수 0 2020. 6. 4.
나무 재테크 [16235] with 파이썬 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net n (땅 넓이) m (나무개수) k (종료 년) n개 줄 -> A[r][c] m개 줄 -> 나무 정보 (x,y 위치, z 나이) 봄 – 양분 -= 나이 / 나이 += 1 / 어린 나무 먼저 양분 흡수 (정렬) 여름 – 양분 += 죽은 나무 나이 // 2 가을 – 나이 % 5 == 0: -> 8방향에 나이 1 나무 추가 / 벗어나면 추가 X 겨울 – A[r][c] 만큼 양분 추가 K.. 공감수 0 댓글수 0 2020. 6. 3.
과외맨 [5213] with 파이썬 https://www.acmicpc.net/problem/5213 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이 www.acmicpc.net 출처: https://rebas.kr/733 [PROJECT REBAS] 우선 주어지는 입력 데이터를 2차원 인접 행렬로 변환한다. 하나의 타일은 2 조각으로 나누어져 있으므로, 세로 N개 가로 N*2개이다. 따라서 인접 행렬을 a[N][N*2]로 선언한다. 입력 데이터를 인접 행렬에 넣을 때, 홀수 줄, 짝수 줄에 따라 다르게 넣어야 한다. 홀수 줄에서는 2*N개의 데이터를 모두 넣는다. 짝수 줄에서는 앞뒤로.. 공감수 0 댓글수 0 2020. 6. 2.
바이러스 [2606] with 파이썬 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net n = int(input()) m = int(input()) adj = [[] for _ in range(n+1)] visited = [False] * (n+1) cnt = 0 for _ in range(m): x, y = map(int, input().split()) adj[x].append(y) adj[y].append(x) def dfs(now_pos): global cnt cnt += 1 v.. 공감수 0 댓글수 0 2020. 6. 2.
벽 부수고 이동하기 [2206] with 파이썬 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net from collections import deque n, m = map(int, input().split()) maps = [list(map(int, input())) for _ in range(n)] dist = [[[0, 0] for _ in range(m)] for _ in range(n)] # d / u / r / l dirs = [(1,0), (-1,0), .. 공감수 0 댓글수 0 2020. 6. 2.
탈출 [3055] with 파이썬 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치�� www.acmicpc.net from collections import deque r, c = map(int, input().split()) forest = [] water = [] for i in range(r): arr = input() for j in range(len(arr)): if arr[j] == 'D': # finish finish = (i,j) elif arr[j] == 'S': start = [(i,j)] elif .. 공감수 0 댓글수 0 2020. 6. 2.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.