CS

재귀(Recursion) 알고리즘과 피보나치 수열

1. 재귀 알고리즘 재귀(Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출해서 문제를 해결하는 함수를 말한다. 재귀함수는 자신의 로직을 내부적으로 반복하여 문제를 해결하고 조건이 만족되면 함수를 이탈해서 결과를 도출한다. 따라서 재귀함수는 함수 내에서 자기 자신을 계속 호출하기 때문에 반드시 종료하는 부분을 정확히 구현해야한다. 그리고 함수를 호출할 때마다 메모리상에서 추가적으로 생긴다. public class Recursion_Test { public static void main(String[] args) { recursion(); } //재귀함수 public static void recursion(){ System.out.println("안녕하세요"); recursion(); } ..

재귀함수를 이용해 배열의 최대값찾기

재귀(Recursion) 먼저 재귀(Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출해서 문제를 해결하는 함수를 말한다. 재귀함수는 자신의 로직을 내부적으로 반복하여 문제를 해결하고 조건이 만족되면 함수를 이탈해서 결과를 도출한다. 따라서 재귀함수는 함수 내에서 자기 자신을 계속 호출하기 때문에 반드시 종료하는 부분을 정확히 구현해야한다. Java Code public class RecursionEx03Ver2 { public static int arr[] = {1, 2, 4, 8}; public static void main(String[] args) { int n = arr.length; System.out.println(recursion(n)); } public static int..

그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘그리디 알고리즘은 다른 말로 탐욕법이라고한다. 이름에서 알수 있듯이 어떠한 문제가 있을 때 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’을 의미한다. 모든 선택지를 고려하고 그중 전체 답이 가장 좋은 것을 찾아야하는 다른 알고리즘 방법과 다르다. 코딩테스트에서 그리디 알고리즘 유형의 문제는 매우 다양해서 암기한다고 잘 풀 수 없다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다. 따라서 이런 기준을 정렬 알고리즘을 사용했을 떄 만족시킬 수 있으므로 정렬 알고리즘과 짝을 이뤄 출제된다. 위와 같은 트리가 존재할 때..

이진 탐색(Binary Search)

이진탐색을 알기전에 먼저 순차탐색을 알아야한다. 순차탐색(Sequential Search)는 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 배열에서 데이터를 찾아야 할 때 사용한다. 배열에서 원소의 개수를 확인하는 count() 메서드를 이용할때도 내부에서는 순차 탐색이 수행된다. 이진탐색 이진 탐색(Binary Search)는 반으로 쪼개면서 탐색하는 방법 으로 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일때는 사용할 수 없지만 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있는 특징이 있다. 이진탐색은 위치를 나타내는 변수 시작점, 끝점, 중간점을 사용한다. 찾으려는 데이터와 중간점 ..

퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort) 퀵 정렬은 이름처럼 가장 많이 사용되고 있는 빠른 정렬 알고리즘이다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬방법이다. 퀵 정렬에는 피벗(Pivot)이 사용되는데 이 피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ’기준’을 말한다. 퀵정렬을 수행할때는 피벗을 어떻게 설정할지는 미리 명시해야하는데 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식으로 설명하겠다. (참고로 피봇을 정하는 기준에서 수행시간의 차이가 존재한다. ) 호어 분할 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 정한다. 따라서 피벗을 정한 뒤에 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. ..

삽입정렬(Insertion sort)

삽입정렬(Insertion Sort) 정렬 알고리즘은 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다. 프로그램에서 데이터를 가공할 떄 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해 사용하는 경우가 많아서 가장 많이 사용되는 알고리즘이다. 데이터를 정렬하면 이진탐색(Binary Search)이 가능하다. 삽입정렬은 특정한 데이터를 적절한 위치에 ‘삽입’한다는 의미에서 삽입정렬이다. 따라서 삽입정렬은 선택정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간측면에서 더 효율적이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어있을 때’ 훨씬 효율적이다. 선택 정렬은 현재데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸면 반면 삽입 정렬을 그..

Ip와 IP 클래스, CIDR, 서브넷

1. IP 기기의 주소를 나타내는 것이 IP 주소이다. 1.1 공인IP ISP가 제공하는 IP주소이자 유일한 IP 주소를 갖는다 . 외부에 공개되어있기 때문에 다른 PC로부터 접근이 가능하며, 따라서 이 IP를 사용하는 경우에는 방화벽 등의 보안 프로그램을 설치해야한다. 1.2 사설IP (= 로컬 ,가상 ip) 라우터에 의해 할당된 ip를 말한다. 외부 접근 불가능하고 , 내부망 안에서만 접근 가능하다. IPv4의 주소부족으로 인해 서브넷팅된 IP를 말한다. ipconfig에 나오는 ip가 사설ip이다. 2. IP 클래스 IP주소는 대역에 따라 A,B,C,D,E 클래스로 나뉜다. 이 클래스들을 구분함으로써 클래스 내에서 Network ID와 Host ID를 구분하게 된다. 네트워크 ID란 네트워크를 구분..

hosts 파일

1. hosts 파일 ip 주소와 도메인 주소를 매핑해주는 파일이다. 호스트 이름에 대응하는 ip주소가 저장되어 있어서 DNS(Domain Name System)에서 주소 정보를 제공받지 않아도 서버의 위치를 찾게 해주는 파일을 말한다. 즉, 주소창에 url을 입력했을때 가장 먼저 hosts 파일의 정보를 먼저 읽어보고 해당 내용이 없으면 DNS에 접속을 한다. 만약에 이렇게 ip주소와 도메인 주소를 hosts파일에 저장하고, 해당 도메인 주소를 호출하면 실제 www.memm.com 주소로 접속되지 않고, 내가 설정한 111.111.111.111로 접속이 된다. 111.111.111.111 www.memm.com 1.1 파일 위치 //윈도우의 호스트파일 위치 C:\\Windows\\System32\\dr..