본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘-PS] Java 에서 재귀 호출로 팩토리얼을 구현하는 방법 재귀 재귀란 본래의 것으로 다시 돌아가는 것을 말 한다고 구글 검색에서 발췌해 왔다. 이 말은 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 이를 재귀적(Recursive) 이라고 한다. 본래의 것으로 다시 돌아간다는 것을 좀더 직관적으로 보여주자면 이러한 것들이 바로 재귀이다. 재귀 호출 프로그래밍에서도 이런 재귀적 효과를 이용하면 좀 더 간결한 프로그래밍을 구사할 수 있는데 재귀 호출을 가장 잘 표현할 수 있는 것이 팩토리얼 이다. 팩토리얼 팩토리얼은 1부터 N 까지의 모든 수를 곱하는 것인데, 다음과 같이 느낌표로 팩토리얼을 정의한다. 이 과정을 코드로 만들어 보자면 다음과 같다 재귀 호출을 사용하지 않은 팩토리얼 함수 class Main { int factorialNonR.. 2020. 2. 21.

[알고리즘-PS] Java 에서 큐를 구현하는 방법 Queue란 Stack 자료구조와 다르게 FIFO(First In First Out) 방식의 선입 선출 구조를 가지고 있는 자료 구조이다. 큐는 최근 사용 문서, 인쇄작업 대기 목록, 버퍼 등의 분야에서 사용되며 스택은 위에만 뚤려 있어 자료가 한 방양으로만 흐른다면 큐는 양 방향으로 뚤려 파이프 같은 모양으로 자료가 흐른다. 큐의 원리 큐는 다음과 같이 front와 rear로 데이터의 추가 및 삭제의 경계를 알린다. 큐에 데이터 추가하기 만약 큐가 비어있다면 front 와 rear은 같은 곳을 향하게 될 것이고 20 과 30 이란 데이터를 추가한다면 어떻게 변하는지 봐보자. front와 rear의 포인터가 달라졌는데 이런 식으로 추가를 한다면 rear += 1으로 rear의 위치가 변경되며 rear에 .. 2020. 2. 16.

[알고리즘-PS] Java 에서 스택을 구현하는 방법 이 글은 Stack의 실질적 사용보다는 자바에서 스택을 구현하는 것에 목적을 두었습니다. 만약 자바에서 어떻게 스택이 사용되는지 궁금하다면 변수가 메모리에 담기는 과정 스택 프레임 또는 JRE와 JVM이 어떻게 실행될까?의 글을 가볍게 읽고 와 주시는 것을 추천드립니다. 스택 Stack 기술 스택 (목적을 달성하기 위해서 습득하기 위한 기술을 단계적으로 쌓아 올리는 것) 등에 쓰이는 말인 스택은 무언가를 쌓아 올린다 라는 표현으로 이해해도 무방하다. 스택은 데이터를 일시적으로 저장하기 위해 탄생한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. 이를 전문 용어로 후입선출 (LIFO, Last In First Out) 이라고 한다. 푸시 (PUSH) 스택에 데이터를 넣는 작업을 뜻 한다. 팝 (.. 2020. 2. 14.

[알고리즘-PS] Java 에서 이진 검색 알고리즘을 구현하는 방법 이진 검색을 하기 위해 적용되는 전제 조건은 데이터가 키 값으로 정렬되어 있다는 가정에서 부터 시작합니다. 정렬 알고리즘의 학습이 필요한 사람은 선택 정렬 에 들어가서 가볍게 읽고 오시는 것을 추천드립니다. 이진 검색 이진 검색은 배열의 요소가 내림차순, 오름차순으로 정렬되어 있는 상태에서 검색을 진행하는 알고리즘 이다. 이진 검색의 배열을 절반으로 나눈 뒤 그 중간 값보다 크면 또 반으로 나누는 과정을 반복하여 원하는 값을 찾는 알고리즘이다.. 이진 검색을 수행하기 전에 알아야 할 용어를 정의해보자. start 배열의 시작 인덱스 (검색 범위의 시작) center 배열의 중간 인덱스 (검색 범위의 중간) end 배열의 끝 인덱스 (검색 범위의 끝) 이진 검색을 위해서 다음과 같이 정의 하였으면 이제 구.. 2020. 2. 13.

[알고리즘-PS] Java에서 선형 검색 구현하는 방법. 검색하는 방법중 가장 기본적이며 자주 사용하는 알고리즘으로 알고리즘을 처음 학습한다면 필수로 알아야 한다. 선형 검색 알고리즘 정의 선형 검색이란 요소가 직선 모양으로 늘어선 배열에서 원하는 값을 찾기 위해 0번째 index에서 부터 배열의 끝까지 순차적으로 index를 비교하여 값을 찾는 알고리즘이다. 종료 조건 조건 1 : 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 조건 2 : 검색할 값과 같은 요소를 발견한 경우 시간 복잡도 입력 배열의 길이가 n 인 경우 n/2 소스 코드 실행 결과 선형 검색의 보초법 선형 검색은 반복할 때 마다 종료 조건을 모두 검사한다. 하지만 이 비용을 절반으로 줄일 수 있는 방법이 바로 선형검색의 보초법이라고 한다. 보초법은 arr[0] ~ arr[5] 까지 있.. 2020. 2. 12.

[알고리즘 문제 풀이 스킬] 자바에서 int형 숫자의 자릿수를 구하는 방법. feat. 백준 2577번 211300291는 몇 자리 수 일까? 백준 알고리즘 2577번:숫자의 개수 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 같거나 크고, 1,000보다 작은 자연수이다. www.acmicpc.net 문제를 풀다 보니 연산 결과의 자리 수를 알아야하는 문제가 나왔는데 이런 비슷한 경우에 사용하면 좋을것 같아서 공유하고자 한다. 숫자의 자리수를 확인할 때는 2가지 방법이 존재한다. int 형 변수를 문자열로 변환하고 해당 문자열의 길이를 구하는 방법 Math 라이브러리를 이용해서 자리수를 구하는 방법 사실 대부분의 경우에는 1번 방법이 훨씬 가독성이 좋고 편하지만, 특정 상황에서도 언젠간 필요할 수 있는 Math 라이브러리를 이용한 방법도.. 2020. 1. 20.

이전 1 ··· 20 21 22 23 24 25 다음

티스토리툴바