본문 바로가기

알고리즘233

[Leetcode] 881. Boats to Save People 문제 요약알고리즘 분류: 그리디, 투 포인터, 정렬난이도: Medium문제내용:각 보트는 최대 2명까지만 태울 수 있습니다.보트에 태운 사람들의 몸무게 합은 limit를 초과할 수 없습니다.모든 사람을 태우기 위한 최소 보트 수를 구해야 합니다.사이트 주소: https://leetcode.com/problems/boats-to-save-people/description/문제풀이 이번 문제에서는 완전탐색으로 풀수 있지만 최대 크기가 10^5인점으로 고려하면 다른 방법으로 풀어야 한다. 그래서 이번에는 그리디와 투 포인트로 풀어야 한다. 그에 대한 이론 설명은 아래 글에 확인 해보면 됩니다.그리디: https://jih3508.tistory.com/70투 포인터: https://jih3508.tistory.. 2025. 4. 28.
[BAEKJOON]2745 진법 변환 문제 요약알고리즘 분류: 구현, 수자난이도: Bronze1문제내용:N을 B진법된것을 10진수로 변환 하여라사이트: https://www.acmicpc.net/problem/2745문제풀이 이번 문제는 각 언어마다 진법을 변환 하는 방법만 알면 문제 푸는데 지장이 없을 것이다. CodePythonint(N, B): B진법 된 N을 10진수로 변환 하여라N, B = input().split()B = int(B)print(int(N, B))JavaInteger.parseInt(N, B): B진법 된 N을 10진수로 변환 하여라import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.ut.. 2025. 4. 24.
[BAEKJOON]25206 너의 평점은 문제 요약알고리즘 분류: 구현, 문자열난이도: Bronze1문제내용:입력한 문자열 5줄을 세로로 읽은 순서대로 글자를 출력한다.사이트: https://www.acmicpc.net/problem/10798문제풀이 이번 문제는 어떻게 가로 문자열을 세로로 구현 하는 방법만 알면 되기때문에 구현은 아래와 같이 하면 쉽게 풀 수 있는 문제이다. 2차원 배열/리스트를 만들어 각 열의 문자들을 저장합니다.5줄의 입력을 처리하면서 각 문자를 해당하는 열 인덱스에 저장합니다.열의 개수는 입력에 따라 달라질 수 있으므로, 필요에 따라 동적으로 열을 추가합니다.모든 입력을 처리한 후, 각 열의 문자들을 순서대로 이어붙여 결과 문자열을 생성합니다.CodePythonstrings = [[]] # 2차원 리스트 초기화, 세.. 2025. 4. 24.
[Leetcode] 1833. Maximum Ice Cream Bars 문제 요약알고리즘 분류: 그리디, 계수 정렬난이도: Medium문제내용:각 아이스크림 바의 가격은 costs 배열에 저장되어 있습니다. 소년은 처음에 coins 코인을 가지고 있으며, 가능한 많은 아이스크림 바를 구매하고 싶어합니다.주어진 coins 코인으로 소년이 살 수 있는 최대 아이스크림 바의 개수를 반환해야 한다.사이트 주소: https://leetcode.com/problems/maximum-ice-cream-bars/description/ 문제풀이 이번 문제에서는 완전탐색으로 풀수 있지만 최대 크기가 10^5인점으로 고려하면 다른 방법으로 풀어야 한다. 그래서 이번에는 그리디나 계수정렬로 풀어야 한다. 그에 대한 이론 설명은 아래 글에 확인 해보면 된다.그리디: https://jih3508... 2025. 4. 23.
[알고리즘 이론] 계수 정렬(Counting Sort) 1. 계수 정렬이란?계수 정렬(Counting Sort)은 비교 기반이 아닌 정렬 알고리즘으로, 정수나 정수로 표현할 수 있는 데이터를 정렬할 때 사용됩니다. 이 알고리즘은 각 항목이 몇 번 등장하는지 세어서 정렬하는 방식으로 작동합니다. 특히 정수의 범위가 작을 때 매우 효율적인 알고리즘입니다.2. 계수 정렬의 기본 원리계수 정렬의 기본 아이디어는 다음과 같습니다:입력 배열의 최댓값과 최솟값을 찾아 범위를 결정합니다.해당 범위만큼의 크기를 가진 카운트 배열을 생성합니다.입력 배열을 순회하며 각 요소의 출현 횟수를 카운트 배열에 기록합니다.카운트 배열을 누적합으로 변환합니다(선택 사항).누적합을 이용하여 각 요소의 정확한 위치를 계산하고 결과 배열에 배치합니다.3. 계수 정렬 알고리즘 단계별 설명계수 정.. 2025. 4. 23.
[Leetcode] 802. Find Eventual Safe States 문제 요약알고리즘 분류: 백트레킹, 수학, 배열난이도: Medium문제내용:개의 노드로 구성된 방향 그래프가 있으며, 각 노드는 0부터 n - 1까지 레이블이 지정되어 있습니다.그래프는 0-인덱스 기반의 2D 정수 배열 graph로 표현되는데, graph[i]는 노드 i에 인접한 노드들의 정수 배열입니다.터미널 노드(Terminal Node): 나가는 간선이 없는 노드입니다.안전 노드(Safe Node): 해당 노드에서 시작하는 모든 가능한 경로가 터미널 노드나 다른 안전 노드로 이어지는 노드입니다.사이트 주소: 문제풀이 이 문제는 얼핏 보면 복잡해 보이지만, 그래프 이론의 위상 정렬(Topological Sort)을 응용하여 해결할 수 있습니다. 여기서 주요 인사이트는 문제를 역방향으로 생각하는 것입.. 2025. 4. 22.

티스토리툴바