코딩테스트란?

CR7_Fantastic·2025년 1월 4일
CodingTestJava기초메소드이론

Coding_Test

목록 보기
1/5

코딩테스트란?

개발자의 알고리즘과 자료구조에대해 정확히 알고있는지 확인하고 그 문제해결 능력을 확인하기위해 채용과정에서 사용되는 시험방법

평가요소

  • 기술 역량 : 프로그래밍 문법, 알고리즘, 자료구조 등을 평가함
  • 문제 해결 능력 : 주어진 제시문을 잘 이해해서 문제를 어떻게 분석하여 어떤 해결책을 찾아 내는지 확인함
  • 코드 구현 능력 : 이를 어떻게 코드로 구현하는지 파악함 (스타일 가이드, 주석 등 코드를 통한 협업을 얼마나 잘하는지도 평가함)

알고리즘 학습방법

  • 자료구조
    • Array/List
    • Linked List
    • Stack
    • Quene
    • Dequene
    • Priority quene
    • Hash Table
    • Tree
    • Graph
    • Heap
  • 알고리즘
    • Simulation/Implementation
    • Search
    • Sort
    • Greedy
    • Dynamic programming
    • Dijkstra
    • Floyd-Warshall
    • Prim
    • Kruscal
    • DFS
    • BFS

시간복잡도와 공간복잡도

시간복잡도

  • 알고리즘을 프로그램으로 실행해 완료하는데까지 걸리는 시간
  • 시간복잡도 = 프로그램 컴파일 시간 + 실행시간
    • 컴파일 시간 → 고려 안해도 됨
    • 실행시간에 따라 컴퓨터의 성능이 달라질수 있으므로 명령문의 실행빈도수를 계산해 추정

분석 방법

  • 입력크기 n에 대한 실행시간의 증가율만 분석하는 점근적 분석(Asymptotic Analysis)을 활용
    • 증가율만 보기에 실행 빈도 함수의 상수항과 계수 무시하고 가장 큰 하나의 항에 대해서 차수 표기법(Order Notation)으로 시간 복잡도를 표기
    • 무시하는 이유 : 정확한 연산의 개수를 알고 싶은게 아니라 input n에 따른 증가 추세가 궁금하기 때문에 n이 커질수록 상수항과 계수의 영향력은 미미해진다

공간복잡도

  • 프로그램의 실행에서 완료까지 얼마나 많은 공간(가변 공간)가 필요한지
  • 총 필요 공간= 고정공간 + 가변공간
    • 고정공간
      • 입출력 횟수, 크기와 관계없이 동일함(코드 저장 공간, 단순 변수, 상수 등)
      • int, double, 크기가 정해진 배열
      • 상수 → 성능에 큰 영향을 안준다
    • 가변공간
      • 필요에 따라 동적으로 할당, 해제되는 메모리공간
      • 특정 instance에 따라서 사이즈가 달라지는 변수
      • 성능에 큰 영향을 미친다
  • 통상적으로 시간복잡도와 공간복잡도는 반비례 관계에 있음
    • 최근에 하드웨어가 대용량으로 나오기 때문에 공간복잡도 < 시간복잡도

빅오 표기법(Big-O Notation)

  • 실행 빈도 함수의 상한을 나타내기 위한 표기법
  • 최악의 경우에도 g(n)의 수행시간 안에는 알고리즘 수행되어야함
  • 일반적으로 최악의 경우를 고려한 해결책을 찾기에 Big-O를 주로 사용한다
  • O(1): Hash Table에서의 검색/삽입.
  • O(log N): 이진 탐색(Binary Search).
  • O(N): 단순 배열 순회.
  • O(N log N): 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort) 평균.
  • O(N²): 중첩 반복문을 사용하는 경우.
  • O(2^N): 재귀를 활용한 피보나치 수열 계산.
  • O(N!): 순열(모든 경우의 수 탐색) 계산.

