본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

알고리즘

Algorithm/BOJ 2022. 3. 8. [BOJ] 용량 부족(5446) [백준(BOJ)] 용량 부족(5446) C++ 문제 : BOJ_5446번 용량 부족 문제 설명 Trie 트라이를 응용해야 풀 수 있는 문제입니다. 지워야 하는 파일과 지우면 안 되는 파일이 모두 주워지는데, 와일드카드 *를 제일 끝에만 사용하여 지울 수 있을 때, 지워야 하는 파일을 모두 지울 수 있는 최소의 횟수를 구해야 합니다. Solution 트라이의 특성상, 문자열의 순서가 자식 트라이 노드로 이어지기 때문에, bool형 변수를 하나 선언해서 처음에 지워야 하는 파일 이름을 트라이에 하나씩 등록할 때마다 한 글자, 한 글자 bool형을 true로 해줍니다. 그 뒤 지우면 안 되는 파일을 등록할 때, 트라이에 한 글자, 한 글자 모두 bool형을 false로 해줍니다. 트라이를 순회하면서 true인..

Algorithm/이론 2022. 3. 8. Trie(트라이) 알고리즘 문자열 저장 Trie(트라이) 알고리즘 C++ Trie 알고리즘은 문자열을 저장하고, 해당 문자열의 저장 유무를 확인할 때 쓰는 알고리즘입니다. 예시 "vivid" 라는 문자열을 저장한다고 가정합시다. 가장 맨 위에 자료를 저장할 루트 노드가 있을 것이고, 그 루트 노드 아래 v를 저장, v가 저장되어 있는 노드 아래 i가 저장 i가 저장되어 있는 노드 아래 v를 저장.. 이런 식으로 마지막 d까지 저장합니다. 여기서 가장 마지막 문자열인 vivid의 d 뒤엔 문자열의 끝을 알리는 '\0'이 붙어있을 것이므로, 이를 d 노드에 표시(노란색 노드)를 해줍시다. 이런 식으로 루트 노드 아래 저장할 단어들의 노드를 확장 시킵니다. "vivid" 외에 "sw", "swan", "sweet"를 추가해보면 아래와 ..

Algorithm/BOJ 2022. 3. 7. [BOJ] 보석 상자(2792) [백준(BOJ)] 보석 상자(2792) C++ 문제 : BOJ_2792번 보석 상자 문제 설명 이분탐색 이분 탐색으로 해결할 수 있는 문제입니다. 사람 수 N이 있고, 보석의 종류 수 M이 있습니다. 한 사람에게는 한 종류의 보석을 나눠 줄 수 있고, 모든 사람에게 보석을 줄 필요는 없지만, 모든 보석은 나누어줘야 합니다. 이때, 보석을 가장 많이 갖고 있는 사람의 보석 수를 질투심이라고 할 때, 질투심의 최솟값을 구하는 문제입니다. Solution 질투심을 최소로 하려면, 보석의 종류와 상관없이, N 명이 넘어가지 않으면서, 한 학생에게 나누어줄 수 있는 보석의 수의 최솟값을 구해야 합니다. 그러므로, 보석 수를 증가시키면서, 모든 보석을 N명 이하의 학생에게 나눠줄 수 있는지를 이분 탐색을 통해 찾아..

Algorithm/BOJ 2022. 3. 7. [BOJ] 휴대폰 자판(5070) [백준(BOJ)] 휴대폰 자판(5070) C++ 문제 : BOJ_5070번 휴대폰 자판 문제 설명 Trie(트라이) 트라이로 해결하는 문제입니다. 입력한 문자열 다음의 문자가 저장된 문자열 중 하나밖에 없을 경우 자동으로 입력해 주고, 다음의 문자열이 하나 이상이거나, 입력을 멈출 때는 사용자가 입력을 해주어야 합니다. 이때 모든 문자에서 사용자가 입력해야 하는 입력의 평균 횟수를 구해야 합니다. Solution 우선 기존 트라이의 공식을 이용해서 트라이 구조체 안에 모든 문자열을 넣어줍니다. 그 뒤에 각 문자열마다 한 번씩 for문을 돌리며 입력해야 하는 횟수를 저장합니다. 저장된 다음 문자가 2개 이상이거나, 끝나는 문자열일 경우 횟수를 저장합니다. 이때, 문제의 조건에서 처음에는 반드시 1회 문자를..

