일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- 백준
- 파이썬 3
- Level1
- dp
- Level2
- 부스트캠프_AITech_3기
- 알고리즘_스터디
- 그리디
- ODQA
- 단계별문제풀이
- 개인회고
- 구현
- 최단경로
- 정렬
- 이코테
- 기술면접
- 주간회고
- Level2_PStage
- 글또
- 프로그래머스
- 백트랙킹
- python3
- 부스트캠프_AITech3기
- 이진탐색
- U_stage
- 알고리즘스터디
- 그래프이론
- dfs
- mrc
- 다시보기
- Today
- Total
목록위상정렬 (3)
국문과 유목민

드디어 이코테의 80~90%정도의 문제를 풀었다. 오늘은 그래프 이론 2문제를 풀었는데, 크루스칼 알고리즘을 활용한 문제와 위상정렬 알고리즘을 활용한 문제였다. 두 문제 다 순전히 내 힘으로 풀지 못했던 것 같아 내심 아쉽다. 다시 한 번 풀면서 문제를 익힐 시간이 필요할 것 같다. 그래도 이런 문제들을 풀면서 문제들을 푸는 기법들을 배우고 있는 것 같아 뭔가 성장하는 것 같은 느낌이 든다. 역시 아무것도 안 하는 것보다 뭐라도 하는게 나은 건 당연한 것 같다. 내일부터는 이코테 기출문제들을 풀면서 시간이나 난이도 등 때문에 넘겼던 문제들을 마저 푸는 시간을 가질 생각이다. 난이도가 높다보니 순전히 내 힘으로 풀겠다라는 객기어린 생각은 없기 때문에 최대한 생각을 하면서도, 내심 금방 해답을 볼 거 같기는..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 40분 + a 1. 문제 설명 - 테스트 케이스의 개수가 주어진다. - 각 테스트 케이스별로 팀 수, 작년에 i등을 한 팀의 번호 - 상대적인 등수가 바뀐 쌍의 수가 입력으로 주어진다. - 출력형식은 다음과 같다. - 1등팀부터 순서대로 출력한다. - 확실한 순위를 찾을 수 없다면 ?를 출력한다. - 데이터에 일관성이 없어서 순위를 정할 수 없는 겨우 'IMPOSSIBLE'을 출력한다. 2. 접근 방식 - 위상정렬 알고리즘을 활용한다. - 순위를 진입차수로 구분한다. 진입차수가 큰 것일 수록 순위가 낮다는 것으로 생각한다. - 확실한 순위를 찾을..

1. 문제 설명 N개의 강의 중 선수 강의가 있을 경우 특정 강의가 주어졌을 때, 해당 강의를 듣기 위해서 걸리는 최소한의 시간을 구하는 문제 - 위상정렬을 이용하는 문제로 위상정렬 이론에서는 리턴하는 값이 순서였다면, 이번에는 cost이다. 하지만 알고리즘 상에서 큰 변경점은 없다. 단지, 시간의 정보를 담은 리스트 변수가 하나 필요하다. 또한, 초기 input값 처리 부분을 고려하면 될 것으로 보인다. 2. 코드 from collections import deque import copy n = int(input()) indegree = [0]*(n+1) graph= [[] for _ in range(n+1)] time = [0]* (n+1) # 방향 그래프의 간선 정보 입력 받기 for i in ra..