Algorithm/Programmers93 [PRGRMS]49191번: 순위 문제: https://programmers.co.kr/learn/courses/30/lessons/49191 그래프 탐색 문제입니다. 순위를 알 수 있는 선수는 자신의 부모, 자식 노드에 대해 BFS를 돌렸을 때 방문하는 노드가 N-1개인 선수입니다. 그러므로 N번 전부 루프를 돌면서 하나의 선수에 대해 BFS를 돌려봅니다. N 제한이 작으므로 모든 선수에 대해 전부 BFS 탐색을 해도 O(N^2)으로 통과가 가능합니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%88%9C%EC%9C%84.java 2022. 3. 15. [PRGRMS]1844번: 게임 맵 최단거리 문제: https://programmers.co.kr/learn/courses/30/lessons/1844 기본 BFS문제입니다. 매 탐색마다 4방향을 탐색해서 진행할 수 있는지 체크해줍니다. 상태배열(visited)을 만들어 해당 칸을 이전에 방문한 적 있는지 표시하여 중복방문을 막습니다. 모든 칸을 방문했는데도 (n,m)에 도달하지 못했다면 갈 방법이 없는 것이므로 -1을 반환합니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EA%B2%8C%EC%9E%84%20%EB%A7%B5%20%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC.java 2022. 3. 11. [PRGRMS]72412번: 순위 검색 문제: https://programmers.co.kr/learn/courses/30/lessons/72412 여러 해결 방법이 있지만 저는 시뮬레이션 + 이분 탐색으로 해결했습니다. 지원자의 4가지 항목에 대해 생길 수 있는 81가지(4x3x3x3)의 상태를 분기하여 리스트를 만듭니다. 그리고 지원자의 정보를 입력받을 때 마다 지원자의 정보가 조회될 수 있는 상태 리스트에 모두 지원자의 점수를 넣어습니다. 그리고 쿼리 수행전에 오름차순 정렬을 해놓습니다. 그러면 하나의 쿼리를 이분 탐색을 통해 해결할 수 있습니다. 시간 복잡도는 O(NlogM)입니다. (지원자의 수: N, 쿼리의 수 M) 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%88%.. 2022. 3. 10. [PRGRMS]67257번: 수식 최대화 문제: https://programmers.co.kr/learn/courses/30/lessons/67257 시뮬레이션 문제입니다. 1. 순열을 통해 해당 연산자의 모든 우선순위쌍을 만듭니다. 2. 하나의 우선순위쌍을 기준으로 연산을 수행합니다. 연산을 수행하는 방법은 다양하지만, 제가 구현한 방식은 2개의 큐를 사용해서 우선순위가 높은 연산자를 먼저 연산하도록 했습니다. 한 가지 주의할 점은 연산을 수행하면서 최초의 식 순서가 바뀌면 안 됩니다ㅠㅠ 그러면 최종 연산 결과가 최적해와 다를 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%88%98%EC%8B%9D%20%EC%B5%9C%EB%8C%80%ED%99%94.java 2022. 3. 10. 이전 1 2 3 4 5 6 ··· 24 다음
