💻 Computer Science/알고리즘

재귀함수 재귀함수는 함수 안에 자신의 함수를 다시 호출하는 함수를 말한다. 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출한다. 재귀함수는 스택 프레임을 사용해 작동한다. 스택 프레임에 저장되는 정보는 다음과 같다. 매개변수 정보 지역변수 정보 복귀 주소 그렇다면 재귀함수가 어떻게 작동하는지 코드를 통해 알아보자. 다음은 일반적으로 재귀함수를 표현하는 패턴이다. class DFS { public static void dfs(int n) { if (//재귀 탈출 조건) { return; } else { dfs(//탈출을 위한 반복 조건); } } } 예시 코드이다. class DFS { public static void dfs(int n) { if (n ..

📝 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💻 풀이 class Solution { public static int solution(int[] numbers) { int sum = 0; boolean[] arr = new boolean[10]; for (int number : numbers) arr[number] = true; for (int i = 0; i < arr.length; i++) if (arr[i] == false) sum += i; return sum; } public static int solution2(int[] numbers..

이진 트리 이진 트리는 부모인 루트 노드와, 자식인 왼쪽 노드 + 오른쪽 노드를 가지는 것이 기본 모양이다. DFS DFS(Depth-First Search)는 깊이 우선 탐색으로, 루트 노드(혹은 다른 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 전위 순회 출력 (부모-왼쪽-오른쪽) : 1 - 2 - 4 - 5 - 3 - 6 - 7 중위 순회 출력 (왼쪽-부모-오른쪽) : 4 - 2 - 5 - 1 - 6 - 3 - 7 후위 순회 출력 (왼쪽-오른쪽-부모) : 4 - 5 - 2 - 6 - 7 - 3 - 1 DFS의 구현 class Node { int data; Node lt, rt; public Node(int val) { data=val; ..

LRU LRU 알고리즘에 대해 알아보자. LRU 알고리즘은 Least Recently Used의 약자로, 직역하자면 가장 최근에 사용되지 않은 것이라는 의미를 가진다. 예를 들어 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다고 했을 때, 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘이다. 만약 캐시 사이즈가 5이고 작업이 [A, B, C, F, D]순으로 저장되어 있다면, Cache Miss 해야할 작업이 캐시에 없는 상태라면 Cache miss가 된다. 모든 작업이 뒤로 밀리며 해당 작업이 캐시의 맨 앞에 위치하게 된다. 예) G일 경우 → [G, A, B, C, F] 이때 D는 캐시에서 삭제 Cache Hit 해야할 작업이 캐시에 있는 상태라면 Cache Hit가..

투포인터 투포인터 알고리즘에 대해 알아보자. 투포인터는 선형시간 O(n)으로 알고리즘을 풀 수 있게 만들어주는 마법의 알고리즘이다. 투포인터는 간단한 편이라 한번쯤 익혀두면 구현하는 것은 어렵지 않을 것이다. 하지만, 시간이 지나면 기억은 흐릿해지기 때문에 다시 찾아 볼 수 있도록 정리해두려고 한다^^,, 투포인터는 연속적인 값들을 이용해 푸는 문제에 적합하다. 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 위 백준의 2003번 문제를 통해 투포인터 알고리즘을 ..

📝 문제 코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr 🖥 풀이 import java.util.Arrays; class Solution { public int[] solution(int n, long left, long right) { int[] answer = new int[(int) (right - left + 1)]; for (long i = left; i

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 import java.util.Scanner; class Algorithm220207 { public static void snail(int n) { int[][] arr = new int[n][n]; int[] dr = { 0, 1, 0, -1 }; // 행 변화값 (우 하 좌 상) int[] dc = { 1, 0, -1, 0 }; // 열 변화값 (우 하 좌 상) int[] dd = ..