전체 글195 [DFS, BFS] 백준 1260번 DFS와 BFS with Python3 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 내 풀이 from collections import deque def bfs(start): que = deque([start]) visit_list[start] = 1 while que: vv = que.popleft() print(vv, end=' ') for i in range(1, n+1): if visit_list[i] == 0 and graph[.. 2021. 8. 20. sw 사관학교 정글 2기 week03 면담 질문 1. 알고리즘을 공부 할 때 문제 풀이 이전에 자료등을 확보해야 할 때 어떤 식으로 접근하면 좋을까요? 블로그, 유투브 등에서 수 많은 무료 강의들이 있으니 이를 활용해도 좋지만, introduction to algorithm 이라는 책에서 결국 거의 대부분의 알고리즘의 원론 그 자체가 담겨있기에 깊이 파고 든다면 ita등의 책으로 수렴할 수 밖에 없다. 질문 2. vr 업계 혹은 메타버스등의 업계의 미래는 어떤가요? 메가 트렌드, 즉 거의 대부분의 컴퓨터 기술의 지향점은 가상 공간 확대에 있기에 갑자기 도태되거나 필요 없어질 일은 없다. 하지만, vr등의 기술이 충분한 경험을 제공하기 위해서는 기술, 예를 들어 통신속도, 연산 능력, 등이 받쳐줘야하는데 이러한 트렌트는 90년대부터 이미 나오던 이.. 2021. 8. 19. 그래프 탐색 알고리즘: DFS/BFS 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. dfs와 bfs는 가장 흔히 사용되는 그래프 탐색 알고리즘이다. 알고 가야하는 두가지 자료 구조: 스택: 선입후출 / 입구와 출구가 동일한 형태 큐: 선입선출 / 입구와 출구가 모두 뚫려 있는 터널과 같은 형태. 재귀 함수: 자기 자신을 다시 호출하는 함수 재귀 함수 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함. 그렇지 않을 경우 함수가 무한히 호출될 수 있다. 재귀 함수를 이용하게 되면 마치 스택에 데이터를 넣었다가 꺼내는 것과 마찬가지로 각각의 함수에 대한 정보가 실제로 스택 프레임에 담기게 되어서 이렇게 차례대로 호출이 되었다가, 마지막에 호출되었던 함수부터 차례대로 종료되어 결과적으로 첫번째 호출했던.. 2021. 8. 19. [스택] 백준 10799번 쇠막대기 with Python3 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 내 풀이 import sys from collections import deque #입력 input = sys.stdin.readline str = input().rstrip() #자료형 stack = deque([]) result = list() #인덱스 대체제 count = 0 #들어갔다 나갔다하는 stack 활용 for i in str: if i == ")": top = stack.pop() if.. 2021. 8. 19. [sw사관학교 정글 2기] week02 개발일지 - 알고리즘- 힙 / 우선순위 큐: 최소값 혹은 최대값이 일정하게 필요할 경우 크게 용이. 자료구조 자체가 첫번째 원소가 최소, 최대임을 보장 받기에 유용. 큐, 스택 : 큐는 bfs, 스택은 dfs 아니면 재귀의 구조와 닮아 있다. 그 이외에는 stack, q 기능만 있는 자료구조를 사용하면 리스트형보다 pop, append 등의 행동의 시간이 덜 든다는 장점이 있다. 이분 탐색: 탐색 기법 중에서 가장 많이 쓰이는 방법이지 않을까 싶다. 간편하고 시간복잡도도 보장받는다. 응용가능성이 무궁 무진. 분할 정복: 개념 자체는 간단하다. 하지만 적절한 조건들을 주어 원하는 지점까지 분할해서 원하는 값을 계속해서 리턴 받는게 어렵다. 어떤 블로그에서 보기로, 분할정복은 리턴 값에 원하는 값을 돌려받을 수 있게 코드를 짜기만.. 2021. 8. 19. [분할정복] 백준 1780번 종이의 개수 with Python3 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 내 풀이 import sys input = sys.stdin.readline N = int(input()) paper = [list(map(int, input().split())) for _ in range(N)] one = 0 zero = 0 minus = 0 def nine_tree(x, y, n): global one, zero, minus, color color = pape.. 2021. 8. 18. [분할정복] 백준 11582번 치킨 TOP N with Python3 https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 문제 정답 풀이 import sys input=sys.stdin.readline def check(s,e): if((e-s)>(n/k)): ##정렬 정지 조건 return mid=int((s+e)/2); idx1=s; idx2=mid+1; idx3=0; while(idx1 2021. 8. 18. [우선순위 큐, 힙] 백준 1658번 가운데를 말해요 with Python3 ★ https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 정답 풀이 import heapq import sys # 중앙값 기준으로 작은 값 = left, 큰 값 = right left, right = [], [] n = int(sys.stdin.readline()) for _ in range(n): num = int(sys.stdin.readline()) # 최소 힙과 최대 힙에 원소를 번갈아가며 push/ left부터이긴함 if .. 2021. 8. 17. [우선순위큐]백준 13334번 철로 with Python3 ★ https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 문제 정답 풀이 import sys import heapq n = int(sys.stdin.readline()) road_info = [] for _ in range(n): road = list(map(int, sys.stdin.readline().split())) road_info.append(road) d = int(sys.stdin.read.. 2021. 8. 17. 이전 1 ··· 9 10 11 12 13 14 15 ··· 22 다음
