목차
  • 범위를 반씩 좁혀가는 탐색
  • [실전 문제] 부품 찾기
  • [실전 문제] 떡볶이 떡 만들기

 

범위를 반씩 좁혀가는 탐색
  • 순차 탐색(Sequential Search)
    • 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
    • 정렬되지 않은 리스트에서 데이터를 찾을 때 사용
    • 시간 복잡도 O(N)
  • 이진 탐색(Binary Search) : 반으로 쪼개면서 탐색하기
    • 배열 내부의 데이터가 정렬되어 있어야 사용 가능
    • 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.
    • 변수 3개 사용 : 시작점, 끝점, 중간점
    • 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
    • 동작 원리
      • 시작점[0]과 끝점[9]을 확인하고, 중간점(나누고, 소수점을 버린다)[4]을 정한다. 
      • 구하려는 값 4가 중간점[4] 작을 경우, 오른쪽 값은 상관없이 끝점을 중간점 보다 한 칸 앞으로 끝점[3]으로 옮긴다.
      • 시작점[0]과 끝점[3]과 중간점[1]에서 중간점[1]보다 4가 더 클 경우, 시작점을 중간점 보다 한 칸 뒤로 시작점[2]으로 옮긴다.
      • 시작점[2]과 끝점[3] 중간점[2]으로, 구하려는 값 4와 동일하기 때문에 탐색을 종료한다.
    • 이진 탐색을 한 번씩 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다 -> 시간 복잡도 O(logN)
    • 이진 탐색 구현 방법 2가지
      • 재귀 함수
      • 반복문
    • 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근해보자.

 

  • 트리 자료구조
    • 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree) 자료구조를 이용하여 항상 데이터가 정렬되어 있다.
  • 이진 탐색 트리
    • 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
    • 이진 탐색 트리의 특징
      • 부모 노드보다 왼쪽 자식 노드가 작다.
      • 부모 노드보다 오른쪽 자식 노드가 크다.
    • 출제 빈도가 낮다.

 

 

실전 문제 (1)
  • 부품 찾기

5개의 부품 번호 8,3,7,9,2에서 3개의 부품 번호 5,7,9가 있는지 확인

  • 문제 요약
    • 부품 N개
    • M개의 종류
    • N개의 부품 번호 중에 M개의 종류가 있는지 확인하는 프로그램
  • 문제 해석
    • N개의 부품을 번호를 기준으로 정렬
    • M개의 찾고자 하는 부품이 각각 존재하는지 확인
    • (정렬되어 있기 때문에) 이진 탐색 사용

 

실전 문제 (2)
  • 떡볶이 떡 만들기

  • 문제 요약
    • 떡의 개수 N개
    • 요청한 떡의 길이 M
    • 서로 다른 높이의 떡이 있을 경우, 같은 높이로 떡을 잘랐을 때 남는 떡의 총 길이는 M이다.
    • 남는 떡의 총 길이를 M으로 만드는 높이의 최댓값을 구하는 프로그램
  • 문제 해석
    • 이진 탐색 문제
    • 파라메트릭 서치(Parametric Search) 유형
      • 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
      • 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용
      • 일반적으로 재귀 함수보다, 반복문 구현이 더 간결하다.
      • ex.범위 내에서 조건을 만족하는 가장 큰 값을 찾는 문제일 경우, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
    • 현재 이 높이로 잘랐을 경우, 조건을 만족하는지 확인 -> 조건의 만족 여부(yes or no) 확인 후 탐색 범위 좁히기(이진 탐색)
    • 문제 풀이
      • 시작점 0, 끝점 19 -> 중간점 9 -> 얻는 떡 25은 6보다 크기 때문에 시작점 증가
      • 시작점(중간점+1) 10, 끝점 19 -> 중간점 14 -> 떡의 합계 9은 6보다 크기 때문에 시작점 증가
      • 시작점(중간점+1) 15, 끝점 19 -> 중간점 17 -> 떡의 합계 2은 6보다 작기 때문에 끝점 감소
      • 시작점15, 끝점(중간점-1) 16 -> 중간점 15 -> 떡의 합계(4+0+0+2) 6은 조건 만족
목차
  • 기준에 따라 데이터를 정렬
  • [실전 문제] 위에서 아래로
  • [실전 문제] 성적이 낮은 순서로 학생 출력하기
  • [실전 문제] 두 배열의 원소 교체

 

 

기준에 따라 데이터를 정렬
  • 정렬(Sorting)
    • 데이터를 특정한 기준에 따라서 순서대로 나열
    • 이진 탐색(Binary Search)에서 사용
    • 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
    • 리스트를 뒤집는 연산 시간 복잡도 : O(N)
  • 선택 정렬(Selection Sort)
    • 매번 가장 작은 것을 선택하는 알고리즘
    • 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 전체 데이터 정렬이 이루어진다.
    • 시간 복잡도 : O(N^2)
      • N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
      • N X (N+1) / 2 = (N^2 + N) / 2 = O(N^2)
  • 데이터가 늘어날 경우의 정렬 수행 시간(파이썬 기준)

 

  • 삽입 정렬(Insertion Sort)
    • 특정한 데이터를 적절한 위치에 삽입
    • 그 앞의 데이터들은 이미 정렬되어 있다고 가정한다.
    • 첫 번째 데이터는 그 자체로 정렬되어 있다고 생각하기 때문에 두 번째 데이터부터 시작한다.
    • 시간 복잡도 O(N^2)
    • 현재 리스트의 데이터가 거의 정렬되어 있는 상태일 경우 매우 빠르게 동작한다.

 

  • 퀵 정렬(Quick Sort)
    • 가장 많이 사용되는 알고리즘
    • 기준을 설정한 다음 큰 수와 작은 수를 교환한 후에 리스트를 반으로 나누는 방식으로 동작한다.
    • 피벗(Pivot)이 사용되고, 다양한 분할 방법이 있다.
    • 호어 분할(Hoare Partition) : 가장 대표적인 분할 방식. 리스트에서 첫 번째 데이터를 피벗으로 정한다.
      • 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 
      • 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
      • 왼쪽과 오른쪽에서 찾는 값이 엇갈린 경우 작은 데이터와 피벗의 위치를 서로 변경해준다.
      • 분할 = 파티션(Divide = Partition) : 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업
      • 파티션이 완료된 상태에서 왼쪽 배열을 정렬 오른쪽 배열을 정렬
      • (퀵 정렬 종료 조건) 현재 리스트의 데이터 개수가 1개인 경우, 이미 정렬이 되어 있다고 간주하여 분할이 불가능하다.
    • 시간 복잡도 평균 : O(NlogN), 최악의 경우 : O(N^2)
    • 무작위 데이터는 빠르게 동작할 확률이 높지만, 왼쪽 데이터를 피벗으로 삼을 때 이미 데이터가 정렬되어 있는 경우라면 매우 느리게 동작한다.
    • 데이터 유형을 파악하기 어렵다면 퀵 정렬을 사용하는 것이 유리하다.

 

  • 계수 정렬(Count Sort)
    • 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
    • 데이터 개수 N, 최대 값 K 
    • 최악의 경우에도 수행 시간 O(N + K) 보장
    • (제한 조건) 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 -> 리스트(배열)을 선언해야 되기 때문
    • 0이상 100이하인 성적 데이터 정렬에 효과적이다.
      • 모든 범위를 담을 수 있는 배열을 생성하고, 모든 데이터를 0으로 초기화한다.
      • 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시켜준다.

 

