jungle python 2252 백준 algorithm

파이썬 알고리즘 3주차 : 줄 세우기

정글일지 17

1.개발 진행 및 완료상황

  • 2주차 python algorithm 문제풀이 완료

  • 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용

  • 백준 2252

2252번: 줄 세우기

2252번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 줄 세우기 스페셜 저지 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 37709 21883 14481 56.278% 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, …

www.acmicpc.net

풀이 방법 : 위상정렬에 기본적인 개념에 대한 문제였다. 문제 풀기 전 개념에 대해 공부를 해서 고생끝에 적용하여 풀었다. 위상정렬의 원리와 코드를 공부하면 쉽게 풀 수 있는 문제였다.

정답코드

import sys from collections import deque n, m = map(int,sys.stdin.readline().split()) in*degree = [0 for * in range(n+1)] list = [[] for _ in range(1+n)] answer = [] for _ in range(m): a,b = map(int, sys.stdin.readline().split()) list[a].append(b) in_degree[b] += 1 queue = deque() for i in range(1,n+1): if in_degree[i] == 0: queue.append(i) while queue: tmp = queue.popleft() answer.append(tmp) for i in list[tmp]: in_degree[i] -= 1 if in_degree[i] == 0: queue.append(i) print(*answer)

  1. 새로 배운 내용
  • 위상정렬 : 위상정렬의 과정은
  1. 진입차수가 0인 정점을 큐에 삽입
  2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거
  3. 제거된 후에 진입차수가 0인 정점을 큐에 삽입
  4. 이후 2~3의 과정을 반복

다음과 같다. Introduction to Algorithms에서 더욱 자세히 공부해야할 필요가 있다.

  1. 참고할 만한 레퍼런스들
  • 자료구조와 함께 배우는 알고리즘 입문 파이썬편(BohYoh Shibata 지음, 강민 옮김, 이지스 퍼블리싱)
  • https://hongcoding.tistory.com/95

  • 특이사항

  • 손에 상처가 곪아 병원을 여러군데 다니느라 시간낭비함. 아프지말것.

  • 회고

  • 이번주에 내가 익혀야할 것이 얼마나 많은지 조금은 체감한듯 하다. 열심히 공부하고 또 공부해야겠다. 지금도 이미 벅차겠지만 내가 몰라서 놓치고 있는것들은 상상도 못할만큼 많을것이다.
  • TO-DO-LIST
  1. 3주차 파이썬 알고리즘 문제 복습
  2. Introduction to Algorithm 읽기
CATALOG
    log