220415 금 Algorithms TIL

백준 1991번 트리 순회 실버1

https://velog.io/@bongf/211226-Algorithms-TIL 에 업데이트

백준 5639번 이진 검색 트리 골드5

• 문제
• 코드-파이썬
• 구글링 참고했다
  • 중위순회를 한 값이 주어지기 때문에 가장 첫번째에 나오는 값은 루투일 것이고 어느 기점을 기준으로 그 왼쪽은 자신보다 작은 값, 그 오른쪽은 자신보다 큰 값이 올 것. 그 각각에 대해서 다시 재귀로 후위 순회로 찾는 함수를 호출해주고 마지막엔 자신의 값을 print
• 파이썬 입력 오류시 종료 except https://dojang.io/mod/page/view.php?id=2398
  • 파이썬 엔터 후 입력 종료
  • readlines를 이용하는 방법도 있다.

lines = sys.stdin.readlines()
    for line in lines:
    	//작업내용

백준 1197번 최소 스패닝 트리 골드4

• 문제
• 코드-파이썬
  https://velog.io/@bongf/211220-Algorithms-TIL

백준 1260번 DFS와 BFS 실버2

• https://velog.io/@bongf/220109-Algorithms-TIL 에 업데이트
• 지난 번에 풀었던 풀이를 보니 graph 그려줄 때 sort를 해주면 searh 할 것 더해줄 때 하나하나 sort 안해줘도 된다.

백준 11724번 연결 요소의 개수 실버2

• 문제
• 코드-파이썬

푼 것, 배운 것

• 예전에 프로그래머스에서 비슷한 문제를 풀었는데 정확히 똑같은 실수를 했다.
• 같은 그래프라면 부모를 동일시하는 방법으로 처음에 접근했다가, 나중에 부모가 업데이트 되면 그 부모의 자식들은 업데이트가 안되니까 오류 발생
  • 그를 위해 for문을 돌면서 다 부모 업데이트를 해줬어야 했는데 이를 안해주는 똑같은 실 수를 했다.
• 안되는 방법으로 생각해서 bfs로 풀어봤다.
• 시간차는 별로 나지 않았다(더 느린 것이 부모 테이블로 푸는 것)
  

백준 5639번 이진 검색 트리 골드5

• 문제
• 코드-파이썬

백준 1933번 스카이라인 골드1

• 문제
• 코드-파이썬

스카이라인

• 1) 높이 기준으로 뽑아내는 것이 중요 (현재 기준 최대 높이)
• 2) building을 정렬 할 떄
  • 1) 일단 x 좌표
  • 2) 시작점과 끝점이 같은 지점에서 겹치는 경우 시작점을 먼저 처리해줘야 끝점이 0으로 떨어지지 않는다
  • 3) 같은 시작점이 다른 높이를 가지는 경우 더 높은 것을 먼저 찍어줘야 더 낮은 것을 안찍을 수 있다 그래서 높이 기준으로 정렬
  • 4) 같은 끝점이 다른 높이를 가지는 경우
    • 맨 위에 한 포인트만 찍어주면 된다. 그래서 종료 포인트에 대한 작업을 하는 경우 역시 우선순위큐에서 맨 앞에 있는값(제일 높은 값이) 아직 종료된 애가 아니라면 종료된 애들을 모아둔 set에 넣기만 하고 pass priority queue가 갱신되다가 혹시 종료된 애가 나오면 삭제 될 수 있도록

백준 1707번 바이러스 실버3

• 여기에 업데이트 https://velog.io/@bongf/211125-Algorithms-TIL

백준 11725번 트리의 부모 찾기 실버2

• 여기에 업데이트

백준 1707번 이분 그래프 골드4

• 문제
• 코드-파이썬
• 이분 그래프가 무엇인지 잘 못해서 검색해봤다.
  • 인접한 점은 다른 색으로 칠한다고 했을 때 두가지 색으로만 가능하면 이분 그래프