Do-It Algo- 시간복잡도

본 Do-It 시리즈 포스팅은, Do-it! 알고리즘 코딩 테스트 java편을 기반으로 작성됩니다. 

1.Intro

  오늘은 배열과 리스트, 리스트는 프로젝트에서 많이 다루어 보았지만, 배열은 상대적으로 더 다뤄보지 못해 오늘의 알고리즘 풀이는 배열로 결정

 

1.배열

 -메모리의 연속 공간에 값이 채워져 있는 형태의 자료 구조 

- 배열의 값은 인덱스를 통해 참조가 가능하며, 선언한 자료형의 값만 저장 가능

 

 1. 시간 복잡도란? 

    1. 인덱스를 사용하여 값에 바로 접근이 가능하다 
    2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제 하기 어려움, 
        -> 값을 삽입 or 삭제 하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요 
    3.배열의 크기는 선언할 때 지정 가능, => 선언된 크기는 변경 불가. 
    4. 간단한 구조로 코테에서 많이 활용 됨 

 

2.리스트란?    

=>값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조    
  리스트 특징 
     1. 인덱스가 없으므로 값에 접근하려면 Head 포인터로부터 순서대로 접근해야 함, => 값에 접근하는 속도 느림 
     2. 포인터로 연결되어 있어 데이터를 삽입하거나 삭제하는 연산 속도가 빠름 
     3. ㅅ너언할 때 크기를 별도로 지정하지 않아도 된다. - > 리스트의 크기는 가변적 
     4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다. 
   

3.Ex01 숫자합 구하기 

  시간제한 1초
 N개의 숫자가 공백없이 써져있고, 이 숫자를 모두 합해 출력하는 프로그램 작성 
 1번째 줄에 숫자의 개수  N, 2번째 줄에 숫자 N개가 공백없이 주어진다. 

 

	public static void main(String[] args) {
		System.out.println("숫자의 개수");
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		System.out.println("숫자 입력");
		String target = sc.next();
		
		int result =numsum(N, target);
		System.out.println(result);
	}
	
	private static int numsum(int N, String target) { 
		int result = 0;
		String[] sc = target.split("");
		for(int i = 0; i < N  ; i++) {
			result += Integer.parseInt(sc[i]);
		}
		
		return result;
	}

교재에서는 bufferReader와 StringToekenizer를 사용해서 사용자에게 값을 입력 받던데, BufferReader는 많이 사용해봤지만 String Tokenizer는 생소하여, Scanner를 활용하여 풀어보았다. 

그래서 위 세 가지의 차이점을 오늘 좀 Algo 가려고 한다. 

 

 

Scanner

- 기본적인 타입 Scanner의 타입 메소드를 활용해 쉽게 타입 지정 가능 

- 공백 또는 개행을 기준으로 읽음. -> ' ', '\t', '\r', '\n' 등의 특수문자가 사용 가능,,? 이건 추후 테스트 예정

-반면 버퍼를 사용하지 않기 때문에, 키보드의 입력이 키를 누르는 즉시 바로 프로그램에 전송한다. 

BufferReader

키보드의 이력이 있을 때마다 한 문자씩 버퍼로 전송하는 방식 -> 버퍼가 가득 차거나 혹은 개행 문자가 나타나면 버퍼의 내용을 한번에 프로그램으로 전달한다. 

StringTokenizer

StringTokenizer 클래스는 문자열을 우리가 지정한 구분자로 문자열을 쪼개주는 클래스입니다. 그렇게 쪼개어진 문자열을 우리는 토큰(token)이라고 부릅니다.

 

StringTokenizer도 입출력을 도와주는 라이브러리인 줄 알았는데 그건 아니었던 모양이다...

 

 

4.Ex02 평균 구하기  

 세준이는 기말 고사를 망쳐서 점수를 조작하기로 했다. 
  일단 세준이는 자기 점수중 최댓값을 골랐다. ㄷ그런 다음 최댓값을 M이라고 할 때 모든 점수를 점수/M *100으로 고쳤다.
  이때 새로운 평균을 구하는 프로그램을작성하시오
 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("과목 갯수입력");
		System.out.println("각 과목의 시험 성적 입력");
		int num = 1;
		String score = "1 100 100 100";
		double result = CustomAvg(score);
		System.out.println(result);
		
	}
	
	public static double CustomAvg(String target) {
		double result = 0;
		String[] score = target.split(" ");
		int Max = 0;
		for(int i = 0; i<score.length; i++) {
			int tar = Integer.parseInt(score[i]);
			if(Max < tar) {
				Max = tar;
			}
		}
		System.out.println(Max);
		double[] custom = new double[score.length];
		double sum = 0;
		for(int j = 0; j<score.length; j++) {
			custom[j] = (Double.parseDouble(score[j])/Max) * 100;
			System.out.println(custom[j]);
			sum += custom[j];
		}
		result = sum/custom.length;
		return result;
	}

 

 

5.Outro

책에서는 수도 코드를 통해 구조화를 하여 알고리즘을 푸는 것을 권장하고 있다. 

하지만 습관이 습관인지라,, 그게 잘 되지 않는다.. 

다음 부터는 조금 더 의식을 하며 풀어보기도 하여야 할 것 같다. 

또, 유지 보수성이 좋지 않다고 느낀다. 주석 좀 잘 달자,,,