본문 바로가기

백준138

[BAEKJOON]2903 중앙 이동 알고리즘 문제 요약알고리즘 분류: 집합난이도: Bronze3문제내용:다음의 두 가지 규칙을 따릅니다:각 변의 중앙에 점을 하나 추가각 정사각형의 중심에 점을 하나 추가N번 거친 후 점의 수를 출력해라사이트: https://www.acmicpc.net/problem/2903문제풀이이 문제는 특정 패턴에 따라 그리드를 그릴 때 생성되는 점의 개수를 계산하는 알고리즘 문제입니다. 문제에서 보여주는 이미지를 통해 패턴을 이해할 수 있습니다.패턴 분석문제에서 주어진 패턴을 분석해보면:N=1일 때, 2×2 사각형에 점 4개가 있습니다.N=2일 때, 3×3 사각형에 점 9개가 있습니다.N=3일 때, 5×5 사각형에 점 25개가 있습니다.N=4일 떼, 9×9 사각형에 점 81개가 있습니다.알고리즘은 다음과 같이 정의됩니다:정사.. 2025. 5. 15.
[BAEKJOON]7785 회사에 있는 사람 문제 요약알고리즘 분류: 집합난이도: Silver5문제내용:사람 이름하고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다. 출근 한 사람 역순으로 출력해라사이트: https://www.acmicpc.net/problem/7785 문제풀이 이번 문제는 간단한 집합문제이다. 각 언어마다 Set이라는 자료 구조만 활용 잘하면 된다. Set에 대한 기본 설명 하면 아래와 같다. O(1) 시간에 추가/삭제 가능자동으로 중복 제거빠른 검색 가능 구현은 아래와 같이 하면 된다.enter 기록은 Set에 추가leave 기록은 Set에서 제거마지막에 Set의 내용을 역순 정렬하여 출력마무리 위와 같이 구현 하면 시간 복잡도는 정렬 때문에 O(NlogN) 만큼 나.. 2025. 5. 12.
[BAEKJOON]13241 최소공배수 문제 요약알고리즘 분류: 유클리드호제법난이도: Silver5문제내용:최대 공배수를 구야여사이트: https://www.acmicpc.net/problem/13241문제풀이 이번 문제는 최대 공배수이다. 여러 가지 푸는 방법이 있지만 최적화로는 유클리드 호제법이라 최적의 방식이 있다 아래 글보고 바로 따라하면 푸는 데는 지장이 없다. 코드 설명은 아래 글만 봐도 이해하는데는 문제가 없다고 생각한다.https://jih3508.tistory.com/13 유클리드 호제법(Euclidean algorithm)이론1. 유클리드 호제법이란?두 개의 정수 혹은 다수의 자연수에서 최대공약수를 구하는 알고리즘이다. 원리는 두 수가 서로 나눠서 나머지를 구한다. 만약 나머지가 0이면 그 수가 최대 공약수jih3508.ti.. 2025. 5. 8.
[BAEKJOON]5639 이진 검색 트리 문제 요약알고리즘 분류: 트리, 트리 탐색난이도: Gold4문제내용:이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.위 트리에서 전위 순회 한것을 후위 순회한 결과를 출력하여라사이트: https://www.acmicpc.net/problem/5639문제풀이 이번에는 문제 유형은 트리 탐색에 관련 문제이다. 트리에 관한 자세한 내용은 여기에서 보면된다.문제 접근방법이 문제의 핵심은 전위 순회 결과만 가지고 후위 순회 결과를 어떻게 구하느냐는 것입니다. 아래 와 같이 처음부터 집어 넣는 식으로 만들면 시간 .. 2025. 4. 29.
[BAEKJOON]2748 피보나치 수 2 문제 요약알고리즘 분류: dp난이도:  Bronze1문제내용:피보나치 수는 0과 1로 시작한다. 피보나치 식은 아래와 같다.Fn = Fn-1 + Fn-2 N이 주어 졌을때 피보나치 Fn을 구하여라 (N 사이트: https://www.acmicpc.net/problem/2748문제풀이이번 문제는 재귀 호출로 풀기에는 숫자가 커질수록 계산량이 급격히 증가하기 때문에, 동적 계획법(Dynamic Programming, DP*을 사용해야 효율적으로 해결할 수 있다. 동적 계획법에 대해 잘 모르신다면, 아래 링크를 통해 자세한 설명을 확인 해보면 된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법.. 2025. 1. 14.
[BAEKJOON]1965 상자넣기 문제 요약알고리즘 분류: dp, LIS난이도:  Silver2문제내용:상자가 일렬로 있다. 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다.. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다.앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.사이트: https://www.acmicpc.net/problem/1965문제풀이 이번 문제에는 모든.. 2024. 11. 27.