전체 글84 [C++] 백준 5052번: 전화번호 목록 문제링크 https://www.acmicpc.net/problem/5052 풀이방법 해당 문제를 트라이 알고리즘을 공부하기 위한 목적으로 트라이 알고리즘을 이용하여 풀었다. 트라이 알고리즘이란 문자열을 효율적으로 처리하기 위한 트리 자료 구조이다. 아래 코드에 대한 상세 설명은 다음과 같고 추가적으로 주석에 설명을 덧붙였다. 코드 설명 c2i 함수: 문자를 정수로 변환해주는 함수입니다. '0'부터 '9' 사이의 문자에 대해 해당 문자의 정수값을 반환합니다. insert 함수: 주어진 전화번호를 트라이에 추가하고 중복 여부를 검사하는 함수입니다. 아래는 함수의 주요 동작을 설명한 것입니다. cur 변수를 루트 노드로 초기화합니다. 문자열 s의 각 문자 c에 대해 다음을 반복합니다. cur 노드에서 문자 c.. 2024. 2. 4. [C++] 백준 14425번: 문자열 집함 문제링크 https://www.acmicpc.net/problem/14425 풀이방법 해당 문제를 트라이 알고리즘을 공부하기 위한 목적으로 트라이 알고리즘을 이용하여 풀었다. 트라이 알고리즘이란 문자열을 효율적으로 처리하기 위한 트리 자료 구조이다. 트라이 알고리즘에 대해서 잘 몰라서 공부가 필요하면 아래 영상을 참고하자 문제에 대한 상세 풀이도 존재한다. https://www.youtube.com/watch?v=ZmLe4tc5XRI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=32 코드 #include using namespace std; const int ROOT = 1; int unused = 2; const int MX = 10000 * 500 + 5; // .. 2024. 2. 3. [C++] 백준 14426번: 접두사 찾기(Large) 문제링크 https://www.acmicpc.net/problem/14426 풀이방법 해당 문제를 트라이 알고리즘을 공부하기 위한 목적으로 트라이 알고리즘을 이용하여 풀었다. 트라이 알고리즘이란 문자열을 효율적으로 처리하기 위한 트리 자료 구조이다. check함수를 이용하여 검사해야 하는 문자열의 문자를 앞쪽부터 탐색한다. 특정 문자에서 존재하지 않는 부분이 발견된다면 false를 반환하고 끝까지 탐색했는데 존재하지 않는 부분이 발견되지 않는다면 true를 반환해서 최종적으로 입력된 특정 문자열의 접두사로 판단하여 ans의 개수를 1 증가 시킨다. 트라이 알고리즘에 대해서 잘 몰라서 공부가 필요하면 아래 영상을 참고하자 문제에 대한 상세 풀이도 존재한다. https://www.youtube.com/wat.. 2024. 2. 3. [C++] 백준 1786번: 찾기 문제링크 https://www.acmicpc.net/problem/1786 풀이방법 해당 문제는 구현된 실패 함수를 기반으로 KMP 알고리즘을 만드는 가장 기본적인 문제이다. 문자열의 각 문자들을 전부 탐색하여 문자열을 비교하는 알고리즘의 시간 복잡도인 O(N*M)을 O(N+M)으로 만들어주는 문자열 비교 알고리즘이다. 해당 내용을 모른다면 아래 바킹독님 알고리즘 영상과 구글링을 통해서 내용을 이해하고 공부하자. 추가적으로 공백이 포함된 문자열을 받아야 하기 때문에 getline을 활용한다. 또한 BOJ 16916과 다르게 일치하는 문자열을 찾아도 계속 진행해야 하기 때문에 j = f[j-1]로 변경하여 다시 문자열 탐색을 시작한다. https://www.youtube.com/watch?v=9bkbV-V.. 2024. 2. 3. 백준 14938번: 서강그라운드 (C++) 문제링크 https://www.acmicpc.net/problem/14938 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 우선 플로이드 알고리즘을 구현하여 인접 배열을 통해서 특정 노드와 특정 노드 사이의 최단 거리를 모두 구한다. 또한 unordered_map을 이용하여 특정 노드의 아이템 개수를 저장해둔다. 마지막으로 시작지점 1~n 까지 각 노드로부터 수색 범위(m) 이하에 존재하는 아이템 개수를 모두 더해서 vector 에 저장해둔다. result에는 각 시작 지점 별로 수색 범위(m) 이하에 존재하는 아이템 개수를 더한 값이 들어있다. 마지막으로 result에 들어있는 값 중 가장 큰 값을 출력하면 정답이 된다. 코드 #include #inclu.. 2024. 2. 3. 백준 1504번: 특정한 최단 경로 (C++) 문제링크 https://www.acmicpc.net/problem/1504 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 우선 solve라는 함수를 만들고 int st, int en을 추가해서 st 부터 en까지 최단 거리 값을 알려주는 함수를 만든다. 1~N까지의 경로 중에 v1과 v2를 반드시 지나는 경우는 딱 두 가지 케이스가 존재한다. (~~~ 중간에 다른 경로를 의미한다. 중간에 다른 경로가 없을 수도 있다.) (1) 1~~~V1을 지나고 V1부터 ~~~ V2를 거쳐서 V2~~~n에 도달하는 방법 (2) 1~~~V2를 지나고 V2부터 ~~~ V1을 거쳐서 V1~~~n에 도달하는 방법 위 두 케이스만 존재한다. 두 케이스에서 작은 값을 최종 결과 .. 2024. 2. 3. 백준 11779번: 최소비용 구하기 2 (C++) 문제링크 https://www.acmicpc.net/problem/11779 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구한다. 추가적으로 위 그림처럼 시작 지점부터 끝 지점 까지 경로를 찾기 위해서 pre 배열을 선언해서 pre배열을 채우고 해당 테이블을 이용해서 경로까지 출력한다. 문제 풀이는 아래 바킹독님 강의 영상을 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace.. 2024. 2. 3. 백준 1753번: 최단경로 (C++) 문제링크 https://www.acmicpc.net/problem/1753 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구하여 배열에 넣는다 아래 강의를 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace std; #define X first #define Y second int v,e,st; // {비용, 정점 번호} vector adj[20005]; const int IN.. 2024. 2. 3. 이전 1 2 3 4 5 6 ··· 11 다음
