반응형 기초탄탄7 [ CodeSignal ] 재귀를 이용한 팩토리얼 계산: 메모이제이션 재귀는 복잡한 문제를 단순하고 이해하기 쉬운 코드로 표현할 수 있게 해주는 강력한 프로그래밍 기법입니다. 그러나 때로는 재귀 호출이 과도하게 발생하여 성능 저하나 스택 오버플로우와 같은 문제가 생길 수 있습니다. 이 글에서는 재귀를 사용하여 리스트의 각 정수에 대한 팩토리얼을 계산하는 방법을 살펴보고, 메모이제이션(memoization)을 통해 어떻게 성능을 향상시킬 수 있는지 알아보겠습니다. 팩토리얼이란?팩토리얼은 수학에서 자연수의 곱을 의미하며, 기호 n!로 표기합니다.정의:n ! = n × ( n − 1 ) × ( n − 2 ) × ⋯ × 1( 0 ! = 1 ) (예외적으로 0의 팩토리얼은 1로 정의됩니다.)예를 들어:3 ! = 3 × 2 × 1 = 65 ! = 5 × 4 × 3 × 2 × 1 = .. 2024. 10. 8. [백준 11060번] 점프 점프 문제출처:https://www.acmicpc.net/problem/11060 백준 11060번 문제는 "점프 점프"라는 문제로, 주어진 배열에서 최단 거리를 이동하여 마지막 칸에 도달하는 방법을 찾는 문제입니다. 이 문제를 해결하기 위해서는 동적 프로그래밍(DP) 접근법을 사용하였습니다. 아래에 문제 풀이 과정을 단계별로 자세히 설명하겠습니다. 문제 이해주어진 배열에서 각 원소는 그 위치에서 최대 몇 칸을 점프할 수 있는지를 나타냅니다. 목표는 첫 번째 칸에서 시작하여 마지막 칸에 도달하는 최소 점프 횟수를 구하는 것입니다. 입력 및 출력 형식입력: 첫 줄에 배열의 크기 N이 주어지고, 두 번째 줄에 N개의 정수가 주어집니다.출력: 마지막 칸에 도달하기 위한 최소 점프 횟수를 출력합니다. 만약 도달할 .. 2024. 6. 4. BFS, DFS bfs, dfs 얘기를 하기 전 기본 그래프 알고리즘에 대해 살펴보겠습니다. 그래프 알고리즘? 그래프 알고리즘은 실제 세계의 다양한 문제를 모델링하고 해결하는데 필수적인 도구입니다. 사람들 간의 소셜 네트워크, 웹페이지의 링크 구조, 도로 네트워크의 복잡한 관계 표현. 물류, 통신, 교통의 경로 문제 해결등 다양한 분야에서 중요한 역할을 수행하며, 이를 통해 우리는 복잡한 문제를 효과적으로 해결할 수 있습니다. 그렇다면 컴퓨터에서 그래프를 어떻게 표현할까요? 인접행렬과 인접리스트를 사용해 표현합니다. 어떻게 표현하는지 알았으니 인접행렬과 인접리스트를 어떻게 들여다볼까요? 여기서 그래프 알고리즘이 사용됩니다. 기본적인 그래프 알고리즘은 1. 너비 우선 탐색(BFS, Breadth-First Search):.. 2023. 11. 10. [Algorithm] Algorithm 소개 알고리즘은 원하는 결과를 생성하기 위해 특정 순서로 수행해야 하는 일련의 명령을 정의하는 단계별 절차입니다. 알고리즘은 일반적으로 기본 언어와 독립적으로 개발됩니다. 즉, 하나 이상의 프로그래밍 언어로 알고리즘을 구현할 수 있습니다. 모호성, 정교함, 효율성 및 언어 독립성은 알고리즘의 일부 특성입니다. 알고리즘의 확장성과 성능은 그 중요성에 기여하는 주요 요인입니다. What is an Algorithm? 알고리즘이라는 단어는 "계산 또는 기타 문제 해결 작업에서 따라야 하는 일련의 유한한 규칙 또는 지침" 또는 "자주 재귀 작업을 포함하는 유한한 수의 단계에서 수학 문제를 해결하는 절차"를 의미합니다. 알고리즘은 컴퓨터가 계산 또는 기타 문제 해결 작업을 수행하기 위해 따라야 하는 일련의 명령입니다... 2023. 11. 4. 1020 TIL 그래프(Graph): 그래프는 정점(vertex)과 간선(edge)의 집합으로 구성된 수학적 구조입니다. 정점은 객체 또는 개체를 나타내고, 간선은 정점 간의 관계를 나타냅니다. 그래프는 방향 그래프(Directed Graph) 또는 무방향 그래프(Undirected Graph)로 나뉠 수 있으며, 간선에 방향이 있는 경우 방향 그래프, 없는 경우 무방향 그래프라고 합니다. 방향 그래프 (Directed Graph): 방향 그래프는 간선에 방향이 있는 그래프로, 간선은 한 정점에서 다른 정점으로 향하는 방향을 가집니다. 무방향 그래프 (Undirected Graph): 무방향 그래프는 간선에 방향이 없는 그래프로, 간선은 두 정점을 양방향으로 연결합니다. Vertex (정점): 정점은 그래프에서 가장 기.. 2023. 10. 20. [Algorithm] Algorithm 특성 이전글: 2023.07.20 - [기초탄탄/Algorithm] - [Algorithm] Algorithm 소개 Clear and Unambiguous: 알고리즘은 명확하고 모호하지 않아야 합니다. 각 단계는 모든 측면에서 명확해야 하며 단 하나의 의미로 이어져야 합니다. Well-Defined Inputs: 알고리즘이 입력을 받도록 지시하는 경우 잘 정의된 입력이어야 합니다. 입력을 받을 수도 있고 받지 않을 수도 있습니다. Well-Defined Outputs: 알고리즘은 산출할 출력을 명확하게 정의해야 하며 잘 정의되어야 합니다. 최소 1개의 출력을 생성해야 합니다. Finite-ness: 알고리즘은 유한해야 합니다. 즉, 유한한 시간 후에 종료되어야 합니다. Feasible: 알고리즘은 사용 가능한.. 2023. 7. 20. 이전 1 2 다음 728x90 반응형