JAVA 정렬 라이브러리
  • Arrays.sort() 
    • 듀얼 피봇 퀵 정렬 사용
    • 시간 복잡도
      • 평균 O(Nlog(N)
      • 최악의 경우 O(N^2)
  • Collection.sort()
    • Timesort 사용
      • 삽입 정렬과 합병 정렬을 결합하여 만든 정렬
    • 시간 복잡도 
      • 평균 O(Nlog(N))
      • 최악의 경우 O(Nlog(N))
      • 최선의 경우 O(N)
    • 삽입 정렬을 사용하는데 O(N^2)이 나오는 이유
      • 삽입 정렬은 인접한 메모리와 비교를 반복하기 때문에 참조 지역성의 원리를 만족하고 있다.
      • 작은 n 에 대하여 삽입 정렬이 빠른 속도를 보여준다.
      • (아이디어) 전체를 작은 덩어리로 잘라 각각의 덩어리를 삽입 정렬을 사용하여 병합하면 좀 더 빨라질 것이다.
      • 참고 글
      • https://d2.naver.com/helloworld/0315536

 

 

실전 문제 (1)
  • 위에서 아래로

  • 문제 요약
    • 하나의 수열을 내림차순으로 정렬하는 프로그램
  • 문제 해설
    • 수의 개수가 500개 이하로 매우 적기 때문에, 모든 수는 1~100,000개이다. 어떠한 정렬 알고리즘이어도 상관 없기 때문에 가독성을 위해 기본 정렬 라이브러리를 사용한다.

 

실전 문제 (2)
  • 성적이 낮은 순서로 학생 출력하기

  • 문제 요약
    • N 명의 학생
    • 학생의 정보 - 이름, 성적
    • 성적이 낮은 순서대로 학생 이름을 출력하는 프로그램
  • 문제 해설
    • 학생의 정보가 최대 100,000개이므로, 최악의 경우 O(NlogN)을 보장하는 알고리즘 혹은 O(N)을 보장하는 계수 정렬 사용

 

실전 문제 (3)
  • 두 배열의 원소 교체

 

  • 문제 요약
    • 두 개의 배열 A, B은 N개의 원소로 구성
    • 배열의 원소는 모두 자연수
    • 최대 K번 바꿔치기 연산 수행 : 배열 A의 원소와 배열 B의 원소 하나를 골라서 서로 바꾸는 것
    • 배열 A의 모든 원소 합의 최대값을 출력하는 프로그램
  • 문제 해설
    • 매번 배열 A에서 가장 작은 원소를 고르고, 배열 B에서 가장 큰 원소와 교체한다.
    • 배열 A의 원소를 오름차순 정렬 후, 배열 B 원소를 내림차순 정렬한다.
    • 그리고 두 배열의 원소를 가장 첫 번째 인덱스부터 비교해나간다.
    • 단, 배열 A에서 가장 작은 원소 < 배열 B에서 가장 큰 원소 일 경우에만 수행
목차
  • 꼭 필요한 자료구조 기초 124
  • 탐색 알고리즘 DFS/BFS 134
  • [실전 문제] 음료수 얼려 먹기 149
  • [실전 문제] 미로 탈출 152

 

 

꼭 필요한 자료구조 기초
  • 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
  • 대표적인 그래프 탐색 알고리즘 : DFS(Depth First Search), BFS(Breadth First Search)
    • 스택, 큐, 재귀 함수 이해 필요

 

  • 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
    • 삽입(Push), 삭제(Pop)
    • 스택, 큐를 사용할 경우 삽입, 삭제 이외에도 overflow, underflow 고려 필요
      • 오버플로(Overflow) : 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 경우 발생
      • 언더플로(Underflow) : 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산 수행 시 발생

 

책에서는 파이썬으로 내용을 다루지만, 자바 기준으로 포스팅하겠습니다.
  • 스택(Stack) 
    • 선입후출(First In Out), 후입선출(Last In Frirst Out)
    • stack.push() : 스택에 원소를 삽입한다.
    • stack.pop() : 스택의 맨 위의 원소를 삭제한다.
    • stack.peek() : 스택의 맨 위의 원소를 출력한다.
    • stack.size() : 스택의 크기 출력
    • stack.empty() : 스택이 비어있는지 확인
    • stack.contains() : 함수 안에 있는 인자 값이 스택에 포함되어 있는지 확인
    • stack.clear() : 스택에 있는 모든 데이터를 한 번에 삭제한다.

 

  • 큐(Queue)
    • 선입선출(First In First Out)
    • queue.offer() : 큐에 원소를 삽입
    • queue.pool() : 큐에서 제일 처음(맨 앞)에 넣은 값을 삭제
    • queue.peek() : 값을 삭제하지 않고, 맨 앞의 값을 출력

 

 

  • 재귀 함수(Recursive Function) 
    • 자기 자신을 다시 호출하는 함수
    • 프랙털(Fractal) 구조와 흡사 : 시에르핀스키 삼각형
    • 종료 조건을 꼭 명시해야 한다.
    • 재귀 함수는 내부적으로 스택 자료구조와 동일하다.
    • ex. factorial : 반복문보다 재귀 함수를 사용한 이점은?
      • 간결한 코드 = 점화식 사용

 


탐색 알고리즘 DFS/BFS
  • 그래프 
    • 노드(Node) = 정점(Vertex)
    • 간선(Edge)
    • 그래프 표현 방식 2가지
      1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계 표현
      2. 인접 리스트(Adjacency List) : (연결)리스트로 그래프의 연결 관계 표현

그래프 표현 1 - 인접 행렬
그래프 표현 2 - 인접 리스트

 

  • 인접 행렬 vs 인접 리스트
    • 인접 행렬 : 모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리 낭비
    • 인접 리스트 : 연결된 정보만 저장하기 때문에 메모리 효율적, but 조회 속도 저하

 

  • 그래프 탐색
    • 하나의 노드를 시작으로 다수의 노드를 방문하는 것
    • 두 노드가 간선으로 연결 = 두 노드는 인접하다(Adjacent)

 

  • DFS(Depth-First Search) 깊이 우선 탐색
    • 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드 방문 후, 돌아가서 다른 경로 탐색
    • 데이터 개수가 N개일 경우 시간복잡도 : O(N)
    • 재귀함수 이용
      • 재귀 함수는 스택구조와 동일하지만, 실제로 스택을 사용하지는 않는다.(Stack Overflow)
    • 활용 문제
      • 백트래킹, 위상 정렬
        • 백트래킹 : 해를 찾는 도중, 찾는 해가 아닐 경우 되돌아가서 해를 찾는 방법
    • 동작 과정
      1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
      2. 스택의 최상단 노드에 방문하지 않은 인접 노드(white)가 있으면 그 인접 노드를 스택에 넣고 방문 처리(gray)를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (방문하지 않은 노드가 여러 개일 경우 번호가 낮은 순서부터 처리)
      3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
    • 노드의 탐색 순서(스택에 들어간 순서) 1->2->7->6->8->3->4->5

 

DFS 예제

 

 

  • BFS(Breadth First Search) 너비 우선 탐색
    • 가까운 노드부터 탐색하는 알고리즘
    • 시간복잡도 : O(N), 일반적인 경우 실제 수행 시간은 DFS보다 빠르다.
    • Queue 이용(선입 선출 방식)
    • 활용 문제
      • 최단 경로 찾기, 위상 정렬
    • 동작 과정
      1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
      2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. (인접한 노드가 여러 개일 경우, 숫자가 작은 노드부터 먼저 큐에 삽입)
      3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
    • 노드의 탐색 순서(큐에 들어간 순서) 1->2->3->8->7->4->5->6

BFS 예제

 

  • DFS vs BFS 방식 비교

 

 

  • 1차원 배열과 2차원 배열은 그래프의 형태로 바꿔서 생각할 수 있다. (단, 상하좌우로만 이동하는 경우)
  • DFS, BFS는 배열로 풀이 가능

 

 

실전 문제 (1)
  • 음료수 얼려 먹기

  • 문제 요약
    • N X M 크기의 얼음 틀
    • 구멍 0, 칸막이 존재 1 
    • 상하좌우로 붙어 있는 경우 연결되어(두 노드가 간선으로 연결) 있는 것으로 간주
    • 생성되는 아이스크림 개수 구하기
    • 위의 문제의 출력 값은 3

 

  • 문제 해설
    • 그래프에서 묶음을 찾아주는 프로그램은 어떻게 작성? -> DFS 사용
      1. 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
      2. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문 가능
      3. 1~2번의 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 센다.

 

실전 문제(2)
  • 미로 탈출

 

  • 문제 요약
    • N X M 크기의 미로
    • 현재 위치(1, 1)
    • 출구 위치(N, M)
    • 괴물이 있는 부분 0, 괴물이 없는 부분 1
    • 최소 이동 칸의 개수 구하기(시작, 마지막 칸 포함)

 

  • 문제 해설
    • 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드 탐색. 최단 거리 -> BFS 사용
    • (1, 1) 부터 모든 노드의 값을 거리 정보로 넣는다.
    • 특정 노드에 방문할 때 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.

출발 지점에서 출구 까지 BFS 수행한 결과

 

<참고> DFS와 BFS 시간 복잡도
인접 행렬 : O(N^2)
인접 리스트 : O(N+E)
목차
  • 아이디어를 코드로 바꾸는 구현
  • [실전 문제] 왕실의 나이트
  • [실전 문제] 게임 개발

 

 

아이디어를 코드로 바꾸는 구현
  • 구현(Implementation)
    • 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
    • 생각해낸 문제의 풀이 방법을 프로그래밍 언어로 정확히 구현해야 하기 때문에, 언어의 문법을 정확히 알고 있어야 한다.
    • 문제를 잘 읽고 요구사항에 어긋나지 않도록 맞춘다.
    • 이 책에서는 완전 탐색, 시뮬레이션 유형을 '구현' 유형으로 묶어서 다루고 있다.
      • 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
      • 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 ex. 상하좌우

 

  • 구현 시에 고려해야 하는 메모리 제약 사항
    • 예를 들어 int 자료형의 표현 범위는 -2.147,483,648 ~ 2,147,438,647 이며, 이 범위를 어긋나는 큰 수는 처리할 수 없다.
    • long long과 같은 자료형을 사용해야 하지만 9,223,372,036,854,775,807보다 큰 수를 처리할 수 없다.
    • 이보다 더 큰 BigInteger 클래스르 구현하거나 이용해야 하지만, 자바의 경우 표준 라이브러리로 지원을 한다. 하지만 라이브러리를 사용하지 못하는 경우도 있다. 
    • 코딩테스트에서 long long 보다 더 큰 정수를 처리하는 문제는 잘 출제되지 않는다.
    • 파이썬은 직접 자료형을 지정할 필요가 없다고 한다.....

 

  • 자바에서의 리스트 크기(추가 예정)
    • 대체로 코딩 테스트에서는 128~512MB 메모리 제한
    • 복잡한 최적화를 요구하는 문제를 거의 나오지 않는다.
  • 채점 환경
    • 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도는 O(NlongN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.
  • 구현에 접근하는 방법
    • C/C++, 자바로 문제를 풀 경우 구현 유형의 문제는 더 어렵다.
    • 문자열을 처리하거나 큰 정수를 처리하는 문제에서는 파이썬이 더 유용하다.
    • API 개발 문제 또한 구현 유형과 유사한데, 파이썬은 매우 간결하고 직관적인 코드의 라이브러리를 사용할 수 있어 유리하다.

 

예제1 - 상하좌우
  • N X N 크기의 정사각형 공간
  • 가장 왼쪽 위 (1, 1) 가장 오른쪽 아래 (N, N)
  • 상, 하, 좌, 우 방향으로 이동 가능 -> L 왼쪽, R 오른쪽, U 위로, D 아래로
  • 공간에서 벗어나는 움직임은 무시한다. ex. (1, 1)에서 L 혹은 U 는 무시

 

 

  • 문제 해설
    • 연산 횟수 = 이동 횟수
    • 이동 횟수가 N번일 경우 시간 복잡도 O(N) -> 넉넉한 편

 

예제2 - 시각
  • 정수 N이 입력되면, 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램 구하기
  • 00시 00분 03초, 00시 13분 30초

 

 

  • 문제 해설
    • 모든 시각의 경우를 하나씩 모두 세는 문제 -> 완전 탐색
    • 하루는 86,400초 -> 모든 경우의 수는 86,400가지 밖에 존재하지 않는다.
    • 완전 탐색 알고리즘은 탐색해야 하는 전체 데이터 개수가 100만 개 이하일 경우 가능
    • 이 문제에서는 매 시각을 문자열로 바꾼 후에 1초씩 늘리면서 3이 포함되었는지 탐색한다. 

 

 

실전 문제 (1) 
  • 왕실의 나이트

a1에서는 c2, b3으로 이동

 

  • 문제 요약
    • 8 X 8 체스판
    • L자 형태로만 이동 가능하고, 체스판 밖으로 나가지 못한다.
    • 2가지 경우로만 이동
      • 수평으로 두 칸 이동 후 수직으로 한 칸 이동
      • 수직으로 두 칸 이동 후 수평으로 한 칸 이동
    • c2에서 이동할 수 있는 경우의 수는 6가지
    • 입력에서 받은 위치에서 이동할 수 있는 경우의 수를 출력해라

 

 

  • 문제 해결
    • 상하좌우 문제와 유사
    • 평면을 벗어나지 않고, 2가지 경로로 움직일 수 있다.
    • 이동 경로를 steps 변수에 넣으면 2가지 규칙에 따라서
    • (-2, -1), (-1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1) 가 나온다.
    • 이 후에 평면 이내에 존재하는지 확인하고, 이 과정은 반복문으로 처리한다.

 

 

실전 문제 (2) 
  • 게임 개발
    •  

 

  • 문제 요약
    • N X M 크기의 공간
    • 동서남북으로 이동 가능
    • 현재 위치 1 X 1
    • 맵의 각 칸은 (A, B) -> A : 북쪽으로부터 떨어진 칸의 개수 / B :  서쪽으로부터 떨어진 개수
    • 북쪽 0, 동쪽 1, 남쪽 2, 서쪽 3
    • 이동 경로
      • 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
      • 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
      • 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
    • 캐릭터가 방문한 칸의 수를 출력하는 프로그램

 

  • 문제 해결
    • 시뮬레이션 문제
    • 일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적
    • 쪽을 바라보고 있고, 북쪽으로 이동하기 위해 x와 y좌표를 각각 dx[0], dy[0]만큼 더한다. => 현재 위치에서 (-1,0) 이동
    • 이처럼 반복문 코드를 작성하여 모든 방향을 차례대로 확인한다.
목차
  • 당장 좋은 것만 선택하는 그리디
  • [실전문제] 큰 수의 법칙
  • [실전문제] 숫자 카드 게임
  • [실전문제] 1이 될 때까지

 

 

당장 좋은 것만 선택하는 그리디
  • 그리디 알고리즘
    • 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
    • 현재 상황에서 지금 당장 좋은 것만 고르는 방법 -> 최적의 해가 아닌 경우가 많다.
    • 나중에 미칠 영향에 대해서는 고려하지 않는다.
    • 그리디 알고리즘은 코딩테스트에서 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많다.
      • 가장 큰 순서대로, 가장 작은 순서대로 등
      • 거스름돈
        • 500원, 100원, 50원, 10원 동전이 있을 경우 손님에게 거슬러줘야 하는 동전의 최소 개수
        • 해결 방법 : 가장 큰 화폐 단위부터 돈을 거슬러 준다.
        • 화폐의 종류만큼 반복 수행 -> 화폐의 종류가 K일 경우 -> 시간 복잡도 O(K)
        • 큰 단위가 항상 작은 단위의 배수 형태이므로, 최적의 해를 보장 가능
    • 코딩테스트 문제를 보고, 유형 파악이 어려울 경우 그리디 알고리즘으로 해결법을 찾아보고, 방법을 찾을 수 없으면 DP나 그래프 알고리즘 등으로 문제 해결 방법을 찾아본다.

 

 

실전문제 (1)
  • 큰 수의 법칙

 

  • 문제 요약
    • 다양한 수로 이루어진 배열이 주어질 때 수들을 M번 더하여 가장 큰 수를 만든다.
    • 특정한 인덱스가 연속 K번을 초과하면 안된다.
    • 2, 4, 5, 4, 6으로 이루어진 배열일 경우 M이 8이고, K가 3일 경우
    • 6 + 6 + 6 + (3연속X) 5 + 6 + 6 + 6 + (3연속X) + 5 = 46
    • 3, 4, 3, 4, 3으로 이루어질 경우 4 + 4 + 4 + 4 + 4 + 4 가능

 

  • 문제 해설
    • 입력 값 중에서 가장 큰 수와 두 번째로 큰 수만 저장한다.
    • 가장 큰 수를 K 번 더하고, 두 번째 큰 수를 한 번 더하는 연산 반복
    • M의 크기가 100억처럼 커질 경우, 시간 초과
    • 예시로 가장 큰 수 6, 두 번째로 큰 수 5, M이 8, K가 3이면 반복되는 수열이 존재한다 (6+6+6+5)*2
    • 이러한 문제에서 가장 먼저 반복되는 수열에 대해서 파악하는 것이 중요
    • 반복되는 수열의 길이 = K+1
    • M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수
    • 반복 횟수에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.
<가장 큰 수가 더해지는 횟수> int (M / (K+1)) * K + M & (K+1) 

 

 

실전 문제 (2)
  • 숫자 카드 게임

 

 

  • 문제 요약
    • 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장 뽑기
    • N X M 개의 카드
    • 먼저 뽑으려는 카드가 포함된 행 선택
    • 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드 뽑기
    • 행을 선택할 때, 가장 숫자가 낮은 카드를 뽑는 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있는 전략 세우기
    • 1, 2번째 행을 선택하는 경우 최종적으로 뽑는 카드 1
    • 3번째 행을 선택하는 경우 최종적으로 뽑는 카드 2
    • 따라서 세번째 행을 선택 후 숫자 2가 쓰인 카드를 뽑는 것이 정답

 

 

  • 문제 해설
    • 각 행마다 가장 작은 수를 찾은 뒤, 그 수 중에서 가장 큰 수를 찾는다.
Collections.max(list); // 리스트에서 최대 값을 출력
Collections.min(list); // 리스트에서 최소 값을 출력

 

 

실전 문제 (3)
  • 1이 될 때까지

 

  • 문제 요약
    • 어떤 수 N이 1이 될 때까지 아래의 과정 중 하나를 반복적으로 수행
    • 두 번째 연산은 N이 K으로 나누어 떨어질 때만 선택 가능
      1. N에서 1을 뺀다.
      2. N을 K로 나눈다.
    • N 17, K 4일 경우, 1번 과정 수행 시 N은 16 
    • 2번 과정을 두 번 수행 시 N은 1
    • 결과적으로 전체 과정 실행 횟수 3

 

  • 문제 해설
    • 주어진 N에 대하여 '최대한 큰 수로 나누기'를 수행
객체 지향 프로그래밍
  • 객체들을 먼저 만들고, 이것들을 하나씩 조립해서 완성된 프로그램을 만드는 기법
  • 객체(Object) : 물리적으로 존재하거나 추상적으로 생각할 수 있는 것 중에서 자신의 속성을 가지고 있고, 다른 것과 식별 가능한 것.
    • 속성 = 필드(field)
    • 동작 = 메소드(method) : 객체들 사이의 상호작용 수단은 메소드
  • 객체 모델링(Object Modeling) : 현실 세계의 객체를 소프트웨어 객체로 설계하는 것
  • 메소드 호출 : 객체가 다른 객체의 기능을 이용하는 것
  • 객체 간의 관계 : 집합 관계, 사용 관계, 상속 관계

[객체 간의 관계]

 

객체 지향 프로그래밍의 특징
  • 캡슐화(Encapsulation)
    • 객체의 필드, 메소드를 하나로 묶고, 실제 구현 내용을 감추는 것
    • 외부 객체는 객체의 내부 구조를 알 수 없다.
    • 자바 언어는 캡슐화된 멤버를 노출시킬 것인지, 숨길 것인지 접근 제한자(Access Modifier) 사용
  • 상속(Inheritance) 
    • 부모가 가지고 있는 재산을 자식에게 물려주는 것
    • 코드의 중복 최소화 가능
    • 유지 보수 시간 최소화
  • 다형성(Polymorphism) 
    • 같은 타입이지만 실행 결과가 다양한 객체를 이용할 수 있는 성질
    • 자바는 다형성을 위해 부모 클래스 또는 인터페이스의 타입 변환을 허용
    • 부모 타입에는 모든 자식 객체 대입 가능
    • 인터페이스 타입에는 모든 구현 객체가 대입 가능
    • 다형성으로 인해 객체는 부품화가 가능

 

객체와 클래스
  • 현실에서 객체는 설계도를 바탕으로 만들어진다.
  • 자바에서의 설계도는 클래스(class)이다.
  • 클래스(class) 
    • 객체를 생성하기 위한 필드와 메소드가 정의되어 있다.
    • 클래스로부터 만들어진 객체를 해당 클래스의 인스턴스(instance)라고 한다.
    • 인스턴스화 : 클래스로부터 객체를 만드는 과정
  • 객체지향 프로그래밍 개발 3단계
    1. 클래스 설계
    2. 설계된 클래스를 가지고 사용할 객체 생성
    3. 생성된 객체 사용

 

클래스 선언
  • 클래스 이름은 자바의 식별자 작성 규칙을 따른다.
  • 일반적으로 소스 파일당 동일한 이름의 하나의 클래스를 선언한다.
  • 두 개 이상도 가능하지만, 컴파일을 하면 바이트 코드 파일은 클래스를 선언한 개수만큼 생기기 때문에, 파일 이름과 일치하지 않는 클래스 선언에 public 접근 제한자를 붙이면 컴파일 에러가 발생한다.

[자바의 식별자 작성 규칙]

 

객체 생성과 클래스 변수
  • new 연산자 
    • 클래스로부터 객체를 생성하는 방법.
    • 연산자 뒤에 생성자가 온다.
    • new 연산자로 생성된 객체는 메모리 힙(heap) 영역에 생성된다.
    • 힙 영역에 객체를 생성시킨 후, 객체의 주소를 리턴한다.
클래스 변수 = new 클래스();

[new 연산자 사용 후 메모리 구조]

 

  • 클래스의 2가지 용도
    • 라이브러리(API)용 : 다른 클래스에서 이용할 목적으로 설계
    • 실행용 : main() 메소드를 제공하는 역할
  • 프로그램을 하나의 클래스로 구성할 수 있지만, 객체 지향 프로그램은 대부분 라이브러리와 실행 클래스가 분리되어 있다.
public class studnet {  // 라이브러리 클래스
}
public class StudentExample {   // 실행 클래스
    public static void main(String[] args){
        ...
    }
}

 

클래스의 구성 멤버
  • 필드(Field)
    • 객체의 데이터가 저장되는 곳
    • 변수와 비슷하지만. 변수는 생성자와 메소드 내에서만 사용되고 생성자는 메소드가 실행 종료되면 자동 소멸한다. 하지만 필드는 메소드 전체에서 사용되고, 객체가 소멸되지 않으면 객체와 함께 존재한다.
  • 생성자(Constructor)
    • 객체 생성 시 초기화 역할 담당
    • 생성자는 메소드와 비슷하지만, 클래스 이름으로 되어 있고, 리턴 타입이 없다.
    • 생성자가 성공적으로 실행되면 힙(heap) 영역에 객체가 생성되고 객체의 주소가 리턴된다.
    • 모든 클래스는 생성자가 반드시 존재한다. 
      • 기본 생성자 
        • 중괄호 블록 내용이 비어있는 기본 생성자. 클래스 내부에 생성자 선언을 생략하면 컴파일러가 자동으로 추가한다.
        • 클래스에 생성자를 선언하지 않아도 new 연산자 뒤에 기본 생성자를 호출해서 객체 생성이 가능하다.

[기본 생성자 자동 생성]
[기본 생성자로 객체 생성 가능]

  • 메소드(Method)
    • 객체의 동작에 해당하는 실행 블록
    • 객체 간의 데이터 전달 수단
public class ClassName{
    int fieldName; // 필드
    ClassName() {...} // 생성자
    void methodName() {...} // 메소드
}

외부 클래스에서 Car 필드 값 읽기와 변경
public class Car {
    // 필드
    String company = "현대자동차";
    String model = "그랜저";
    String color = "검정";
    int maxSpeed = 350;
    int speed;
}
public class CarExample {
    public static void main(String[] args){
        // 객체 생성
        // 다른 클래스의 필드 값을 사용하기 위해서는 다른 클래스의 객체를 생성해야한다.
        Car myCar = new Car();

        // 필드 값 읽기
        System.out.println("제작회사 " + myCar.company);
        System.out.println("모델명 " + myCar.model);
        System.out.println("색깔 " + myCar.color);
        System.out.println("최고속도 " + myCar.maxSpeed);
        System.out.println("현재속도 " + myCar.speed);

        // 필드 값 변경
        myCar.speed = 60;
        System.out.println("수정된 속도 " + myCar.speed);
    }
}

 

기본 생성자 대신 명시적 생성자 선언
  • 명시적 생성자의 매개 변수는 new 연산자로 생성자를 호출할 때 외부의 값을 생성자 블록 내부로 전달한다.
public class Car {
    // 생성자
    Car(String color, int cc) {
    }
}
public class CarExample {
    public static void main(String[] args){
        Car myCar = new Car("검정", 3000);
        // Car myCar  new Car();
        // 생성자가 명시적으로 선언되어 있을 경우 기본 생성자 호출이 불가능
    }
}

 

필드 초기화
  • 클래스로부터 객체가 생성될 때, 필드는 기본 초기 값으로 자동 설정
  • 다른 값으로 초기화하는 2가지 방법
    1. 필드를 선언할 때 초기값을 준다.
    2. 생성자에서 초기값을 준다. (객체 생성 시점에 외부에서 제공되는 다양한 값들로 초기화될 경우)
public class Korean {
    // 필드
    String nation = "대한민국"; // 필드에서 초기화
    String name;
    String ssn;


    // 생성자
    // 생성자에서 초기화
    public Korean(String n, String s) {
        name = n;
        ssn = s;
    }
}
  • 생성자의 매개 변수 이름은 필드와 동일한 이름을 갖는 매개 변수를 사용한다. 그렇게 되면 필드와 매개 변수 이름이 동일하기 때문에 생성자 내부에서 해당 필드에 접근이 불가능하다. (매개 변수가 사용 우선순위가 높기 때문)
  • 해결 방법 : 필드 앞에 this를 붙인다.
    public Korean(String name, String ssn) {
        this.name = name; // this.필드 = 매개변수
        this.ssn = ssn;
    }
}

 

생성자 오버로딩(Overloading)
  • 매개 변수를 달리하는 생성자를 여러 개 선언하는 것
  • 다양한 방법으로 객체를 생성할 수 있도록 사용한다.
  • 매개 변수의 타입, 개수, 순서를 다르게 선언한다.
public class Car {
    Car(){}
    Car(String model) {}
    Car(String model, String color) {}
}
  • 매개 변수의 이름만 바꾸는 것은 생성자 오버로딩이 아니다.
Car(String color, String model) {}
Car(String model, String color) {}
public class Car {
    // 필드
    String company = "현대자동차";
    String model;
    String color;
    int maxSpeed;

    // 생성자
    Car(){
    }
    Car(String model) {
        this(model, "은색", 250); // 맨 아래 생성자 호출
    }
    Car(String model, String color) {
        this(model, color, 250); // 맨 아래 생성자 호출
    }
    Car(String model, String color, int maxSpeed){
        this.model = model;
        this.color = color;
        this.maxSpeed = maxSpeed;
    }
}

 

메소드
  • 메소드 : 객체의 동작에 해당하는 중괄호 블록
  • 리턴타입, 메소드이름, 매개변수선언
  • 시그너처(signature) : 메소드 선언부
  • 메소드 이름은 자바 식별자 규칙에 맞게 사용한다.
    • 소문자로 작성, 단어의 첫머리는 대문자
public class Caculator {
    // 메소드
    void powerOn(){
        System.out.println("전원을 켭니다.");
    }
    int plus(int x, int y){
        int result = x + y;
        return result;
    }
}

public class CaculratorExample {
    public static void main(String[] args){
        Caculator myCalc = new Caculator();
        myCalc.powerOn(); // 메소드 호출
        
        int result1 = myCalc.plus(5, 6);
        System.out.println(result1);
    }
}
  • 매개 변수의 수를 모를 경우 : 매개 변수를 배열 타입으로 선언한다.
public class Computer {
    // 첫번째 방법 생성자
    int sum1(int[] values){
        int sum = 0;
        for(int i=0; i<values.length; i++){
            sum += values[i];
        }
        return sum;
    }
    
    // 두번째 방법 생성자
    int sum2(int ... values) {
        int sum = 0;
        for (int i = 0; i < values.length; i++) {
            sum += values[i];
        }
        return sum;
    }
}

public class ComputerExample {
    public static void main(String[] args){
        Computer myCom = new Computer(); // 객체 생성
        
        int[] values1 = {1, 2, 3};
        int result1 = myCom.sum1(values1);
        System.out.println(result1);
        
        int result2 = myCom.sum1(new int[] {1,2,3,4,5});
        System.out.println(result2);
        
        int result3 = myCom.sum2(1, 2, 3);
        System.out.println(result3);
    }
}

 

메소드 오버로딩(overloading)
  • 클래스 내부에 같은 이름의 메소드를 여러 개 선언하는 것
  • 매개 값을 다양하게 받아 처리할 수 있도록 사용한다.
  • 매개 변수의 타입, 개수, 순서 중 하나가 달라야 한다.

 

인스턴스 멤버와 this
  • 인스턴스 멤버
    • 객체(인스턴스)를 생성한 후 사용할 수 있는 필드와 메소드
    • 객체 없이는 사용 불가능
    • 인스턴스 필드, 인스턴스 메소드
  • this 
    • 객체 내부에서도 인스턴스 멤버에 접근하기 위해 this를 사용한다.
Car(String model) {
    this(model, "은색", 250); 
}
void setModel(String model){
    this.model = model;
}

 

정적 멤버와 static
  • 정적 멤버(클래스 멤버)
    • 클래스에 고정된 멤버
    • 객체를 생성하지 않고 사용할 수 있는 필드와 메소드
    • 정적 필드, 정적 메소드
  • 클래스 로더가 클래스(바이트 코드)를 로딩해서 메소드 메모리 영역에 적재할 때 클래스별로 관리된다.
  • 클래스 이름으로 접근할 수 있다. 객체 참조 변수로도 가능하지만, 사용 시 경고 표시가 나타난다.
  • 정적 필드는 필드 선언과 동시에 초기 값을 주는 것이 보통이지만, 계산이 필요한 경우 정적 블록을 사용한다.
public class Television {
    static String company = "Samsung"; // 보통 필드에서 초기값 결정 
    static String model = "LCD";
    static String info;
    
    static { // 정적 블록 사용
        info = company + "_" + model;
    }
}
  • 정적 블록과 메소드에서 인스턴스 필드와 메소드를 사용할 수 없다.
  • 해결 방법은 객체를 먼저 생성(new 연산자 사용)하고 참조 변수로 접근해야 한다.
public class ClassName {
    // 인스턴스 필드와 메소드
    int field1;
    void method1() {}
    
    // 정적 필드와 메소드
    static int field2;
    static void method2() {}
    
    // 정적 블록
    static {
        field1 = 10; // 컴파일 에러
        method1();  // 컴파일 에러
        field2 = 10;
        method2();
    }
    
    // 정적 메소드
    static void Method3 {
        this.field1 = 10; // 컴파일 에러
        this.method1();  // 컴파일 에러
        field2 = 10;
        method2();
    }
}

 

싱글톤(Singleton)
  • 단 하나의 객체만 만드는 객체를 싱글톤이라고 한다.
  • 클래스 외부에서 new 연산자로 생성자를 호출할 수 없도록 해야 한다.
  • 호출할 수 없도록 생성자 앞에 private 접근 제한자를 붙여준다.
  • 클래스 내부에서 new 연산자로 생성자 호출이 가능하기 때문에, 정적 필드도 private 접근 제한자를 붙인다. 
  • 외부에서 호출할 수 있도록, 정적 메소드인 getInstance()를 선언하고, 정적 필드에서 참조하고 있는 자신의 객체를 리턴해준다.
public class Singleton {
    // private + 정적 필드
    private static Singleton singleton = new Singleton();
    
    // private + 생성자
    private Singleton(){}
    
    // private + 정적 메소드
    static Singleton getInstance(){
        return singleton;
    }
}

// 외부에서 객체를 얻는 유일한 방법
public class SingleExample(){
    public static void main(String[] args){
        Singleton obj = Singleton.getInstance();
    }
}

 

final 필드와 상수
  • final 필드
    • 초기 값이 저장되면 이것이 최종적인 값이 되어서 프로그램 실행 도중에 수정할 수 없다.
  • final 필드 초기값 주는 2가지 방법
    1. 필드 선언 시에 준다.
    2. 생성자에서 준다.
public class Person {
    final String nation = "Korea"; // 수정 불가
    final String ssn;
    String name;
    
    public Person(String ssn, String name){
        this.ssn = ssn;
        this.name = name;
    }
}
  • 상수(static final)
    • 변하지 않는 값
    • final 필드는 객체마다 저장되고, 생성자의 매개값을 통해서 여러 가지 값을 가질 수 있기 때문에 상수가 될 수 없다.
    • 상수는 static + final 
    • 상수 이름은 모두 대문자
public class Earth {
    static final double EARTH_RADIUS = 6400;
    static final double EARTH_SURFACE_AREA;
    
    static {
        EARTH_SURFACE_AREA = 4 * Math.PI * EARTH_RADIUS * EARTH_RADIUS;
    }
}

 

패키지(Package)
  • 클래스를 체계적으로 관리하기 위해서 사용
  • 패키지의 물리적 형태는 파일 시스템의 폴더
  • 클래스를 식별해준다.
  • 상위패키지.하위패키지.클래스
  • package 상위패키지.하위패키지;
  • 모두 소문자로 작성
  • 중복되지 않도록 보통 회사의 도메인 이름으로 패키지 작성 
  • 패키지 폴더를 자동으로 생성하려면 javac 명령어 다음 -d 옵션을 추가해 패키지가 생성될 경로를 지정해줘야한다.
    • javac -d 경로

 

import문
  • 다른 패키지에 속하는 클래스를 사용할 수 있는 방법
  • * 은 패키지에 속하는 모든 클래스 
  • import 문으로 지정된 패키지의 하위 패키지는 import 대상이 아니다.

 

접근 제한자(Access Modifier)
  • 객체 생성을 막기 위해 생성자를 호출하지 못하게 하거나 객체의 특정 데이터를 보호하기 위해서 해당 필드에 접근하지 못하도록 막아준다.
  • public, protected, default, private
  • 클래스에 적용할 수 있는 접근 제한 : public, default

[접근 제한자 종류]

 

Getter와 Setter 메소드
  • 객체 지향 프로그래밍에서는 객체의 무결성을 유지하기 위해, 외부의 직접적 접근을 막는다.
  • 메소드를 통해 데이터를 변경하는 방법을 선호한다.
  • Setter : 검증을 통해 유효한 값만 데이터로 저장 가능 (ex. 음수 검증)
  • Getter : 객체 외부에서 객체 필드값을 사용하기 부적절한 경우, 메소드에서 필드 값 가공 후 외부로 전달
private 타입 fieldName;

// Getter
public 리턴타입 getFieldName(){
    return fieldName;
}

// Setter
public void setFieldName(타입 fieldName){
    this.fieldName = fieldName;
}

 

어노테이션(Annotation)
  • 메타데이터(metadata)라고 볼 수 있다.
    • 애플리케이션에서 처리해야 하는 데이터가 아니라, 컴파일 과정과 실행 과정에서 코드를 어떻게 컴파일하고 처리할 것인지 알려주는 정보
  • 어노테이션의 3가지 용도
    • 컴파일러에게 코드 문법 에러를 체크하도록 정보 제공
      • 대표적인 예시 : @Override (메소드가 오버라이드된 것인지 컴파일러에게 알려주고, 제대로 되지 않았으면 에러 발생)
    • 소프트웨어 개발 툴이 빌드나 배치 시 코드를 자동으로 생성할 수 있도록 정보 제공
    • 실행 시 특정 기능을 실행하도록 정보 제공
  • 어노테이션 타입 정의 방법
    • public @interface AnnotationName {}
    • 엘리먼트(element)를 멤버로 가질 수 있다.
      • 타입 element() [default 값];
      • 엘리먼트 타입 : int, double, String, 열거, Class 타입 등등
  • 어노테이션 타입 적용 방법
    • @AnnotationName
  • 어노테이션 적용 대상 : java.lang.annotation.ElementType 열거 상수로 정의
    • TYPE, ANNOTATION_TYPE, FIELD, CONSTRUCTOR, METHOD, LOCAL_VARIABLE, PACKAGE
    • @Target 사용
  • 어노테이션 유지 정책 : java.lang.annotation.RetentionPolicy 열거 상수로 정의
    • SOURCE, CLASS, RUNTIME
    • @Retention 사용
  • 리플렉션(Reflection) : 런타임 시에 클래스의 메타 정보를 얻는 기능
    • java.lang.refelct

'프로그래밍 > JAVA' 카테고리의 다른 글

[자바의 정석] 연습문제 1.변수와 타입  (0) 2022.06.23
[JAVA] 자바 메모리 구조 - Heap, Stack, JVM, GC  (0) 2022.06.23
Ch05. 참조 타입  (0) 2022.01.01
Ch04. 조건문과 반복문  (0) 2022.01.01
Ch03. 연산자  (0) 2022.01.01
데이터 타입 분류
  • 자바의 데이터 타입
    • 기본 타입(primitive type) : 정수, 실수, 문자, 논리 리터럴을 저장하는 타입. 
    • 참조 타입(reference type) : 객체(object)의 번지를 참조하는 타입. 
      • 배열, 열거, 클래스, 인터페이스 타입

[데이터 타입의 종류]
[기본 타입과 참조 타입 변수]

// 기본 타입 변수
int age = 25;
double price = 100.5;

// 참조 타입 변수
String name = "신용권";
String hobby = "독서";
  • 변수는 스택 영역에 생성되고 객체는 힙 영역에 생성된다.
  • String 클래스 변수는 name과 hobby에 대한 힙 영역 주소 값(100, 200)을 가지고 있다. 

[변수의 스택 영역과 객체의 힙 영역]

 

메모리 사용 영역

[메모리 사용 세부 영역]

  • 메소드(Method) 영역
    • 코드에서 사용되는 클래스들을 클래스 로더로 런타임 상수풀, 필드 데이터, 메소드 데이터, 메소드 코드, 생성자 코드 등을 분류해서 저장한다. 
    • JVM이 시작할 때 생성되고 모든 스레드가 공유하는 영역
  • 힙 영역(Heap) 영역
    • 객체와 배열이 생성되는 영역
    • JVM 스택 영역의 변수나 다른 객체의 필드에서 참조한다.
    • 참조하는 변수나 필드가 없으면 JVM은 Garbage Collector를 실행시켜 쓰레기 객체를 힙 영역에서 자동으로 제거한다.
  • JVM 스택(stack) 영역
    • 각 스레드마다 하나씩 존재하고, 스레드가 시작될 때 할당된다.
    • JVM 스택은 메소드를 호출할 때마다 프레임(Frame) 추가(push)하고, 메소드가 종료되면 해당 프레임 제거(pop)
    • 프레임 내부의 로컬 변수 스택은 기본 타입 변수와 참조 타입 변수가 추가(push) 되거나 제거(pop)된다. 변수가 생성되는 시점은 초기화가 될 때, 제거되는 시점은 블록을 벗어나는 경우이다. 

 

 참조 변수의 연산
  • 기본 타입 변수의 ==, != 연산은 변수의 값이 같은지 확인
  • 참조 타입 변수의 ==, != 연산은 동일한 객체를 참조하는지 확인

 

null 과 NullPointerException
  • 참조 타입 변수는 힙 영역의 객체를 참조하지 않는다는 뜻으로 null 값을 가질 수 있다.
  • NullPointerException : 참조 타입 변수를 잘못 사용할 경우. null 을 가지고 있는 참조 타입 변수를 사용할 경우 발생.

 

배열 타입
  • 같은 타입의 데이터를 연속된 공간에 나열시키고, 각 데이터에 인덱스(index)를 부여해 놓은 자료구조
  • 인덱스는 0부터 시작
String[] names = {'a', 'b', 'c'};

names[0] -> a
names[1] -> b
names[2] -> c
  • new 연산자로 배열 생성
int[] intArray = new int[5];
  • 타입별 배열의 초기값

[타입별 배열의 초기값]

  • 배열의 길이 
int[] intArray = {10,20,30};
int num = intArray.length; //  배열의 길이

 

커맨드 라인 입력
  • "java 클래스"로 프로그램을 실행하면
  • JVM은 길이가 0인 String 배열을 먼저 생성하고 main() 메소드를 호출할 때 매개 값으로 전달한다.

[길이가 0인 String 배열]

  • "java 클래스 문자열0 문자열1 문자열2"으로 프로그램을 실행하면
  • 문자열 목록으로 구성된 String[] 배열이 생성되고 main() 메소드를 호출할 때 매개 값으로 전달된다.

[문자열 목록으로 구성된 String 배열]

  • Integer.parseInt() : 문자열은 산술 연산이 불가능 하기 때문에 메소드를 사용해서 정수로 변환시킨다.

 

다차원 배열
  • 1차원 배열과는 달리 행과 열로 구성된 배열을 2차원 배열이라고 한다.
int[][] scores = new int[2][3];

[2차원 배열의 메모리 구조]

배열 복사
  • System.arraycopy() 메소드 사용

 

열거 타입
  • 한정된 값만 갖는 데이터 타입
  • 몇 개의 열거 상수 중에서 하나의 상수를 저장하는 데이터 타입
  • 열거 타입 선언 
    • 열거 타입 이름을 정하고, 소스 파일(.java) 생성
    • 이름은 첫 문자를 대문자로 하고, 나머지를 소문자로 구성. 여러 단어로 구성된 경우 단어 첫 문자는 대문자로 구성.
    • public enum 열거타입이름 {...}
public enum Week {MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, ...}
public enum LoginResult {LOGIN_SUCCESS, LOGIN_FAILED}

 

  • 열거 타입 변수
    • 열거타입 변수 = 열거타입.열거상수;
Week today = Week.SUNDAY;
Week birthday = null;

열거 객체의 메소드
  • name() : 열거 객체가 가지고 있는 문자열 리턴
  • ordinal() : 전체 열거 객체 중 몇 번째 열거 객체인지 알려준다.
  • compareTo() : 매개값으로 주어진 열거 객체를 기준으로 전후로 몇 번째 위치하는지 비교
  • valueOf() : 매개값으로 주어지는 문자열과 동일한 문자열을 가지는 열거 객체를 리턴
  • values() : 열거 타입의 모든 열거 객체들을 배열로 만들어 리턴

'프로그래밍 > JAVA' 카테고리의 다른 글

[JAVA] 자바 메모리 구조 - Heap, Stack, JVM, GC  (0) 2022.06.23
Ch06. 클래스  (0) 2022.01.02
Ch04. 조건문과 반복문  (0) 2022.01.01
Ch03. 연산자  (0) 2022.01.01
Ch02. 변수와 타입  (0) 2022.01.01
제어문
  • 실행 흐름을 개발자가 원하는 방향으로 바꿀 수 있도록 해주는 것
  • 조건문 : if문, switch문
  • 반복문 : for문, while문, do-while문
    • 루핑(looping) : 반복문에서 제어문 처음으로 다시 되돌어가 반복 실행하는 것

 

조건문(if문, switch문)
  • if문, if-else문, if-else if-else문, 중첩 if문
  • switch문
    • if문처럼 조건식이 true인 경우 실행하는 것이 아닌, 변수의 값에 따라 실행문이 선택된다.
    • break가 없으면 값과는 상관없이 다음 case가 연달아 실행된다.

 

반복문(for문, while문, do-while문)
  • for문 : 반복 횟수를 알고 있을 경우
    • for(초기화식, 조건식, 증감식)
for(int i=1; i<=10; i++){
    System.out.println(i);
}
  • while문 : 조건에 따라 반복할 때 주로 사용
  • do-while문  
    • System.in.read() : 키보드의 키 코드를 읽는다.
int i = 1;
while (i<=10){
    System.out.println(i);
    i++;
}
  • continue문, break문 사용

'프로그래밍 > JAVA' 카테고리의 다른 글

Ch06. 클래스  (0) 2022.01.02
Ch05. 참조 타입  (0) 2022.01.01
Ch03. 연산자  (0) 2022.01.01
Ch02. 변수와 타입  (0) 2022.01.01
Ch01. 자바 시작하기  (0) 2022.01.01

+ Recent posts