Algorithm283 [코딩테스트 연습] 단어 변환 문제: https://programmers.co.kr/learn/courses/30/lessons/43163 BFS 문제입니다. 자신과 한 글자만 다른 단어를 다음 탐색 후보로 하여 BFS를 수행해주면 됩니다. 또한 방문 표시를 통해 똑같은 단어를 다시 방문하지 않도록 해주면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43163.cc 2020. 6. 11. [BOJ]1654번: 랜선 자르기 문제: https://www.acmicpc.net/problem/1654 parametric search 문제입니다. 랜선의 하한: 1 랜선의 상한: 2^31 - 1 랜선의 상한 ~ 하한에 대한 임의의 길이 값을 기준으로 "N개의 랜선을만들 수 있다면 TRUE, 만들 수 없다면 FALSE" 입니다. 임의로 정한 랜선의 길이가 길어질 수록 만들 수 있는 랜선의 갯수는 작아지고, 랜선의 길이가 짧아질수록 만들 수 있는 랜선의 개수는 늘어납니다. 이런 구간의 연속성이 성립하기 때문에 랜선의 하한 ~ 상한의 범위를 선형 탐색이 아닌 이분 탐색으로 훑을 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1654.cc 2020. 6. 9. [BOJ]9466번: 텀 프로젝트 문제: https://www.acmicpc.net/problem/9466 싸이클 찾기 문제입니다. 위상 정렬을 통해 해결할 수 있습니다. 싸이클의 대상이 아닌 노드의 특징은 자신에게 들어오는 간선이 하나도 없다는 점입니다. 그러므로 처음에 데이터를 입력받을 때 finished[] 배열을 통해서 자신에게 들어오는 간선을 카운트 해줍니다. 1. finished[Node] == 0인 애들을 제외 (싸이클이 아님) 2. 1번에서 제외된 노드들과 연결되어있던 Node들의 finisehd[] 값을 1 감소시켜줍니다. (싸이클이 아닌 후보들로부터 들어온 간선은 싸이클에 아무런 영향을 끼치지 못하므로) 3. 2번 과정을 통해 finished[] == 0인 애들이 있다면 이 노드들도 제외해줍니다. 4. finished[.. 2020. 6. 9. [BOJ]2792번: 보석 상자 문제: https://www.acmicpc.net/problem/2792 https://jaimemin.tistory.com/1128 https://blog.encrypted.gg/630 parametric search 문제입니다. 가지고 있는 보석갯수의 하한, 상한을 정한 후 "임의의 보석갯수 K개씩 나눠줬을 때 N명 이하에게 나눠줄 수 있냐/없냐"라는 결정문제로 바꿔서 풀 수 있습니다. ps. 아무것도 못 받는 인원이 발생해도 되니 N명 미만으로 나눠줘도 문제 조건을 만족합니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2792.cc 2020. 6. 5. 이전 1 ··· 52 53 54 55 56 57 58 ··· 71 다음
