알고리즘(462)
-
구조체를 활용한 priority_queue 비교함수
먼저 우선순위 큐는 보통 힙의 구조를 가지는 비선형 자료구조다. 배열로 구성할 경우엔 1. 자료의 낭비 2. 삽입에서 시간을 크게 잡아먹는다. 또한 연결리스트로 구성할 경우에도 삽입 시간이 배열과 같기에 더 낫다. 따라서 logN의 시간으로 삽입과 삭제를 할 수 있는 힙의 구조로 우선순위 큐를 작성할 수 있다 그래서 priority_queue에 우선순위를 줘야 하는데 기본적으로 우선순위는 큰 값이 높게 설정되어 있다 따라서 큰 수부터 출력하고 싶으면 우선순위 큐를 선언만하고 사용하면 된다 문제: https://www.acmicpc.net/problem/11279 https://github.com/surinoel/boj/blob/master/11729.cpp 하지만 특정한 구조체에서는 각기 다른 경우의 수..
2019.05.14 -
1431 시리얼 번호
심화 정렬문제 문제: https://www.acmicpc.net/problem/1431 https://github.com/surinoel/boj/blob/master/1431.cpp
2019.05.14 -
2638 치즈
가장자리에 치즈는 존재하지 않는 점을 이용해서 벽을 bfs로 구할 수 있다 문제: https://www.acmicpc.net/problem/2638 https://github.com/surinoel/boj/blob/master/2638.cpp
2019.05.12 -
14864 줄서기
N 제한이 큰 경우라 규칙을 찾아서 O(N)에 끝내야한다 먼저 차례대로 레벨을 번호대로 부여한다 그리고 순서쌍을 탐색하면서 갑은 +1 을은 -1로 레벨을 업데이트한다 그리고 레벨이 겹치지 않는다면 정상적으로 순서가 나오게 된다 문제: https://www.acmicpc.net/problem/14864 https://github.com/surinoel/boj/blob/master/14864.cpp
2019.05.11 -
구조체 초기화
123456789#include int main(void) { struct shape a, b; memset(&a, 0, sizeof(struct shape)); memset(&b, 0, sizeof(struct shape)); ....}Colored by Color Scriptercs
2019.05.11 -
2252 줄 세우기
위상정렬의 대표적인 문제 [참고] https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html [참고] https://blog.naver.com/ndb796/221236874984 위상정렬은 먼저 DAG(Directed Acyclic Graph)을 기반으로 하는 알고리즘이다. DAG는 방향 그래프와 비사이클 그래프를 모두 만족하는 그래프다. 따라서 순서가 정해진 그래프로, 순서를 지키며 정렬하는 알고리즘이 위상정렬이다. 탐색을 하면서 가장 중요한 요소는 자신 전에 존재하는 노드들(차수) 그리고 자신 다음의 노드 총 2가지다. 그래서 차수가 0인 것을 먼저 큐에 넣고 탐색을 진행한다. 그리고 그와 연결된 차수를 하나씩 지워나가면서 차수가 ..
2019.05.11