본문 바로가기

Algorithm/BOJ172

[BOJ]2644번: 촌수계산 https://www.acmicpc.net/problem/2644 한 명의 사람(노드)는 자신을 기준으로 부모 / 자식의 관계를 가질 수 있습니다. 부모는 단 한 명이고, 자식은 여러명일 수 있으니 아래와 같이 표현할 수 있습니다. int parent[105]; vector child[105]; 그래서 특정 노드를 기준으로 부모, 자식 방향으로 BFS를 돌아서 목적 노드에 도달한다면 걸린 거리만큼 촌수를 계산해주면 되고, 목적 노드에 도달하지 못하면 -1을 출력하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2644.cc 2020. 8. 22.
[BOJ]1946번: 신입 사원 https://www.acmicpc.net/problem/1946 바킹독님의 풀이를 참고하여 해결하였습니다.(https://blog.encrypted.gg/120) 등수가 중복되지 않고 1~N으로 분포해있습니다. 때문에 따로 정렬을 하지 않아도 유일한 값입니다. grade[i]라는 변수에 서류심사 성적순으로 인원들을 넣어놓습니다. grade[i]를 앞에서 순회하면 서류 심사 성적이 높은 인원부터 탐색하는 것입니다. grade를 앞에서부터 돌면서 지금까지 나온 가장 높은 면접 성적 등수(minInterviewRank)를 저장합니다. 그리고 그 값과 i 번째 사원의 면접 성적 등수를 비교합니다. 1. i번째 사원의 면접 성적 등수가 더 좋으면 i번째 사원은 신입 사원에 넣을 수 있습니다. (cnt++) 2... 2020. 8. 22.
[BOJ]7576번: 토마토 https://www.acmicpc.net/problem/7576 기본 BFS 문제입니다. 단, 매 초당 토마토가 있는 칸이 전부 확장되어야 합니다. 이런 경우는 BFS를 무한 루프로 돌리는 것이 아닌, 큐 사이즈만큼만 루프를 돌리면, 현재 BFS 내에 있는 모든 상태가 다음 상태로 확장 될 수 있습니다. 이런식으로 매 큐 사이즈를 새로 구하고 큐 사이즈 만큼만 BFS를 돌려봅니다. 새로 구한 큐 사이즈가 0이 되면 더 이상 확장이 될 수 없다는 의미이므로 탐색을 종료하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ7576.java 2020. 8. 22.
[BOJ]10473번: 인간 대포 https://www.acmicpc.net/problem/10473 suuntree님 풀이를 참고하여 해결하였습니다. (https://suuntree.tistory.com/152) 정점의 수가 작으므로 완전 그래프처럼 생각해도 해결할 수 있습니다. 출발점을 v[0], 도착점을 v[N]이라 놓고 나머지 중간 지점들을 입력받습니다. 특정 정점 N1과 N2의 거리 중 어떤 거리를 취할 지는 아래 두 가지 중 하나를 취하면 됩니다. 1. 대포를 사용하던가 2. 그냥 걸어가던가 두 정점 사이의 거리는 피타고라스 정리를 사용했고, getDistance 라는 함수로 구했습니다. 즉, minTime = min(getDistance(n1,n2)/5 , 2 + (getDistance(n1,n2) - 50) / 5 ) 입니.. 2020. 8. 22.

티스토리툴바