Algorithm69

• 

  Strahler 순서 문제 설명 Strahler 순서구하기 Strahler 규칙 강의 근원인 노드의 순서는 1이다. 나머지 노드는 그 노드로 들어오는 강의 순서 중 큰 값을 i라고 했을 때, i로 정한다 강의 순서가 i개 노드로부터 2개이상 진입되면 해당 노드는 i+1의 강의 순서로 업데이트 한다. 생각한 아이디어 없음 풀이 강의 근원만 있는 상태 (위상정렬이기 때문에) 순서는 1번에 하든 2번에서 하든 상관없습니다. 3번 노드는 1번과 2번 에서 부터 진입이 시작되므로 1번이 먼저 시작한다면 3번 노드의 근원은 1로 초기화 되고 다음으로 2번 노드가 3번노드로 들어오면 2번 강의 순서도 1번이기 때문에 기존에 기존의 1로 초기화된 3번 노드는 i+1의 조건을 충족하여 2로 업데이트가 된다. 이런형식으로 강의 최대 순서를 구.. Algorithm/백준 2022. 11. 15.

• 영우는 사기꾼? 문제 설명 영우의 건설정보를 보고 거짓말을 했는지 안했는지 판별하는 프로그램을 만들어야 한다. 생각한 아이디어 영우가 거짓말을 한 경우 해당 건물의 사전 조건을 만족하지 않는데 지어져 있다면 거짓말 건물을 파괴할 때 안지어져 있을 때 파괴하자 풀이 >> 예외 상황 중복된 건물이 건설될 경우, 이 경우 건물의 진입차수가 중복으로 내려가, 사전 조건을 만족하지 않음에도 불구하고 건물을 지울 수 있게 된다. 이런 관계를 갖는 그래프일 때, 1 → 2 → 3 4→ 2 영우의 입력에는 건설 1번 건설 1번 건설 2번 이렇게 입력이 들어올 경우, 진입차수[2] = 2에서 진입차수가 0이되어 2번을 건설하게 된다. 2번을 짓기 위해서는 1번과 4번이 건설이 되어야 하는데, 2번은 건설되지 않았는데 사전 조건을 만족한.. Algorithm/백준 2022. 11. 15.

• 

  BOJ1931_회의실 배정 회의실 배정 A. 최대 사용할 수 있는 회의의 최대 개수를 구하라 how 가장 짧은 구간을 갖는 회의를 진행(X) 시작시간이 빠른 순으로 진행(X) 끝나는 시간이 빠른 순으로 진행(O) 증명 만약 회의 시간이 있고 가장 빨리 끝나는 회의가 K라고 할 때. 이 회의 이후로의 시간만큼 사용할 수 있다. 그런데 만약 k보다 늦게 끝나는 회의 K'가 있을 때 K' 이후로의 시간만큼 사용할 수 있다. K'를 선택하게 되면 이 이후로의 시간이 K시간에 끝냈을 때 보다 범위가 더 적어진다. k에 끝나는 회의를 고르는것이 k'에 끝나는 회의를 고르는것보다 최적의 방법이라는 것을 반박하기 위해서는 L이라는 남은 시간보다 L'라는 남은시간에 회의들을 배치하는것이 더 많은 회의를 넣을 수.. Algorithm/백준 2021. 10. 24.

• 

  Graph Graph 노드와 간선을 하나로 모아 놓은 자료구조. ex) 지도, 지하철, (최단거리),선수과목 .... 트리 또한 그래프라고 할 수 있다. 단, 사이클을 허용하지 않는다. ※ 그래프와 트리의 차이 관련 용어 정의 정점 (vertax) 점,위치 라는 개념.(node라고 부름) 간선 (edge) 점,위치 간의 관계, 노드를 연결하는 선(link ,branch 라고 함) 인접 정점(adjacent vertax) 간선에 의해 연결된 주변 점들. 정점의 차수 (degree) 무방향 그래프에서 하나의 정점에 인접한 정점의 수 ※ 무방향 그래프에 존재하는 정점의 모든 차수의 합= 그래프의 간선 수의 2배 진입 차수 (In- degree) 한 정점을 기준으로 외부에서 들어오는 간선의 수 진출 차수 (out- deg.. Algorithm/DataStructure 2021. 4. 13.

• PS 관련 유입 경로 velog.io/@admin1194 Algorithm/백준 2021. 3. 27.