시간 복잡도를 기반으로 코딩 테스트에서 효율적인 풀이를 설계하는 방법

  1. 문제 크기(N)를 분석하여 요구되는 시간 복잡도 범위를 추정.
    • N ≤ 1,000,000인 경우: O(N log N) 이하 필요.
    • N ≤ 1,000인 경우: O(N²)까지 가능.
  2. 알고리즘 선택 기준
    • N의 크기에 따라 완전 탐색, 이분 탐색, 동적 프로그래밍 등 선택.
  3. 최적화
    • 중복 계산 제거, 캐싱 사용 등.

예시) 시간 복잡도를 고려하지 않았을 경우의 문제

풀이 1: 시간 복잡도를 고려하지 않은 완전 탐색 (Brute Force)

import java.util.*;

public class TwoSumBruteForce {
    public static int[] findPair(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{nums[i], nums[j]};
                }
            }
        }
        return new int[]{}; // No pair found
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 7, 5, 4};
        int target = 9;
        int[] result = findPair(nums, target);

        System.out.println(Arrays.toString(result));
    }
}

외부루프(i): O(N)

내부루프(j): O(N)

총 시간 복잡도: O(N²)

문제점

  • 답은 도출되지만 입력의 크기가 커지기 때문에 실행시간도 늘어남→ 시간복잡도에 걸려 실패

❓How resolve this problem?

→ HashMap을 사용해 시간복잡도를 최소화 한다.

import java.util.*;

public class TwoSumOptimized {
    public static int[] findPair(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();// hashMap을 이용하여 현재숫자 저장
				//<현재까지 탐색한 숫자, 해당 숫자가 존재한다는 표시>
				
        for (int num : nums) { //배열 nums의 첫 번째 원소부터 마지막 원소까지를 순서대로 탐색
            int complement = target - num; //목표값에서 현재숫자를 뺌 ex) 9-1=8
            if (seen.containsKey(complement)) { //seen에 complement가 존재하는지 확인
                return new int[]{complement, num}; //존재 하면 새로운 int 배열에 반환!
            }
            seen.put(num, 1); //해당 숫자(num)가 존재
        }
        return new int[]{}; // 조건을 만족하는 쌍이 없을 때 빈 배열 반환
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 7, 5, 4};
        int target = 9;
        int[] result = findPair(nums, target);

        System.out.println(Arrays.toString(result));
    }
}

단일루프: O(N)

Hash Map 조회와 삽입: O(1)

총 시간 복잡도: O(N)

⇒ 결론: 답이 도출되어도 시간 복잡도에 따라서 실행시간 더 짧게 걸린다면 훨씬 더 메리트 있는 정답이다.

Java: 코딩테스트에서 자주 쓰이는 method

라이브러리

import java.util.*;
import java.io.*;

변수선언

String[] arr1 = new String[5];
int[] arr2 = {1,2,3};
int N=3
int[] arr3 = new int[N];

Arrays

int arr[]= {10,8,11,2,3,0}

//오름차순 {0,2,3,8,10,11}
Arrays.sort(arr1);

//내림차순
Arrays.sort(arr1, Collections.reverseOrder());

//일부만 정렬 {2,8,10,11,3,0}
Arrays.sort(arr1,0,4);

// 4. 오름차순 정렬하면 binary search로 특정 값을 찾을 수 있다.
Arrays.binarySearch(arr1, 2);

// 5. 배열을 어레이리스트로 변환!
List list = Arrays.asList(arr1);

// 6. 배열의 특정 범위 자르기
int tmp[] = Arrays.copyOfRange(arr1, 0, 3);

length/length()/size()

  • length: 배열의 길이
  • length(): String related object(str.length())
  • size(): Collections object
// 1. length
int[] arr = new arr[3];
System.out.println(arr.length);

// 2. length()
String str = "java";
System.out.println(str.length());

// 3. size()
ArrayList<Integer> list = new ArrayList<>();
System.out.println(list.size());

String

String str = "hello world";

//길이 반환
str.length();

//빈문자열 체크
str.isEmpty();

//문자 찾기
str.charAt(0);  // 'h' -> 문자 반환
str.indexOf("e"); //1 -> 인덱스 반환
str.lastIndexOf("r"); // 8->마지막으로 문자가 속한 인덱스 반환

