본문 바로가기
  • 초부득3 - 어제보다 나은 내일을 위해
  • 꿈이 현실이 되는 날까지

전체 글195

[위상정렬] 백준 음악프로그램 2623번 with Python3 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 내 풀이 from collections import deque import sys input = sys.stdin.readline # 입력 n: 가수 수 m:보조 pd 수 n, m = map(int, input().split()) # 앞 원소에서 뒷 원소를 향하는 간선들 / 진출 방향 routes = [] for _ in range(m): m_countdown = list.. 2021. 8. 25.
[BFS] 백준 섬의 개수 2588번 with Python3 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline # 상 우 하 좌 좌상 좌하 우상 우하 dx = [-1, 0, 1, 0, -1, 1, -1, 1] dy = [0, 1, 0, -1, -1, -1, 1, 1] def bfs_2d(r, c): que = deque([]) que.append([r, c]) vis.. 2021. 8. 25.
[BFS] 백준 단지번호붙이기 2667번 with Python3 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline # 입력 n = int(input()) gangnam = [list(map(int, list(input().rstrip()))) for _ in range(n)] visited = [[0] * (n) for _ in range(n)] ans = [] # 상 우 하 .. 2021. 8. 25.
[BFS] 백준 숨바꼭질 1697번 with Python3 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline def bfs(): while que: now = que.popleft() if now == sister: print(record[now]) exit() if 0 2021. 8. 25.
Topological sort, 위상 정렬 좋은 설명 링크: https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html https://terms.naver.com/entry.naver?docId=3579618&cid=59086&categoryId=59093 위상 정렬이란? 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 개인적 노트 위상정렬이라는 알고리즘은 기본적으로 단순히 노드/꼭짓점들을 진입 방향에따라 순서대로 나열 할 뿐인 알고리즘이다. 위상정렬을 마친 답은 여러 종류가 있을 수 있고, 이를 응용하는게 알고리즘 문제들의 특징이다. 가장 기본적인 위상정렬을 시행하는 문제로 백준-줄.. 2021. 8. 25.
[위상정렬] 백준 작업 2056번 with Python3 ★★★ https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 정답 풀이 import sys from collections import deque def topological(): q = deque() # 진입 차수가 0인 값 q에 삽입 for i in range(1, n + 1): if len(indegree[i]) == 0: q.append((i, time[i])) # 각 작업번호i에 걸리는 시간 time[i] print(q) total =.. 2021. 8. 25.
[BFS] 백준 숨바꼭질 1697번 with Python3 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline def bfs(): while que: now = que.popleft() if now == sister: print(record[now]) exit() if 0 2021. 8. 24.
sw사관학교 정글 2기 week03 면담2 질문 1 개발자로서 커리어의 첫 1~2년이 어떤 사수를 만나는가 등으로 아주 중요한 시기라고 말씀해주셨는데, 좋은 회사, 혹은 좋은 선배와 만날 수 있는 방법이 있을까요? 현재 많은 소프트웨어 회사들이 팀 단위 채용을 통해 지원자가 회사 그리고 자기 팀에 맞는지를 면밀히 파악한다. 그렇기에 면접 단계에서 팀, 회사, 그리고 선배들에 대한 질문들을 준비해가서 직접 질문해보며 파악할 수 있다. 면접은 회사가 나를 알아가는 단계임과 동시에 내가 회사에 대해 직접적으로 알수 있는 기회이다. 질문 혹은 사수가 될 수도 있는 사람과 10~15분 정도의 통화 기회 요청등으로 적극적으로 행동하면 좋다. culture fit 이란 단어가 회자되고 있는데 어떠한 사람은 능동적으로 일하기에 터치가 없어야 오히려 더 일을 잘.. 2021. 8. 24.
[위상정렬] 백준 장난감 찾기 2637번 with Python3 ★★ https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 문제 정답 풀이 import sys from collections import deque input = sys.stdin.readline # N = 완제품 번호, 1,2,3,...N-1 까지 기본부품 혹은 중간부품 N = int(input().rstrip()) # M = 어떤 부품을 완성하는데 필요한 부품들의 관계 개수 M = int(input().rstrip()) ar.. 2021. 8. 24.

티스토리툴바