NAIAHD

02-1 배열

자료구조 data structure : 데이터 단위와 데이터 사이의 물리적 또는 논리적인 관계

배열 array 

배열은 같은 자료형의 변수로 이루어진 구성요소component가 모인 것입니다.

구성요소

구성 요솟수(길이)

배열의 구성 요소는 자동으로 0으로 초기화 되는 규칙이 있습니다.

배열의 복제 

a.clone()

주사traverse: 배열의 요소를 하나씩 차례로 살펴보는 과정을 알고리즘 용어 

Random클래스의 인스턴스는 일련의 의사 난수를 생성합니다.

난수는 무에서 생성되는 것이 아니라 seed이라는 수의 값을 바탕으로 여러 연산을 수행하여 얻습니다

배열 a의 최댓값 구하기

static int maxOf(int[] a){

  int max = a[0];

  for (int i = 1; i < a.length;i++)

    if (a[i] > max)

      max = a[i];

  return max;

}

배열 요소를 역순으로 정렬하기 

static void swap(int[] a, int idx1, int idx2){

  int t = a[idx1];

  a[idx1] = a[idx2];

  a[idx2] = t;

}

static void reverse(int[] a){

  for(int i = 0; i <a.length/2; i++)

    swap(a, i, a.alength-i-1);

}

두 배열의 비교

static boolean equals(int[] a, int[] b){

  if(a.length != b.length)

    return false;

  for (int i = 0; i < a.length;i++)

    if(a[i] != b[i])

      return false;

  return true;

}

기수 변환

정수값을 임의의 기수로 변환하는 알고리즘 

기수: 수를 나타내는데 기초가 되는 수

서수 사물의 순서를 나타내는 수 

static int cardConvR(int x, int r, char[] d){

  int digits = 0;

  String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  do {

    d[digists++] = dchar.charAt(x%r);

    x /= r;

   }while(x != 0);

   return digits;

}

전위형 증가 연산자 ++a

++를 앞에 놓으면 식 전체를 평가하기 전에 피 연산자의 값을 증가시킵니다.

후위형 증가 연산자 a++

++를 뒤에 놓으면 식 전체를 평가한 후에 피연산자의 값을 증가시킵니다.

다차원 배열: 

int[][] x = new int[2][4]

2행 4열

서기 year년은 윤년인가?

static int isLeap(int year){

  return (year % 4 == 0 && year $ 100 != 0 || year % 400 == 0 ) ? 1:0;

}

02-2클래스

클래스: 여러 형의 요소를 조합하여 만든 자료구조 

필드 filed데이터 요소

공개클래스 : 클래스 접근 제한자 public을 붙여 선언한 클래스로 , 다른 패키지에서 사용할 수 있는 것

final 클래스 : 클래스 접근 제한자 final을 붙여 선언한 클래스로 , 서브 클래스를 가질 수 없습니다. 

(새로운 클래스를 상속할 수 없습니다.)

파생클래스 :

  direct superclass

  direct subclass

추상클래스 : abstract

중첩클래스 : nested class

출처 : Do it ! 자료구조와 함께 배우는 알고리즘 입문 자바편

알고리즘: 간단히 말해 '어떤 문제를 풀기 위한 절차나 방법'입니다.

입력 ->과정 -> 출력

문제: 어떤 숫자의 절댓값 구하기

입력 : 절댓값을 구할 실수 a

출력 : a의 절댓값

알고리즘 분석: 알고리즘의 성능이나 특징을 분석하는 것 

첫째마당 알고리즘 기초

문제 01: 1부터 n까지의 합 구하기

입력 : 1....2

출력 : 5050

입력 -> 알고리즘 -> 출력

def sum_n(n):

  s = 0

  for i range(1,n+1):

    s = s + i

  return s

알고리즘 분석: 

def sum_n(n):

  return n * (n+1) //2

계산복잡도 complexity:어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도

02. 최댓값 찾기

def find_max(a):

  n = len(a)

  max_v = a[0]

  for i in range(1,n):

    if a[i] > max_v:

      max_v = a[i]

  return max_v

03. 동명이인 찾기

def find_same_name(a):

  n = len(a)

  result = set()

  for i in range(0,n-1):

    for j in range(i+1, n):

      if a[i] == a[j]

        result.add(a[i])

  return result

02. 재귀호출

재귀호출은 함수가 자기 자신을 다시 호출하는 것을 뜻합니다.

04. 팩토리얼 구하기

1부터 n까지의 곱 , 즉 팩토리얼 구하는 문제 

• 1.팩터리얼 

def fact(n):

  f = 1

  for i in range(1, n+1):

    f = f*i

  return f

