본문 바로가기

Algorithm&Data Structure

[Algorithm] Java 재귀, 스택 프레임
Algorithm&Data Structure 2023. 8. 25. [Algorithm] Java 재귀, 스택 프레임 DFS를 공부하기 전 재귀에 대해 다시 공부해 봤다. 스택 프레임을 그려보며 동작 과정을 보니 좀 더 직관적으로 이해할 수 있었다. 이 공부 과정에 대한 기록이다. 개요 먼저 스택 영역과 스택 프레임에 대해 간략하게 다루고, 대표적인 재귀의 예제인 피보나치수열을 스택 프레임을 그려보며 구현해볼 것이다. 그리고 리팩토링을 통해 코드를 개선해 볼 예정이다. 스택 프레임 스택 프레임은 메모리 스택 영역에 저장되는 함수 호출 정보이다. 자바의 메모리 영역 중 스택 영역이 있다. 메모리 영역에 대한 기록은 지난번에 다룬 적이 있다. [JAVA] JVM 메모리 영역 JVM이 사용하는 메모리 영역에 대한 공부 기록이다. 개요 JVM(Java Virtual Machine)이란?? 자바가 실제로 구동하는 환경 운영체제별..
[Algorithm] 순열&조합 JAVA로 구현
Algorithm&Data Structure 2023. 6. 27. [Algorithm] 순열&조합 JAVA로 구현 코딩 테스트 준비를 하다 순열, 조합 문제가 꽤 나와서 헷갈리지 않게 정리해보려고 한다. 조합 조합은 말 그대로 n개 중 r개의 조합을 말한다. 따라서 순서가 있어선 안 된다. 조합은 순열과 다르게 순서가 있어서는 안 되기 때문에 이를 위한 장치가 중요하다. 먼저 코드를 보자. package AlgorithmNote.NumberTheory; import java.util.*; public class Combination { public static void combination(int[] arr,int[]output,boolean[] visited, int start,int n,int r){ if(r==0){ System.out.println(Arrays.toString(output)); return; ..
[Algorithm] 정수론 및 조합론(백준 2981,2004번)
Algorithm&Data Structure 2023. 1. 25. [Algorithm] 정수론 및 조합론(백준 2981,2004번) 백준 알고리즘을 풀면서 각 단계를 마칠 때마다 해당 단계에서 배운 점을 정리해 보면 좋을 것 같아서 복습 겸 풀었던 단계들을 먼저 정리해 보려고 한다. 정수론 정수론에서는 최소 공배수, 최대 공약수에 대한 개념이 주로 나왔던 것 같다. 최대 공약수를 유클리드 호제법이라는 알고리즘을 사용해 구하면 시간 복잡도를 O(N)에서 O(logN)으로 줄일 수 있다. 10과 12의 최대 공약수를 구한다고 해보자. 위와 같이 쉽게 구할 수 있다. 코드로 나타내면 아래와 같다. def gcd(a,b): while b: a,b=b,a%b return a 최소 공배수는 최대 공약수를 이용하면 바로 구할 수 있다. 두 수의 곱을 최대 공약수로 나누면 최소 공배수이다. 코드로 나타내면 아래와 같다. def lcm(a,b): r..
[Algorithm] Python 집합 유형
Algorithm&Data Structure 2023. 1. 10. [Algorithm] Python 집합 유형 백준 집합 단계를 풀고, 알게 된 것과 더 공부한 것들에 대한 기록이다. 집합 파이썬에서 특정 원소를 찾아내는 작업이 집합으로 접근했을 때 가장 빠르다는 것을 알게 되었다. 사실 이 단계를 접하기 전까지 집합 자료구조를 한 번도 써본 적이 없는데 이번에 유용하다는 것을 알게 되었고, 자주 쓸 것 같아 추가적으로 한 공부 기록을 남기려고 한다. 기본 개념 집합과 딕셔너리 모두 중괄호를 사용하기 때문에 선언 시에 set 생성자를 이용해야 한다. s=set() 집합의 원소로 mutable(수정 가능)한 값을 가질 수 없다. s=set() s.add([1,2]) #TypeError: unhashable type: 'list' 집합 내에 중복되는 값들은 자동으로 삭제된다. s=set([1,2,3,1,2]) pri..
Algorithm&Data Structure 2022. 12. 22. [Algorithm] 백준 정렬 파트 (2108,18870) 백준 알고리즘 단계별로 풀어보기 중 정렬 단계를 모두 풀어봤다. 그중 2108번과 18870에서 어려움을 겪어 기록을 남기게 되었다. 개요 정렬은 이전 기록에서 다룬 적이 있다. [Algorithm] 정렬 방법, 구현(선택, 버블, 삽입, 병렬, 퀵, 계수) 정렬에 대해 공부를 해서 이에 대한 기록을 하려고 한다. 본 글의 정렬은 오름차순을 기본으로 한다. 내림차순은 파이썬에 내장된 reverse 메서드를 사용하면 쉽게 구현할 수 있다. 1. 선택 정렬 선 choi-records.tistory.com 때문에 백준 알고리즘 정렬 단계에서 대부분의 문제들을 무난하게 풀어냈다. 정렬 단계 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 ..
[Algorithm] 탐색 알고리즘 DFS/BFS
Algorithm&Data Structure 2022. 12. 11. [Algorithm] 탐색 알고리즘 DFS/BFS 기본 탐색 알고리즘 DFS와 BFS에 대한 기록이다. DFS DFS(Depth-First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프는 저번 기록에서 다뤄보았다. [Data Structure] 그래프의 구성, 종류, 표현 (Graph) 기본 자료 구조 그래프에 대한 공부 기록이다. 구성 그래프는 정점과 간선으로 구성된다. 정점 : 대상(개념, 값 등) 간선 : 대상들 간의 관계를 나타냄 간선으로 연결된 두 정점은 인접의 관계를 choi-records.tistory.com DFS에 대한 그림 설명이다. DFS는 보통 스택 자료구조를 이용한다. [Data Sturcture] 스택, 큐, 우선순위 큐, 기본적인 자료구조에 대해 먼저 다뤄보려고 ..
[Data Structure] 그래프의 구성, 종류, 표현 (Graph)
Algorithm&Data Structure 2022. 12. 11. [Data Structure] 그래프의 구성, 종류, 표현 (Graph) 기본 자료 구조 그래프에 대한 공부 기록이다. 구성 그래프는 정점과 간선으로 구성된다. 정점 : 대상(개념, 값 등) 간선 : 대상들 간의 관계를 나타냄 간선으로 연결된 두 정점은 인접의 관계를 가진다. 종류 무향 그래프 간선에 정점의 관계없이 그냥 이어져있다. 방향이 없다는 뜻의 무향이다. 가중 그래프 간선에 인접한 두 정점의 관계값이 있다. 하지만, 방향은 없다. 방향 그래프(유향 그래프) 인접한 두 정점 사이의 방향이 결정된다. 수치로 볼 수 있는 값은 없다. 가중 방향 그래프 인접한 두 정점 사이의 관계 값이 방향 각각에 결정된다. 그래프의 표현 그래프는 다양하게 구현될 수 있다. 인접 행렬 그래프가 n*n 행렬 A[][]로 표현된다. 정점 i와 j 사이의 간선 존재 여부를 A[i][j]에 기록한..
Algorithm&Data Structure 2022. 12. 11. [Algorithm] Python 각 자릿수 더하는 방법(sum,map) 백준 기본 문제를 풀다가 쓰는 각 자릿수 더하는 방법에 대한 기록이다. 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 문제는 위의 문제이다. 셀프 넘버를 구하는 데에 포인트는 각 자릿수를 더하는 것이다. 처음에는 10으로 나눠가며 더했지만, 비효율적인 것 같아 다른 방법을 고안해봤다. 바로 map 함수를 이용해 list로 바꿨다가 다 합하는 방법이다. num=123 numSum=sum(map(int,str(num))) 이에 더해 map 함수에 대해 더 알아봤..
[Data Structure] 색인과 이진 검색 트리(구현, 순회)
Algorithm&Data Structure 2022. 12. 11. [Data Structure] 색인과 이진 검색 트리(구현, 순회) 기본 자료 구조 이진 트리에 대한 공부 기록이다. 색인 색인은 데이터를 찾을 때 사용되는 지름길 같은 개념이다. 색인은 키와 페이지로 이루어져 있다. 키를 이용해 페이지를 얻어 쉽게 데이터를 찾을 수 있다. 색인을 위한 자료구조로는 저번 기록에서 다뤘던 Hash Table [Data Structure] Hash Table Hash Table에 대한 공부 기록이다. Hash Table 입력값에 대해 hash 함수를 거치고, 결과값 즉, key값에 의해 위치가 결정된다. 정렬이 아닌 결정된 위치에 데이터를 보관하기 때문에 빠른 삽입, 검색, 삭 choi-records.tistory.com 그리고 이번 기록에서 다룰 이진 검색 트리 등이 있다. 이진 검색 트리 트리는 위와 같은 구조로 이루어져 있다. 이진 검..

티스토리툴바