기타
[코테 대비] Java로 코딩테스트 준비하기 - 심화
일 월
2025. 3. 17. 15:49
기본 문법에 관련된 글은 아래 링크에!
[코테 대비] Java로 코딩 테스트 준비하기 - 기본
보통 Python으로 알고리즘을 준비하는데, 사용 가능 언어에 Python이 없는 코테가 있다. Java로 코딩 테스트를 보려고 할 때, 참고하면 좋을 내용을 적어보려고 한다.빠르게 익히는 것을 목표로 하고
ilwol-developer.tistory.com
5. 주요 알고리즘
5-1. 정렬
// 배열 정렬
import java.util.Arrays;
int[] intArr = {8,7,6,5,4};
String[] strArr = {"d", "c", "b", "a"};
Arrays.sort(intArr); // 숫자 오름차순
Arrays.sort(intArr,2,5); // 2~4번 인덱스 까지만 정렬
// primitive 타입이 아닌 Wrapper 클래스 일 경우 arr 뒤에 추가로 Comparator를 인자로 전달하여 정렬 가능
Arrays.sort(strArr, Collections.reverseOrder()); // 문자 내림차순
// Comparator를 활용하여 사용자가 직접 정렬 기준을 정의할 수도 있음
Integer[] intArr = new Integer[] {1,3,2,5,4};
Arrays.sort(intArr,new Comparator() {
@Override
public int compare(Integer a, Integer b) {
return a.compareTo(b); // 오름차순 (a가 b보다 작다면 양수를 반환하고, a와 b가 같다면 0을 반환, a가 b보다 크다면 음수를 반환)
//return b.compareTo(a); // 내림차순
}
});
// 람다식을 사용한 정렬
Integer[] intArr = new Integer[] {1,3,2,5,4};
Arrays.sort(intArr, (a, b) -> a - b); // 오름차순 정렬
// List 정렬
List numbers = new ArrayList<>();
numbers.add(3);
numbers.add(5);
numbers.add(1);
Collections.sort(numbers); // 오름차순 정렬
ArrayList list = new ArrayList<>();
list.add("d");
list.add("e");
list.add("a");
list.sort(Comparator.naturalOrder());
// 객체 특정 속성으로 정렬
List people = new ArrayList<>();
people.add(new Person("John", 25));
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 20));
people.sort((o1, o2) -> o2.getName().compareTo(o1.getName())); // name 속성으로 내림차순 정렬5-2. 스택
// Stack 클래스
// LinkedList로 되어 있어 크기 지정하지 않아도 됨
// push(), pop(), peek(), empty(), search() 기능을 지원
import java.util.Stack;
import javax.lang.model.element.Element;
public class Main {
public static void main(String\[\] args) {
Stack stack = new Stack<>();
for(int i=1; i<=5 ; i++) {
stack.push(i);
System.out.println(stack.peek());
}
stack.pop();
System.out.println("Pop()");
System.out.println(stack.peek()); //4
System.out.println(stack.search(3)); //2
System.out.println(stack.empty()); //false
}
}5-3. 큐
// Queue 인터페이스를 이용한 구현
// add/offer, remove/poll, element/peek, clear, size, contains, isEmpty
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue queue = new LinkedList();
queue.offer(1); // 해당 큐 맨 뒤에 값 삽입, 값 추가 성공 시 true 반환, 값 추가 실패 시 false 반환
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
while(!queue.isEmpty()) {
System.out.println(queue.poll()); // 큐 맨 앞에 있는 값 반환 후 삭제, 큐가 비어있을 경우 null 반환
}
}
}5-4. 우선순위 큐, 힙
// PriorityQueue 이용
// add/offer, remove/poll, element/peek, clear, size, isEmpty
import java.util.PriorityQueue;
public class Example {
public static void main(String[] args) {
PriorityQueue<Integer> pQ = new PriorityQueue<>();
pQ.offer(1); // pQ에 원소 1 추가
pQ.offer(6); // pQ에 원소 6 추가
pQ.offer(2); // pQ에 원소 2 추가
// pQ가 비어있면: true, 그렇지 않으면 : false
while(!pQ.isEmpty()) {
// pQ에 첫 번째 값을 반환하고 제거, 비어있다면 null 반환
System.out.println("pQ.poll() = " + pQ.poll());
}
}
}
// 우선순위 큐
// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자) - 최소 힙
PriorityQueue pQ = new PriorityQueue<>();
// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자) - 최대 힙
PriorityQueue pQ = new PriorityQueue<>(Collections.reverseOrder());
// Comparator로 우선순위 결정
import java.util.Comparator;
import java.util.PriorityQueue;
class Student {
int mathScore;
int engScore;
public Student(int mathScore, int engScore){
this.mathScore = mathScore;
this.engScore = engScore;
}
}
// 클래스 객체의 우선순위를 위한 클래스
class StudentComparator implements Comparator {
@Override
public int compare(Student o1, Student o2) {
if (o1.mathScore == o2.mathScore) {
return o2.engScore - o1.engScore;
} else {
return o1.mathScore - o2.mathScore;
}
}
}
public class Example {
public static void main(String[] args) {
// 클래스 객체에 대한 우선순위 기준 제공
PriorityQueue<Student> pQ = new PriorityQueue<>(1, new StudentComparator());
pQ.offer(new Student(70, 50));
pQ.offer(new Student(60, 50));
pQ.offer(new Student(70, 40));
while (!pQ.isEmpty()) {
Student s = pQ.poll();
System.out.printf("Student\'s MathScore and engScore: %d, %d \n", s.mathScore, s.engScore);
}
}
}
// 람다식으로 우선순위 결정
PriorityQueue memberQueue = new PriorityQueue<>((m1,m2)->m1.age-m2.age);
// Comparable 구현
class MyMember implements Comparable{
String name;
int age;
public MyMember(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(MyMember o) {
return this.age-o.age;
}
}5-5. 트리
package Tree;
public class Tree {
int count;
public Tree() {
count = 0;
}
public class Node {
Object data;
Node left;
Node right;
// 생성 시 매개변수를 받아 초기화하는 방법으로만 선언 가능
public Node(Object data) {
this.data = data; // 저장할 값
left = null; // 왼쪽 연결 노드
right = null; // 오른쪽 연결 노드
}
// 현재 노드의 좌측에 노드 연결 정보를 추가
public void addLeft(Node node) {
left = node;
count++;
}
// 현재 노드의 우측에 노드 연결 정보를 추가
public void addRight(Node node) {
right = node;
count++;
}
// 현재 노드의 좌측 노드 연결 정보를 삭제
public void deleteLeft() {
left = null;
count--;
}
// 현재 노드의 좌측 노드 연결 정보를 삭제
public void deleteRight() {
right = null;
count--;
}
}
// 노드 생성
public Node addNode(Object data) {
Node n = new Node(data);
return n;
}
// 전위 순회
public void preOrder(Node node) {
if(node == null) {
return;
}
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// 중위 순회
public void inOrder(Node node) {
if(node == null) {
return;
}
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
// 후위 순회
public void postOrder(Node node) {
if(node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
}
// 코드 실행
import Tree.*;
import Tree.Tree.Node;
public class Run {
public static void main(String[] args) {
// 트리 생성
Tree tree = new Tree();
// 노드 생성
Node node1 = tree.addNode(1);
Node node2 = tree.addNode(2);
Node node3 = tree.addNode(3);
Node node4 = tree.addNode(4);
Node node5 = tree.addNode(5);
Node node6 = tree.addNode(6);
Node node7 = tree.addNode(7);
// 트리 연결관계 생성
/* 트리 모양
* 1
* 2 3
* 4 5 6 7
*/
node1.addLeft(node2);
node1.addRight(node3);
node2.addLeft(node4);
node2.addRight(node5);
node3.addLeft(node6);
node3.addRight(node7);
// 순회
tree.preOrder(node1);
System.out.println();
tree.inOrder(node1);
System.out.println();
tree.postOrder(node1);
System.out.println();
// 삭제
node2.deleteLeft();
node3.deleteRight();
/* 삭제 이후 트리 모양
* 1
* 2 3
* 5 6
*/
// 순회
System.out.println();
tree.preOrder(node1);
System.out.println();
tree.inOrder(node1);
System.out.println();
tree.postOrder(node1);
System.out.println();
}
}5-6. dfs
import java.util.*;
public class Main {
public final static int GRAPH_LIST_SIZE = 9;
public static boolean[] visitedFlag = new boolean[GRAPH_LIST_SIZE];
public static ArrayList<ArrayList> graph = new ArrayList<ArrayList>();
public static void main(String[] args) {
// 리스트 초기화
for (int i = 0; i < GRAPH_LIST_SIZE; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
// DFS 탐색을 위한 재귀함수
public static void dfs(int point){
// 현재 노드 방문 처리
visitedFlag[point] = true;
System.out.print(point + " ");
// 인접 노드 방문
for(int node : graph.get(point)){
if(!visitedFlag[node]){
dfs(node);
}
}
}
}5-7. bfs
import java.util.*;
public class Main
{
public final static int GRAPH_LIST_SIZE = 9;
public static boolean[] visitedFlag = new boolean\[GRAPH_LIST_SIZE];
public static ArrayList<ArrayList> graph = new ArrayList<ArrayList>();
public static void main(String[] args) {
// 리스트 초기화
for (int i = 0; i < GRAPH_LIST_SIZE; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
bfs(1);
}
// BFS 탐색을 위한 재귀함수
public static void bfs(int point){
Queue<Integer> queue = new LinkedList<Integer>();
// 현재 노드 방문 처리
queue.offer(point);
visitedFlag[point] = true;
while(!queue.isEmpty()){
int target = queue.poll();
System.out.print(target + " ");
// 인접 노드 방문
for(int node : graph.get(target)){
if(!visitedFlag[node]){
queue.offer(node);
visitedFlag[node] = true;
}
}
}
}
}6. 문제 풀기
- 프로그래머스/백준 쉬운 문제부터 풀기 시작해서 변수 선언, 타입 등에 익숙해지면 구현, 빈출 알고리즘 문제를 푸는 방식으로 진행했다.
- 기업마다 코딩테스트를 담당하는 곳(프로그래머스, 구름, 잡다 등)이 다르고 문제 유형도 조금씩 다르니, 해당하는 곳에서 문제를 미리 풀어보는 것을 추천한다.
참고
스택 - https://go-coding.tistory.com/5
큐 - https://go-coding.tistory.com/6
큐 - https://songsunkite.tistory.com/156
큐 - https://kwin0825.tistory.com/157
우선순위 큐, 힙 - https://kbj96.tistory.com/49
우선순위 큐, 힙 - https://innovation123.tistory.com/112
정렬 - https://80000coding.oopy.io/21cb57a3-681b-404d-a4ac-8ab0e7289bc0
정렬 - https://jaehee1007.tistory.com/87
정렬 - https://oscarstory.tistory.com/53
트리 - https://readerr.tistory.com/35
dfs, bfs - https://jellili.tistory.com/26