• 2. 러시아 인형

• 3. 재귀호출 : 다시 돌아가 부르기

RecursionError:특정 조건이 되면 더는 자신을 호출하지 않고 멈추도록 설계하지 않으면 

계속 반복하다가 재귀 에러가 난다. 

• 4. 재귀호출 알고리즘

def fact(n):

   if n <= 1:

     return 1

   return n * fact(n-1)

• 5. 알고리즘 분석

계산 복잡도 O(n)

종료 조건이 없으면 재귀 에러 나 스택 오버플로 등 프로그램 에러가 발생해 비정상적인 

동작을 할 수 도 있다. 

05. 최대 공약수 구하기 

두 자연수 a와 b의 최대 공약수를 구하는 알고리즘

• 1. 최대 공약수 알고리즘

최대 공약수 성질

1. 두 수 중 더 작은 값을 i에 저장한다.

2. i가 두 수의 공통된 약수인지 확인한다.

3. 공통된 약수이면 이 값을 결괏값으로 돌려주고 종료한다.

4. 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복합니다.(1은 모든 

정수의 약수이므로 i가 1이되면 1을 결괏값으로 돌려주고 종료합니다.

def gcd(a,b):

  i = min(a,b)

  while True:

     if a % i == 0 and b % i ==0:

        return i

     i = i - 1

• 2. 유클리드 알고리즘 

def gcd(a,b):

  if b == 0:

    return a

  return gcd(b, a % b)

06. 하노이의 탑 옮기기 

• 1. 하노이의 탑 

간단한 원반 옮기기 퍼즐 이다.

크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮겨야 한다.

원반은 한 번에 한 개씩만 옮길 수 있다

원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아 , 다른 기둥의 맨 위로만 옮길 수 있다.

원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없다.

• 2. 하노이의 탑 
• 3. 하노이의 탑 알고리즘 

1-A: 원반이 한개면 그냥 옮기면 끝 (종료 조건)

1-B: 원반이 n개일 때

   1 : 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮깁니다.

   2 : 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮깁니다.

   3 : 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮깁니다.

def hanoi(n , from_pos, to_pos, aux_pos)

   if n == 1:

     print(from_pos , "->", to_pos)

     return

   honoi(n-1, from_pos, aux_pos, to_pos)

   print(from_pos,"->", to_pos)

  honoi(n-1, aux_pos, to_pos, from_pos)

• 4. 알고리즘 분석 

O(1): n과 무관하게 일정한 시간이 걸림

O(n): n과 비례하여 계산 시간이 증가함

O(n^2): n의 제곱에 비례하여 계산 시간이 증가함

O(2^n): 2의 제곱에 비례하여 계산 시간이 증가함

출처: 모두의 알고리즘 with python

01-1 알고리즘이란 ?

세 값의 최대값 : 

int max = a;
if(b > max) max = b;
if(c > max) max = c;

이렇게 여러 문장(프로세스)이 순차적으로 실행되는 구조를 순차적(concatenation)구조라고 합니다.

세 값의 중앙값 :

if (a >= b)

  if (b >= c)

    return b;

  else if (a <= c)

    return a;

  else 

    return c;

else if (a > c)

  return a;

else if(b>c)

  return c;

else 

  return b;

연산자: 기호 +- 등

피 연산자 숫자

01-2 반복 

1부터 n까지의 정수 합 구하기 

int sum = 0;

int i = 1;

while ( i <= n){

  sum += i;

  i++;

}

===> 사전 판단 반복 구조 

for 문 반복

int sum = 0;

for (int i = 1; i <= n; i++){

  sum += i;

}

사전 판단 반복: while문과 for문은 처음에 제어식을 평가한 결과가 0이면 루프 본문은 한번도 실행되지 않습니다.

사후 판단 반복: do문은 루프 본문이 반드시 한번 은 실행됩니다.

구조적 프로그래밍: 하나의 입구와 출구를 가진 구조 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법

단축 평가(short circuit evaluation) 논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우 오른쪽 피 연산자의 평가를 수행하지 않는데 이를 단축평가라로 합니다.

드로르간 법칙 (De Morgan's laws): 각 조건을 부정하고 논리곱을 논리합으로 , 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.

다중 루프 

곱셈표 :

for (int i = 1; i<=9; i++){

  for (int j = 1; j<=9; j++){

    System.out.printf("%3d",i*j);

  }

}

직각 이동변 삼각형 출력

for(int i=1; i<=5;i++){

  for (int j=1;j<=i;j++){

    System.out.print("*")

  }

  System.out.println();

}

출처 : Do it ! 자료구조와 함께 배우는 알고리즘 입문 자바편