// 문자 자르기
str.substring(0, 5);  //인덱스 0 이상 5미만 위치의 문자열 반환
str.substring(3); //인덱스 3 이상 위치의 문자열 반환

for(int i = 0; i < str.length(); i++) str.charAt(i);

//문자 치환(바꾸기)
//replace([기존문자],[바꿀문자]) 
str.replace('e','o'); // 모든 [기존문자]를 [바꿀문자]로 치환

//문자 반복
str.repeat(k) //k번 반복

//문자 포함 여부 판단
str.contains("hell");

//문자열을 배열로 만들고 싶을 때
String str = "12345";
String[] Arr = str.split("");
char[] cRsp = str.toCharArray();

// 대소문자 변경
str = str.toUpperCase();		// HELLO WORLD
str = str.toLowerCase();		// hello world

StringBuilder

StringBuilder sb = new StringBuilder();

sb.append("A"); //문자열 추가하기
sb.insert(1,"B"); //중간에 문자열 삽입하기
sb.delete(0,1); //문자열 삭제하기(~부터 ~까지)
sb.reverse(); // 문자열 뒤집기
sb.toString(); // 문자열 변환

String str = sb.append("A").append("B").append("C").append("D")
			.insert(4,"Java").delete(4,8).reverse().toString();  //메소드 체이닝

HashMap

HashMap<String,Integer> = new HashMap<>();// HashMap 선언

// key-value 넣기
hm.put("java",0);

//key로 값 가져오기
hm.get("java");

//containsKey()로 존재유무 확인
if(!hm.containsKey("java")){
	hm.put("java",1)
}

// keySet() 함수로 맵 순회
for(String key : hm.KeySet()) {				
	hm.get(key);
}

ArrayList

// 선언
ArrayList<String> list = new ArrayList<>();

// 삽입
list.add("java");			// {"java"}
list.add(0, "python");			// {"python", "java"} (0번째 인덱스에 삽입)

// 수정
list.set(1, "kotlin");			// {"python", "kotlin"}

// 삭제
list.remove(1);				// {"python"}

// 가져오기
list.get(1);

// 값 존재 유무 확인
list.contains("java");		// false
list.indexOf("python");		// 0 존재하면 인덱스 리턴

// 리스트 길이
list.size();

//리스트에 다른 리스트 요소가 전부 포함되어 있는지 여부 체크
list.containsAll(list2);

//문자열 타입 배열을 list로 변환
String[] temp = {"apple","banana","lemon"};
List<String> list = new ArrayList<>(Arrays.asList(temp));

//list를 문자열 배열로 변환
List<String> list = new ArrayList<>();
String[] temp = list.toArray(new String[list.size()]);

Collections 관련 메서드

int[] temp = {1,2,3,10,20};
List<Integer> list = new ArrayList<>(Arrays.asList(arr));

//정수형 list 원소 중 최대, 최소값
Collections.max(list);
COllections.min(list);

//List 정렬
Collections.sort(list);	//오름차순(ASC)
Collections.sort(list, Collections.reverseOrder()); //내림차순 (DESC)

//List 뒤집기
Collections.reverse(list);

Math 라이브러리

// 1. 최대 최소
Math.max(10, 2);
Math.min(10, 2);

// 2. 절대값
Math.abs();

// 3. 올림 내림 반올림
Math.ceil(-3.2);		// -3
Math.floor(-3.2);		// -4
Math.round(-3.26);		// -3	첫째자리에서 반올림

// 3-1. 소수 둘째, 셋째 자리에서 반올림 하고 싶다면
double a = 1.23456;
String b = String.format("%.1f", a);	// .1f는 둘째자리에서 반올림

// 4. 제곱 제곱근
Math.pow(2, 2);		// 2^2 = 4
Math.sqrt(4);		// 2
profile
CR7_Fantastic
우직한, 나무같은 개발자
다음 포스트

재귀함수 & 재귀 알고리즘 (Recursion)

2개의 댓글

comment-user-thumbnail
히껑
2025년 1월 5일

🌳🌲🌴🌳🌲🌴

답글 달기
comment-user-thumbnail
Federico-15
2025년 1월 6일

화이팅!

답글 달기