전체 글361 [BOJ]14425번: 문자열 집합 문제: https://www.acmicpc.net/problem/14425 트라이 문제입니다. N, M 제한이 1만이므로 정직하게 2중 포문을 돌면 시간초과가 납니다. 트라이 자료구조에 대한 설명: https://www.notion.so/Trie-875eeb41921f4559b87a38f1e4136e7e 트라이를 사용하면 하나의 문자열에 대해 최대 문자열의 길이만큼만 탐색이 이뤄지기 때문에 O(500*M) 으로 통과할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ14425.java 2022. 3. 15. [PRGRMS]72411번: 메뉴 리뉴얼 문제: https://programmers.co.kr/learn/courses/30/lessons/72411 시뮬레이션 문제입니다. 놓치기 쉬운 조건은 아래 두 가지입니다. 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다. 예를 들어, 요리 2개 코스 후보가 AB -2번 주문, AC - 3번 주문, AD - 3번 주문 이렇게 주어진 경우 AC, AD만 정답에 포함됩니다. 그러므로 AB도 2명이상으로부터 시켰다고 정답에 포함시키면 안되겠습니다. 1. 임의의 메뉴 2개 String 선택 (두 String 중 길이가 짧은 String을 A, 길이가 긴 String을.. 2022. 3. 15. [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. 이전 1 ··· 7 8 9 10 11 12 13 ··· 91 다음
