티스토리

Breath everything

검색하기

블로그 홈

Breath everything

tipsyziasu.tistory.com/m

이것 저것

구독자: 9

방명록 방문하기

주요 글 목록

[백준] 17070 파이프 옮기기1(Python) 1. 생각 정리 그림만 보면 되게 복잡한 것 같지만 파이프의 끝부분이 가리키는 좌표 이동하는 느낌으로 생각하면 될 듯 이전 단계에서 어떤 방향으로 움직였는지가 다음 방향 선택에 영향을 미친다. 가로 이동 -> 이전에 대각선 or 가로 세로 이동 -> 이전에 대각선 or 세로 대각선 이동 -> 이전에 대각선 or 가로 or 세로 2. DFS 풀이(시간 초과) def dfs(pos): global cnt x, y, z = pos # n,n 도달 if x == n - 1 and y == n - 1: cnt += 1 # 가로 세로 대각선의 경우 대각선 이동 if x + 1 < n and y + 1 < n: if graph[x + 1][y + 1] == 0 and graph[x][y + 1] == 0 and gr.. 공감수 0 댓글수 0 2021. 10. 23.
[백준] 2655 가장높은탑쌓기(Python) 1. 생각정리 탑을 쌓을 때 고려해야 하는 사항은 세 개다. 무거운 것은 무조건 아래 밑면이 넓은 것은 무조건 아래 위의 두 조건들을 만족시키면서 가장 높은 탑을 쌓을 수 있어야 함 일단 '밑면의 넓이' 혹은 '무게' 중 하나에 대해 정렬을 해준 뒤 코드를 짜면 생각해야 할 조건이 하나 줄어든다. 그리고 dp를 이용해서 하나씩 영역을 확장시키며 쌓을 수 있는 가장 높은 높이를 구할 수 있지 않을까? 여기서 "첫 번째까지 고려한 최대 높이는 dp [1]에", "두 번째까지 고려한 최대 높이는 dp [2]에"... 이렇게 dp를 채운 뒤 dp리스트의 최댓값이 쌓을 수 있는 최대 높이이다. 그리고 mapp과 dp를 바탕으로 하나씩 기억을 더듬어가면 문제가 원하는 답을 도출할 수 있다. 2. 성공 코드 N = .. 공감수 0 댓글수 0 2021. 10. 23.
연속하는 자연수의 곱? (Python) 1. 문제 - 연속하는 자연수 두 개 이상 곱해서 만들 수 있는 값을 크기 순으로 나열한 수열 arr가 있다. ex) 2, 6, 12, 20, 24, 30, 42... - 자연수 n이 매개변수로 주어질 때 arr [n]을 return 해주는 함수 만들기 - n은 1~10^6 2. 풀이 - 일단 arr의 요소들을 나열해보며 규칙을 발견해보자 (0) 1*2 = 2 (1) 2*3 = 6 (2) 3*4 = 12 (3) 4*5 = 20 (4) 2*3*4 = 24 (5) 5*6 = 30 (6) 6*7 = 42 (7) 7*8 = 56 (8) 3*4*5 = 60 (9) 8*9 = 72 (10) 9*10 = 90 (11) 10*11 = 110 (12) 4*5*6 or 2*3*4*5 = 120 (13) 11*12 = 13.. 공감수 0 댓글수 1 2021. 10. 18.
[프로그래머스] 해시 > 완주하지 못한 선수 1. 생각 정리 완주를 못한 사람은 무조건 한 명 존재 participant 리스트의 길이 = completion 리스트의 길이 +1 2. 성공 코드(리스트 sort를 통한 방법) 일단 participant, completion 리스트를 정렬한 뒤 쭉 비교 비교하다 같은 인덱스에 있는 값이 다르면 return participant [i] def solution(participant, completion): participant.sort() completion.sort() for i in range(len(completion)): if participant[i] != completion[i]: return participant[i] return participant[-1] #무조건 완주 못한 사람은 한명 .. 공감수 0 댓글수 0 2021. 10. 14.
[프로그래머스] 해시 > 위장(Python) 1. 생각정리 clothes 2차원 배열에는 (종류, 이름) 형식으로 스파이가 가지고 있는 옷에 대한 정보가 저장되어 있음 만들어질 수 있는 옷의 조합은 (각 종류별로 옷 종류+1을 다 곱한 값 -1) 2. 96.4/100 코드 set란 2차원 리스트에 옷에 대한 정보들을 저장 1행에는 옷의 종류들을 다 저장 2행부터는 (2행->1행 1열 옷 종류의 옷 이름, 3행->1행 2열 옷 종류의 옷 이름...) 이런 느낌으로 저장 정답을 도출할 때는 2행부터 끝까지 훑으며 각 행의 리스트 길이를 활용하여 계산 근데 내가 코드를 작성하고도 다소 복잡하다는 느낌이 들었음 def solution(clothes): set = [[] for _ in range(30)] #1행에는 옷의 유형, 2행부터는 옷의 종류를 유형.. 공감수 0 댓글수 0 2021. 10. 14.
[백준] 1012 유기농 배추(Python) 1. 생각 정리 전체 map에서 배추가 심어져 있는 위치를 입력받고, 몇 개의 지렁이가 필요한지 구하는 문제 지렁이는 인접한 배추로 이동할 수 있기 때문에 연결되어있는 배추 지역에는 지렁이가 하나만 있어도 됨 결국 전체 map에 0(배추x), 1(배추 o)로 입력을 받고 섬처럼 생긴 1 지역이 몇 개인지? 구하는 접근을 가지면 됨 DFS와 BFS 둘 다 활용하여 풀어보자 2. BFS 시간초과 코드 한번 탐색한 부분은 다시 탐색하지 않게 전체 map과 같은 크기인 visited 리스트를 따로 만들어서 정보를 관리했더니 시간 초과가 떴다. #bfs 시간초과 from collections import deque def bfs(start): q=deque() q.append(start) dir = [(-1,0).. 공감수 0 댓글수 0 2021. 10. 13.
[백준] 2606 바이러스(Python) 1. 생각정리 문제를 좀 풀다 보니까 대충 감은 오는 것 같다 연결 정보는 이차원 리스트에 (1행에 1과 연결된 요소들 다 넣기, 2행에 2와 연결된 요소들 다 넣기...)의 느낌으로 입력받고, n+1 크기의 일차원 리스트를 통해 바이러스에 걸리는 것을 확인했는지 여부를 체크해준다 컴퓨터의 수가 적으므로, DFS로 모든 연결정보를 탐색하고, visited정보를 바꿀 때마다 결괏값+=1 해주어 최종 바이러스 걸린 컴퓨터 개수를 도출한다 2. 코드 구현 from collections import deque #컴퓨터의 수 1 공감수 0 댓글수 0 2021. 10. 12.
[백준] 1697 숨바꼭질(Python) 1. 생각 정리 수빈이의 위치에서 동생의 위치까지 무조건 동생과 가까워지는 루트만 따라가면 오히려 시간이 오래 걸릴 수도 있다. 그러므로 각 프로세스마다 (프로세스 단계 * 3)만큼 다양해지는 모든 경우를 고려하여 그중 동생의 위치까지 갔을 때 지금까지 소요된 시간 출력 크기가 100001인 일차원 리스트에 각 위치마다 시간이 얼마나 걸렸는지 갱신하며 동생을 찾을 수 있는 가장 빠른 시간을 구하기 2. 메모리 초과 코드 #메모리 초과 from collections import deque N,K = map(int, input().split()) def bfs(n,k): q = deque([N]) result = 0 count = 1 while q: pos = q.popleft() if pos == K: p.. 공감수 0 댓글수 0 2021. 10. 12.
[백준] 1260 DFS와 BFS(Python) 1. 생각 정리 처음에 간선 정보 입력을 2차원 리스트에 [[1,2], [1,3]]이런 식으로 담으려 했는데 문제를 더 간단히 풀기 위해서는 빈 2차원 리스트를 생성한 뒤 1행에 1과 연결된 정점 넣어주기, 2행에 2와 연결된 정점 넣어주기... 의 느낌으로 입력받는 게 더 편함 visited 리스트를 따로 만들어서 이미 탐색된 정점에 대한 정보를 관리 DFS의 경우에는 재귀함수로, BFS의 경우에는 deque를 이용하여 구현 2. 코드 구현 from collections import deque #정점 개수 N, 간선 개수 M, 탐색 시작 정점번호 V N, M, V = map(int, input().split()) mapp = [[] for _ in range(N+1)] #두개의 정점이 연결되어있다는 간.. 공감수 0 댓글수 0 2021. 10. 12.
[백준] 11053 가장 긴 증가하는 부분 수열(Python) 1. 생각 정리 무조건 다음 숫자가 지금 보다 크다고 해서 수열에 포함시키면 정답을 구하지 못할 수도 있다 수열의 시작부터 전체로 확장해나가며 가장 긴 수열의 길이를 찾아보자 길이가 4인 [10,20,10,30] 수열이 있으면 [10]이면 1, [10,20]이면 2, [10,20,10]이면 2, [10,20,10,30]이면 3처럼 확장해나가며 정답을 도출해보자 2. 코드 구현 N = int(input()) arr = list(map(int, input().split())) dp = [1]*N for i in range(1,N): for j in range(i): if arr[j]dp[i]: dp[i]+=1 print(max(dp)) 공감수 0 댓글수 0 2021. 10. 11.
[백준] 12865 평범한 배낭(Python) 1. 문제 조건 N개의 물건이 있고 각 물건은 무게 W와 가치 V를 가짐 무게 K까지 담을 수 있을 때 물건의 가치합 최대값 구하기 2. 풀이 전 생각정리 각각의 물건을 한번씩 훑으며 가능한 모든 경우에 대한 가치합을 리스트에 저장한다. 무게 7까지 담을 수 있고 물건 2개의 (무게, 가치)가 (2,3), (4,2)라면 3 3 2 5 이런 식으로 저장하며 물건들의 가치합 최댓값은 5 임을 알 수 있다. 무게 합이 K를 초과하는 경우에는 담을 수 없음을 고려한다. 3. 테스트 케이스만 통과한 코드 N, K = map(int, input().split()) mapp = [] for _ in range(N): W, V = map(int, input().split()) mapp.append([W,V]) dp =.. 공감수 0 댓글수 0 2021. 10. 11.
[백준] 1495 기타리스트 (Python) 1. 문제 조건 곡의 개수 N, 시작 볼륨 S, max 볼륨 M 매번 곡 연주를 시작하기 전에 볼륨 조정을 하는데 볼륨 조정이 가능한 값이 V리스트에 담겨있음 ex) max 볼륨이 10, 시작 볼륨이 5, V[0]이 3이면 될 수 있는 볼륨 값은 2 or 8 2. 풀이 전 생각정리 볼륨 조정이 들어갈 때마다 가능한 볼륨의 가짓수는 2배로 늘어난다. 단 가능한 볼륨값 범위 안에 속하지 않은 옵션들은 없애줘야 한다. 볼륨 조정이 있을 때마다 가능한 볼륨의 크기를 담고, 다음 볼륨 조정이 있을 때 다시 확장시키는 방법? (N+1)*(M+1) 크기의 0으로 초기화된 리스트를 만들어 볼륨 조정을 하나씩 해가며 발생할 수 있는 경우를 1로 표시해놓기? 3. 메모리 초과 뜬 코드 볼륨 조정을 하기 전마다 가능한 볼륨.. 공감수 0 댓글수 0 2021. 10. 5.
[백준] 9251 LCS (Python) 1. 문제 조건 첫째줄과 둘째 줄에 비교할 수열이 주어짐(각각의 길이는 같지 않을 수 있음)(최대 1000글자(알파벳 대문자)) 문자열을 비교했을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기 2. 풀이 전 생각정리 수열 x와 y가 주어졌을 때 (x[0]과 y전부 비교하여 dp 갱신, x[1]과 y전부 비교하여 dp 갱신...) 이런 식으로 차근차근 dp를 갱신해보자 dp의 크기는 (x의 길이+1) * (y의 길이+1) / 처음에는 다 0으로 채워넣어주기 이중 for문을 돌면서 두 가지 상황이 발생 x의 값과 y값이 같을 때 dp[i][j] = dp[i-1][j-1]+1 x의 값과 y값이 같지 않을 때 dp[i][j] = max(dp[i][j-1], dp[i-1][j]) dp를 다 갱신하고 dp.. 공감수 0 댓글수 0 2021. 10. 5.
SQL 개발자(SQLD) 42회 시험 후기 제가 생각했을 때 이번 시험의 난이도는 중? 정도였던 것 같습니다. 처음 본시험이긴 했지만, 이 시험의 바이블이라고 불리는 노란 책과 비슷한 유형이 많이 나왔고, 기본적인 문제들만 실수 없이 맞혀주면 평균 60점은 쉽게 넘을 수 있었던 시험이라고 느꼈기 때문입니다. 아직 시험 결과 발표가 난 것도 아니기 때문에 간단하게 시험장 분위기 & 제가 단기 목표를 잡고 공부했던 방법 에 대해 이야기 해보겠습니다. [시험장 분위기] 시험 시작 30분 전까지 입실 완료(조금 늦어도 봐주는 듯?) 시험 시작 30분 이후부터 퇴실 가능(몇몇 분들은 이때 나가시는 듯) 객관식은 컴싸로 마킹, 주관식은 검은색 볼펜으로 작성 엄청 고차원적인 개념을 물어보는 문제가 없고, 암기가 제대로 안되었다면 틀릴 수밖에 없는 문제가 많다.. 공감수 0 댓글수 0 2021. 9. 6.
[백준] 17472 다리만들기2 (Python) 1. 문제 조건 지도는 NxM 이차원 격자(1 공감수 0 댓글수 0 2021. 8. 24.
[알고리즘] 크루스칼 알고리즘(Kruskal's algorithm) 1. 크루스칼 알고리즘 동작 원리...? a) 간선의 가중치를 오름차순으로 sort b) (sort 되었으니까) 간선을 하나씩 확인하며 사이클 발생 O: MST에 포함 X 사이클 발생 X: MST에 포함 O c) 모든 간선에 대해 b) 과정을 해줌 사실 수업을 들을 때도 말로만 설명을 들으니까 확실히 이해가 되지 않아서 코드를 짠 후, 그 코드를 분석해보았다. 2. 크루스칼 알고리즘 코드 분석 graph = { 'vertices':['A','B','C','D','E','F','G'], 'edges':[ (7, 'A', 'B'), (5, 'A', 'D'), (7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (8, 'C', 'B'), (5, 'C', .. 공감수 0 댓글수 0 2021. 8. 23.
[자료구조] 신장트리(Spanning Tree) & 최소 신장 트리(MST) 1. 신장 트리(Spanning Tree)란...? Original 그래프에서 다음의 조건들을 만족시키는 그래프 -> (모든 노드가 연결 / 트리의 속성 만족(사이클 X)) 신장 트리 조건 사이클 X Original 그래프의 모든 노드 포함 모든 노드 연결 2. 최소 신장 트리(MST)란...? Minimum Spanning Tree 신장 트리 중에서, 간선의 가중치 합이 최소인 것 토목, 통신 등등 다양한 분야에서 활용 가능 공감수 0 댓글수 0 2021. 8. 21.
SQL 개발자(SQLD) 독학 시작(2주반 단기) Why SQLD...? 사실 어쩌다가 이 시험에 신청하게 된지는 잘 모르겠습니다ㅎㅎ 데이터베이스를 다루는 SQL에 대한 어느 정도의 개념은 가져야 한다는 생각이 들긴 했는데 뭐부터 시작해야 할지도 막막해서 에라이 모르겠다~~ 심정으로 신청했습니다. 근데 막상 시험을 신청하고 보니 SQLD 시험이 제가 생각했던 것 처럼 SQL로 개발을 막 하는 느낌보다는 데이터 모델에 대한 이해, SQL에 대한 이해에 대한 내용이 주를 이루더라고요 SQL은 프로젝트 하다가 필요에 의해 가끔 써보고 정보처리기사 필기시험을 보면서 문법을 몇 번 훑은 게 다입니다ㅎㅎ 과연 남는게 있을지에 대한 의문도 있지만 일단 해보는 게 안 하는 것보다는 낫지 않을까? 란 생각입니다. 공부계획...? 개념서 혹은 인강을 좀 찾아봤는데, 합격.. 공감수 0 댓글수 0 2021. 8. 18.
[HTML] 기본정리(2) DOCTYPE이란...? HTML에는 여러 종류가 존재하기 때문에 DOCTYPE을 선언하여 올바른 출력을 도와줌 HTML5가 나온 현시점에서는 아래에 보이는 DOCTYPE으로 단일화되었음 상대 경로 태그 활용으로 간단한 웹페이지 만들기 [index.html(main)] '몸풀기' 텍스트를 클릭하면 1.html로 이동 운동순서 몸풀기 조깅하기 근력운동하기 몸풀기 몸을 잘 풀어야 부상을 예방할 수 있다 [1.html] '운동순서' 텍스트를 클릭하면 index.html로 이동 운동순서 몸풀기 조깅하기 근력운동하기 몸풀기 몸을 잘 풀어야 부상을 예방할 수 있다 주요 태그 [ 태그] paragraph의 줄임말로 단락을 표현 [ 태그] a forced line break의 줄임말로 줄 바꿈 기능(직접 줄 바꿈) [.. 공감수 0 댓글수 0 2021. 8. 18.
[HTML] 기본 정리(1) HTML(HyperText Markup Language)이란...? 웹을 통해 볼 수 있는 문서를 만들 때 사용 Hypertext: 다른 문서를 연결하고 있는 문서의 일부분 ex) 네이버 영어사전에 happy를 검색하여 보다가 동의어인 delighted단어를 클릭하면 delighted에 관한 정보가 있는 페이지로 이동 가능 Markup Language: Mark 혹은 Tag로 둘러싸인 언어로 Mark 혹은 Tag를 통해 문서나 데이터 구조를 명시 ex) 오늘의 목표 이면 '오늘의 목표'가 큰 제목임을 의미 태그 여기로 이런 느낌으로 코드를 작성했을 때, '여기로' 텍스트를 클릭하면 밑줄 친 곳으로의 이동이 가능합니다. 상대 경로: 현재 웹페이지의 html 문서를 기준으로 경로를 인식 My name is .. 공감수 0 댓글수 0 2021. 8. 18.
[WEB] HTTP(HyperText Transfer Protocol)란...? HTTP(HyperText Transfer Protocol)란...? Web browser와 Web server가 콘텐츠를 주고받기 위해서 사용하는 통신 규칙 크게 Request와 Response를 위한 메시지로 구분되어 있음 HTTP Request...? 첫 번째 줄은 Request Line ①GET /②check.html ③HTTP/1.1 ①: request method, GET은 요청 URI의 정보를 가져오는 의미 ②: 웹서버에게 request 하는 정보가 무엇인지 ③: 웹브라우저가 사용하고 있는 HTTP version 첫 번째 줄 아래부터는 Request Headers Header에 대한 정보가 적혀있음 Host: request 하려는 서버 호스트 이름 User Agent: 웹 브라우저의 다른 이.. 공감수 0 댓글수 0 2021. 8. 16.
For the sake of 활용, 의미 최근에 강화 학습(reinforcement learning) 공부를 하다가 이런 문장을 발견했습니다. When for the sake of computational efficiency we prefer to compute the expected value by using sampling and Monte Carlo simulation; e.g., approximate an integral or a huge sum of numbers by a Monte Carlo estimate (의역하면) 계산 효율을 높이기 위해서 sampling과 Monte Carlo simulation을 사용하여 기댓값을 구하는 방법이 선호됩니다. 여기서 나온 'for the sake of'란 표현을 많이 보기는 했는데 정확히 어떤.. 공감수 0 댓글수 0 2021. 8. 13.
[Python] enumerate 함수란...? enumerate 함수...? 순서가 있는 자료형을 입력받아서 인덱스 값 포함하는 enumerate 객체를 반환 리스트의 원소에 순서값을 부여 반복문에서 인덱스와 데이터를 함께 처리해야 할 때 자주 사용됨 soldier = ['지민', '용규', '지수', '진수'] for index, name in enumerate(soldier): print("{}번째 훈련병은 {}입니다.".format(index+1,name)) #1번째 훈련병은 지민입니다. #2번째 훈련병은 용규입니다. #3번째 훈련병은 지수입니다. #4번째 훈련병은 진수입니다. 공감수 0 댓글수 0 2021. 8. 13.
[Python] Lambda 표현식란...? Lambda 표현식 형태 lambda 인자 : 표현식 함수를 정의하지 않고 일회성으로 만들어서 사용 가능 x의 y승을 return 해주는 lambda 식 example (lambda x,y : x**y)(2,4) Lambda 표현식 활용 일반적인 함수 def grade(score): if score>=90: return 'A' else: return 'B' grade(85) lambda 표현식 grade = lambda score: 'A' if score>=90 else 'B' #lambda 표현식에는 elif를 쓸 수 없음 grade(85) 공감수 0 댓글수 0 2021. 8. 13.
[Python] iter, next 내장함수 Iterable이란...? 반복할 수 있는 객체 예로는 String, List, Dictionary, Set 객체가 있음 dir(객체)를 실행했을 때 __iter__ 매서드가 존재하는지 여부를 확인하여 객체가 iterable 한 지 확인할 수 있음 iter 함수란...? 객체의 __iter__ 메서드를 호출 iter(호출가능한(callable) 객체, 반복을 끝낼값)의 형태로 사용 ##callable: 객체()이런 형태로 사용 가능한지, callable(객체)를 통해 callable 여부를 확인 가능 #0~7사이의 random값이 출력되다가 random값이 3이 되면 출력을 멈춤 #iter()를 사용하려면 callable한 객체를 넣어줘야하기 때문에 lambda 사용 import random for i .. 공감수 0 댓글수 0 2021. 8. 13.
Nginx란...? AWS에서 EKS파트를 공부 중인데, 쿠버네티스를 활용하여 Nginx 서비스를 배포해야 하는 과제를 받았습니다. 살면서 처음 들어보는 단어입니다... Nginx...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 깊게는 아니더라도 대충 뭐하는 놈인지 공부하며 정리해봤습니다. Nginx(엔진엑스)란...? 요즘 널리 많이 사용되는 웹 서버용 오픈 소스 소프트웨어 웹 서버란...? 웹 서버용 오픈 소스 소프트웨어 웹 서버...? -> 정적 파일에 대한 응답을 처리 Why 웹 서버...? -> WAS는 동적인 처리를 담당한다. 단순한 정적 파일에 대한 처리를 웹 서버에서 담당하여 WAS의 짐을 줄여주기 위함 Why Nginx...? 빠르다 -> 다른 웹서버에 비해 초당 요청 처리 속도가 현저히 빠름 리버스 프록시로 사용 가능 ->.. 공감수 0 댓글수 0 2021. 8. 12.
[AWS] EC2 최근에 AWS를 공부하며 토이 프로젝트를 진행하고 있습니다. VPC의 public subnet에 EC2 서비스를 통해 NAT instance를 생성하여 Bastion Host를 겸할 수 있게 설계를 해봤는데, EC2가 과연 어떤 서비스인지 정확히 이해가 안 되어 한번 정리해봤습니다. EC2(Elastic Cloud Compute)...? '클라우드 상에 있는 가상의 컴퓨터'라고 생각하면 이해하기 쉬움 AWS에서는 사용자들이 쉽게 '클라우드상에 있는 컴퓨팅 파워를 유연하게 빌려서 사용고, 쓴 만큼 가격을 지불할 수 있도록 하는 서비스라고 보면 됨 AWS 서비스를 사용하는 사용자 입장에서는 EC2가 Server 혹은 Web Hosting Server의 역할 ##만약에 내가 운영하고 있는 웹 서비스가 AWS를.. 공감수 0 댓글수 0 2021. 8. 10.
[외부 강의] 강화학습(Reinforcement Learning)(1) 1. 강화 학습(Reinforcement Learning)이란...? '궁극적인 목표를 이루기 위해서 현 상황에서 어떤 input을 넣어야 할까?'란 문제에 대한 해답을 찾으려는 학습 어린아이가 시행착오를 통해 학습하는 방법과 비슷한 느낌 2. 강화학습(Reinforcement Learning)의 특징 Supervised Learning과 다르게 Supervisor(정답을 알려주는 사람)이 없고 reward signal만이 존재 Feedback이 즉각적이지 않을 수 있음 어떻게 fitting하느냐에 따라 제공받는 데이터가 다를 수 있음 3. 강화학습(Reinforcement Learning) 용어 정리 Agent: 모델 / cumulative result를 maximize 하는 것을 목표로 함 Rewar.. 공감수 0 댓글수 0 2021. 8. 9.
[알고리즘] 깊이 우선 탐색(DFS) (Python) 1. DFS란...? 정점의 자식들을 먼저 탐색 2. 구현 전 생각정리 탐색할 그래프를 딕셔너리와 데크를 활용하여 구현해보자 need_visit 데크의 오른쪽에서 하나씩 node를 뽑아오며 탐색하면 최대 깊이까지 탐색하고 다시 올라오는 느낌으로의 탐색이 가능 3. 코드 구현 from collections import deque graph = dict() graph['A'] = deque(['B', 'C']) graph['B'] = deque(['A', 'D']) graph['C'] = deque(['A', 'G', 'H', 'I']) graph['D'] = deque(['B', 'E', 'F']) graph['E'] = deque(['D']) graph['F'] = deque(['D']) graph['G.. 공감수 0 댓글수 0 2021. 8. 8.
[알고리즘] 너비 우선 탐색(BFS) (Python) 1. BFS란...? 한 단계씩 내려가면서 같은 레벨에 있는 노드들을 먼저 순회 2. 구현 전 생각정리 탐색할 그래프를 딕셔너리와 데크를 활용하여 구현해보자 need_visit 데크의 왼쪽에서 하나씩 node를 뽑아오며 탐색, 탐색할 때 그 node와 연결된 노드들을 need_visit 데크의 오른쪽에 추가해줌 3. 코드 구현 from collections import deque graph = dict() graph['A'] = deque(['B', 'C']) graph['B'] = deque(['A', 'D']) graph['C'] = deque(['A', 'G', 'H', 'I']) graph['D'] = deque(['B', 'E', 'F']) graph['E'] = deque(['D']) grap.. 공감수 0 댓글수 0 2021. 8. 8.

문의안내

티스토리
로그인
고객센터

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