Prologue
- Java로 알고리즘/코딩테스트에서 자주 쓰이는 문법들을 정리하기 위한 포스팅이다.
구현
-
구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
-
Problem -> Thinking -> Solution
-
구현 유형의 예시는 다음과 같다.
-
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
-
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
-
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
-
적절한 라이브러리를 찾아서 사용해야 하는 문제
-
-
-
구현 유형은
완전 탐색,시뮬레이션을 포함한다.완전 탐색(Brute Forcing) : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
관련 문제
DFS/BFS
- 깊이 우선 탐색과 너비 우선 탐색은 기본적인 그래프 기법 : DFS, BFS에 정리했으니, 해당 글을 참고하자.
유형1. 연결된 요소 찾기
-
연결된 노드의 개수는 몇 개인가요?
-
연결된 묶음/덩어리의 개수는 몇 개인가요?
-
1번과 연결된 노드의 번호를 오름차순으로 출력하세요
-
1번과 3번의 거리는 얼마인가요?
이 유형을 잘 풀기 위해 고민할 것들
-
주요 키워드: 정점(node), 간선(edge), 연결, 네트워크, 그래프
-
주어진 정보를 어떻게 변환할지 -> 2차원 배열(1,000이하) / ArrayList(1,000 초과)
-
재방문을 방지하는 방법
관련 문제
유형2. 같은 부류 찾기
-
연결된 묶음/덩어리의 개수는 몇 개인가요?
-
가장 큰 덩어리의 크기는 얼마인가요?
이 유형을 잘 풀기 위해 고민할 것들
-
주요 키워드: 인접한 위치로 이동, 상하좌우, 가로/세로, 대각선으로 이동
-
주어진 정보를 어떻게 변환할지
-
재방문을 방지하는 방법
-
어느 지점에서 DFS를 시작할지
-
어느 방향으로 DFS를 진행할지
그외
Stack
-
스택은
LIFO(List In First Out, 후입선출) 구조로 데이터를 쌓아올린 형태의 자료구조를 뜻한다. ex) 쓰레기통, 마트용 음료수 진열대, 프링X스(과자) -
즉 한쪽 끝에서만 자료(데이터)를 넣고 뺄 수 있는 형식의 자료 구조이다.
-
스택은 데이터를 쌓는 형식으로 저장하는데 따라서 조회, 추가, 삭제 모두 가장 위에 있는, 가장 최근의 값에서 이루어진다.
-
스택 구조에서 가장 상단에 있는 데이터를
Top라 부른다.
관련 문제
Stack 선언
Stack<Element> stack = new Stack<>();
Stack 주요 클래스
public Element push(Element item); // 데이터 추가
public Element pop(); // 최근에 추가된(Top) 데이터 삭제
public Element peek(); // 최근에 추가된(Top) 데이터 조회
public boolean empty(); // stack의 값이 비었는지 확인, 비었으면 true, 아니면 false
public int seach(Object o); // 인자값으로 받은 데이터의 위치 반환, 그림으로 설명하겠음
Stack 예제
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < 5; i++) {
stack.push(i + 1);
System.out.println(stack.peek());
} // 1, 2, 3, 4, 5 가 현재 들어가 있음
stack.pop(); // 1, 2, 3, 4
System.out.println(stack.peek()); // 4
System.out.println(stack.search(1)); // 4
System.out.println(stack.empty()); // false
Queue
-
큐는
FIFO(First In First Out, 선입선출) 데이터를 순서대로 줄을 세운 형태의 자료구조를 뜻한다. ex) 놀이공원 이나 매표소 등 줄을 서서 차례로 업무를 처리하는 경우 -
주로
앞(frotn)에서는조회/삭제연산을 수행하고,뒤(Rear)에서는삽입연산을 수행한다. -
그래프의 넓이 우선 탐색(BFS)에서도 사용된다.
-
용어 정리
-
Enqueue: 큐 맨 뒤에 데이터 추가 -
Dequeue: 큐 맨 앞쪽의 데이터 삭제
-
관련 문제
Queue 선언
import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용
-
자바에서 큐는
LinkedList를 활용하여 생성해야 한다. 그렇기에 그렇기에Queue와LinkedList가 다 import되어 있어야 사용이 가능하다. -
Queue<Element> queue = new LinkedList<>()와 같이 선언해주면 된다.
Queue 값 추가
Queue<Integer> q = new LinkedList<>(); // int형 queue 선언
q.offer(3);
q.offer(5);
q.offer(1);
q.offer(4);
System.out.println(q); // 출력 결과 : [3, 5, 1, 4]
-
Queue에 값을 추가하려면
offer(value)메서드를 사용한다. -
이때, add(value) 메서드를 사용해서도 값을 추가할 수 있다.
-
큐 용량 초과 등의 이유로 값 추가에 실패했을 때, add() 메서드는 예외를 발생시키고 offer() 메서드는 false를 리턴한다는 차이가 있다.
Queue 값 삭제
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1); // queue에 값 1 추가
queue.offer(2); // queue에 값 2 추가
queue.offer(3); // queue에 값 3 추가
queue.poll(); // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove(); // queue에 첫번째 값 제거
queue.clear(); // queue 초기화
-
Queue에서 값을 삭제하려면
poll()메서드를 사용한다. 물론remove를 사용해도 된다. -
Queue의 모든 데이터를 삭제하려면
clear()메서드를 사용한다.
Queue에서 가장 먼저 들어간 값 출력
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1); // queue에 값 1 추가
queue.offer(2); // queue에 값 2 추가
queue.offer(3); // queue에 값 3 추가
queue.peek(); // queue의 첫번째 값 참조
- Queue에서 첫번째로 저장된 값을 참조하고 싶다면
peek()라는 메서드를 사용한다.
그 외 Queue 주요 메서드
-
isEmpty(), isFull(): 각각 큐가 비었는지, 가득 찼는지를 boolean 형태로 반환한다. -
enqueue(): 큐에 새로운 원소를 삽입한다. 만약 가득 차 있다면 예외를 던진다. -
peek(): 맨 앞에 위치한 데이터를 읽어온다. -
dequeue(): 맨 앞에 위치한 데이터를 읽어오고, 해당 데이터를 큐(queue)에서 제거한다.
Map
-
맵(Map)은 key와 value로 이루어져 있고, 두개의 값이 한 쌍을 이루어 데이터를 저장하는 자료구조이다.
-
순서가 없으며, 중복을 허용하지 않는 특징이 있다.
관련 문제
HashMap 선언
//map 선언
Map<String, String> map = new HashMap<String, String>();
//map에 값 저장
map.put("이름", "팬시");
map.put("취미", "운동");
//map의 크기 출력
System.out.println(map.size());
//map의 모든 값 출력
System.out.println(map.toString());
//map의 key가 이름인 값 출력
System.out.println(map.get("이름"));
HashMap 메서드
-
데이터 추가
V put(K key, V value): key와 value를 저장한다.
-
데이터 삭제
-
void clear(): 모든 데이터를 삭제한다. -
V remove(Object key): key와 일치하는 기존 데이터(key와 value)를 삭제한다. -
boolean remove(Object key, Object value): key와 value가 동시에 일치하는 데이터를 삭제한다.
-
-
데이터 수정
-
V replace(K key, V value): key와 일치하는 기존 데이터의 value를 변경한다. -
V replace(K key, V oldValue, V newValue): key와 oldValue가 동시에 일치하는 데이터의 value를 newValue로 변경한다.
-
-
데이터 확인
-
boolean containsKey(Object key): key와 일치하는 데이터가 있는지 여부를 반환한다. (있으면 true) -
boolean containsValue(Object value): value가 일치하는 데이터가 있는지 여부를 반환한다. (있으면 true) -
boolean isEmpty( ): 데이터가 빈 상태인지 여부를 반환한다. (빈 상태면 true) -
int size( ): key-value 맵핑 데이터의 개수를 반환한다.
-
-
데이터 반환
-
V get(Object key): key와 맵핑된 value값을 반환한다. -
V getOrDefault(Object key, V defaultValue): key와 맵핑된 value값을 반환하고 없으면 defaultValue값을 반환한다. -
Set<Map.Entry<K, V>> entrySet( ): 모든 key-value 맵핑 데이터를 가진 Set 데이터를 반환한다. -
Set<K> keySet(): 모든 key 값을 가진 Set 데이터를 반환한다. -
Collection<V> values(): 모든 value 값을 가진 Collection 데이터를 반환한다.
-
문자열
String.toCharArray()
-
String.toCharArray()은 문자열을 한 글자씩 쪼개서 이를 char타입의 배열에 집어넣어주는 메소드이다. -
String(문자열)을 char형 배열로 바꾼다.
class Solution {
static boolean v[][]; // 체크 배열
public int solution(int m, int n, String[] board) {
int answer = 0;
char copy [][] = new char[m][n];
// 보드를 2차원 문자 배열로 복사합니다.
for(int i = 0; i < m; i++) {
copy[i] = board[i].toCharArray();
}
}
}
- 예를 들어, 입력으로 주어진 board 배열이 다음과 같다고 가정하면,
String[] board = ["CCBDE", "AAADE", "AAABF", "CCBBF"]
- 이때, 위에서 제시한 코드를 통해 copy 배열에는 아래와 같이 데이터가 저장된다.
char[][] copy = {
{'C', 'C', 'B', 'D', 'E'},
{'A', 'A', 'A', 'D', 'E'},
{'A', 'A', 'A', 'B', 'F'},
{'C', 'C', 'B', 'B', 'F'}
};
- 결과적으로 copy 배열은 board 배열의 복사본으로, copy 배열을 변경하여 작업하면 원본 board 배열에는 영향을 미치지 않는다.
관련 문제
String.contains
-
contains() 함수는 대상 문자열에 특정 문자열이 포함되어 있는지 확인하는 함수이다.
-
대/소문자를 구분한다.
-
공백을 확인한다.
-
public class ContainsTest{
public static void main(String[] args){
String str = "my java test";
System.out.println( str.contains("java") ); // true
System.out.println( str.contains(" my") ); // false -> 공백이 있기 때문
System.out.println( str.contains("JAVA") ); // false
System.out.println( str.contains("java test") ); // true
}
}