Algorithm/BOJ 2022. 3. 7. [BOJ] 전화번호 목록(5052) [백준(BOJ)] 전화번호 목록(5052) Java 문제 : BOJ_5052번 전화번호 목록 문제 설명 Trie(트라이) 트라이 문제 중 기본적인 문제입니다. 전화번호들을 입력받는데, 해당 번호의 첫 번호부터 끝 번호가 다른 전화번호의 첫 번호부터 해당되있으면 일관성이 없는 것이라고 판단해야하고, 서로 겹치지않으면 일관성이 있는 것이라고 판단해야합니다. Solution java로 트라이구조를 구현해서 풀어보았습니다. String을 입력받은 뒤, String을 한 글자씩 for문으로 돌려가며, 해당 자식 번호가 없으면 Trie 인스턴스를 만들어주고, 자식의 유무와 단어의 끝 유무를 파악했습니다. Description 테스트케이스마다 생성되는 트라이 그래프의 일관성은 정적 변수로 체크했습니다. import ..

Algorithm/BOJ 2022. 3. 7. [BOJ] 히스토그램(1725) [백준(BOJ)] 히스토그램(1725) C++ 문제 : BOJ_1725번 히스토그램 문제 설명 분할정복 유명한 분할정복 문제입니다. 스텍을 활용하여 O(N) 안에 푸는 방법도 존재한다고 들었으나, 분할정복을 이용해 풀어봤습니다. 임의의 크기를 가진 간격이 1인 막대 그리프들이 늘어져있고, 내부에서 가장 큰 넓이를 구해야 하는데 이때, 막대그래프는 연속한 막대그래프를 선택해야 하고, 높이 값은 선택된 막대그래프들 중 최소 높이, 간격은 막대그래프 하나의 간격이 1이므로, 막대그래프의 개수입니다. Solution 막대그래프들을 계속 절반씩 나눠서 각각 나눠진 절반마다의 경우에서 최대 크기를 구해야 합니다. 이때, 최대 크기는 처음에 막대그래프를 중앙을 기준으로 잡고, 높이가 큰 쪽(같은 쪽이면 아무 데나)으..

Algorithm/BOJ 2022. 3. 6. [BOJ] 곱셈(1629) [백준(BOJ)] 곱셈(1629) C++ 문제 : BOJ_1629번 곱셈 문제 설명 분할정복 A, B, C가 주어지고 , A를 B번 곱한 값을 C로 나눈 값의 나머지를 구하는 문제입니다. B가 매우 크기 때문에, B에 맞게 여러 번 곱해주면 시간 초과가 납니다. Solution n이 짝수라면, A^n = A^(n/2) * A^(n/2) n이 홀수라면, A^n = A^(n/2) * A^(n/2) *A인 것을 이용하여 분할 정복 합니다. 값의 크기도 이 문제에서 매우 중요한데, A, B, C의 값이 int형의 최댓값까지 가능하므로, long long형으로 해주고, mod C를 계속 수행해 주어야 합니다. 그리고 저는 이 문제에서 자꾸 오답 제출이 많이 됐는데, n이 홀수일 때 A^n = A^(n/2) * A..

Algorithm/BOJ 2022. 3. 6. [BOJ] 회의실배정(1931) [백준(BOJ)] 회의실배정(1931) C++ 문제 : BOJ_1931번 회의실배정 문제 설명 그리디 알고리즘 유명한 그리디 문제입니다. 회의실이 하나 있고 N 개의 회의가 있는데, 회의마다 시작 시간과 끝나는 시간이 정해져있고 회의 시간은 겹칠 순 없지만 회의의 끝 시간과 다음 회의의 시작 시간이 겹칠 순 있습니다. 또 한, 시작 시간과 끝 시간이 동일한 경우도 있습니다. 이때 가능한 회의의 최대 개수를 구하는 문제입니다. Solution 끝나는 시간이 빠른 회의를 선택하면, 뒤에 선택할 수 있는 회의의 수가 늘어나므로, 끝나는 시간대로 정렬하여 그리디하게 회의를 선택하는 것이 문제의 핵심입니다. 끝 시간 순으로 정렬을 하고, 이전 회의의 끝 시간보다 시작 시간이 늦는다면 최대 개수에 추가해 줍니다. ..

이전 1 ··· 3 4 5 6 7 8 다음

티스토리툴바