배열과 리스트

• 배열
  • 메모리의 연속 공간에 값이 채워져 있는 형태의 자료 구조
  • 값은 인덱스 통해 참조
  • 값을 삽입, 삭제하기 위해선 해당 인덱스 주변의 값을 이동시키는 과정이 필요
  • 크기는 선언할 때 지정, 크기는 수정 불가
• 리스트
  • 값과 포인터를 묶은 노드라는 것을 포인트로 연결한 자료구조
  • 값에 접근하기 위해선 Head 포인터부터 순서대로 접근(느림)
  • 포인터로 연결되어 있어 삽입 삭제 빠름
  • 크기가 정해져 있지 않아 변하기 쉬운 데이터를 다룰 때 적절
• 문제 001 숫자의 합 구하기
  • 문자열을 문자 배열로 변환: tocharArray
  • 문자 배열 값 숫자형으로 변환: ‘5’ - 48(’0’) = 5

구간 합

**배열 고정되어 있고 질의의 수가 많을 때 적합(시간복잡도 줄이기 위한 알고리즘)

• 합 배열 공식

  • S[i] = S[i-1] + A[i]
  • 이처럼 합 배열은 구하기가 매우 쉽기 때문에 데이터 받으면서 바로 구할 수 있음

• i~j까지의 구간 합 구하는 공식

  • S[j] - S[i-1]

• 문제 003 구간 합 구하기

  • 0.5초 안에 값이 나와야 하므로 더 빠른 입력을 위해 BufferReader 사용
  • 받을 수 있는 수의 갯수가 10만개라면, 한 줄에 굉장히 많은 데이터가 들어오기 때문에 int로 못 받음
  • 토큰으로 값을 분리해 받기 위해 stringtokenizer 사용

    • 또한, BufferedReader 클래스의 메서드로 입력을 읽어들인다면 라인 단위로 읽어들일 수 밖에 없음

      출처:

      https://dev-coco.tistory.com/94

      [슬기로운 개발생활:티스토리]

• 문제 004 구간 합 구하기2

  • 공식 적용하고 그림 그려가면서 하면 이해 쉬움 허나 코테에서 이런 문제 나오면 남들 다다닥 타자 칠 때 나는 그림 교실 열고 끄적여야 함..
  • 2차원 구간 합 배열 D[X][Y]
    • 원본 배열의 (0,0)부터 (x,y)까지의 사각형 영역 안에 있는 수의 합
  • D[i][j]의 값을 채우는 구간 합 공식
    • D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

• 문제 005 나머지 합 구하기

  • 배열 고정되어 있고 10^6개의 수에 대해 구간 합에 대한 질의에 수가 많으므로 구간합 배열 이용
  • 아니 책에서 말한 아이디어가 어떻게 이렇게 떠오르냐..? 뭐냐..?
    • 책에서 말한 아이디어 이해하는 것도 어려웠음;; 이거 글로 어케씀

투 포인터

• 최대값이 억단위로 크게 잡혀있는 경우 O(nlogn)보단 O(n) 시간 복잡도를 이용해야 함

  • 시간 복잡도가 왜 N인가?
  • M번씩 훑어서 MN이 나와도 시간 복잡도는 상수 M을 날림 따라서 N

• 이런 경우 사용하는 것이 투 포인터

• 문제 007 주몽의 명령

  • N의 최대 범위가 15000이므로 O(nlogn)을 사용해도 되나 입력받은 N개의 수를 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근

    ⇒ 2개를 뽑아서 값을 만들면 답이 나옴(뽑은 2개는 다음부터 상관없고) 이를 빨리 찾기 위해 투 포인터 사용

  • 정렬 알고리즘의 시간 복잡도는 O(nlogn), 자바에선 Arrays.sort(A)

• 문제 008 ‘좋은 수’ 구하기

  • 어떻게 투 포인터 정렬임을 알 수 있는가?

  → 문제 설명 중 ‘두 수’에서 힌트, 정렬해 놓고 구하면 편하니까

  • 주의) 정렬된 수에서 자기 자신은 포함X!

슬라이딩 윈도우

• 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제 해결
• 문제 009 DNA 비밀번호
  • 문자열 크기가 백만이므로 O(n)의 시간복잡도 알고리즘으로 해결
  • 범위(window)를 지정해 이 범위를 유지한 채로 현재 상태 배열과 체크 배열을 두고 비교해가야함
  • 부분 문자열 크기가 커도 옮길 때(한 칸 이동할 때)마다 양 끝 두 개의 데이터만 넣고 빼면 됨