코테 문제유형 정리 + 팁

 

전역

문제가 안풀린다면?

1. 유형조차 모르겠다 (뭘 써야할지 모르겠다)

2. 방법을 아는데 틀린다 (어딘가 실수했을 부분이 있을거다)

 2-1. 범위를 초과했다 (int범위를 넘어 long으로 처리 등)

 2-2. 문제의 조건을 까먹었다 (문제에서 제시한 예외, 숨은 예외)

3. 어디가 틀렸는지 모르겠다 (실수할만한 부분을 다 체크했는데 왜 틀렸는지를 모르겠다

 3-1. 유형을 아예 잘못생각했다.

 

 

공통 팁

1. 자료구조를 활용할 때, 값과 인덱스를 둘 다 활용할 수 있다면 인덱스를 사용하는 것이 활용범위가 더 넓다.

2. 범위 체크 잘하기 (int범위를 넘는 경우 조심)

3. 최적화 문제의 경우 brute force가 아니라면 대부분 그리디나 DP로 풀린다. 먼저 그리디로 접근해보고 안된다면 DP로 접근하기

4. map이나 set같은 자료구조를 쓰는 것보다 index에 대한 value를 활용하여 배열로 접근하는 것이 훨씬 간단하다 (BOJ16472)

 

배열

1. 2차원 배열 인덱스를 탐색할 때, %연산과 /연산을 표현해서 연속된 인덱스로 접근 가능하다.

int[][] arr = new int[N][M];
for(int i=0; i<N*M; i++) {
    System.out.println(arr[i/M][i%M]);
}

 

 

 

 

 

코테에 많이 나오는 유형

- 구현, 그리디

- 그래프 탐색(BFS, DFS)

- 이분 탐색, 파라미터 탐색

- DP (LIS, LCS, Knapsack)

- 자료구조(스택, 큐, 우선순위 큐, 덱)

- 백트래킹

- 트리, 그래프(MST, 이진트리, 위상정렬, union-find, floyd, dijkstra)

 

투 포인터

- 투 포인터 템플릿

int l = 0, r = n-1;
while(l<r) { 이진탐색과 상이하게 종료조건에 등호가 들어가지 않는다.
    if(len[l]+len[r]==x) {
        // 찾음
        break;
    } else if(len[l]+len[r]>x) {
        r--;
    } else {
        l++;
    }
}

 

- BOJ 2531(회전 초밥) >> 투 포인터 사용

: 투포인터 사용시 모든 증가로직과 감소로직은 묶어서 실행해야 함 (https://www.acmicpc.net/source/64968030)

 

- BOJ 2470(두 용액), BOJ 2467(용액) >> 투 포인터 사용

: 투포인터 사용시 whlie문 등호 있으면 안됨

 

- BOJ3649(로봇 프로젝트))

: 투포인터로 등호조건을 찾을때는 l과 r의 증감순서가 중요하지 않다는 것을 기억하자. (답을 지나칠 일은 없다)

 

 

 

 

Stack

- BOJ 9935(문자열 폭발), 16120(PPAP) >> 문자열 + Stack

: 문자열을 char배열로 변환(str.toCharArray())하고 부분문자열이 일치하는지 검사(stack.get()이용)

 

- BOJ 2493(탑), 17298(오큰수), 17299(오등큰수) >> "오른쪽에 있는 것 중에서 가장 왼쪽에 있는 것"

: 스택에 넣었다가 조건에 만족하는 것이 나오면 연속으로 빼주기. 끝까지 남은것은 조건을 만족하는 것이 없음

스택에 인덱스를 넣으면 인덱스를 활용해서 바로 arr값까지 구할 수 있다. 하지만 arr값을 직접 넣으면 인덱스를 알 수 없다.

https://www.acmicpc.net/source/64008052를 https://www.acmicpc.net/source/64008563로 수정한 것을 보면 장점을 확실히 알 수 있음. 왼쪽코드는 테스트케이스가 worst case로 나오면 시간초과 가능성이 충분해보임

 

 

 

Binary Search

- 이진탐색 템플릿

int 정답;
while(left<=right) {
  mid = (left+right)/2;
  int 정답후보 = function(mid);
  if(정답후보>=최소정답) {
    left = mid+1;
    정답 = Math.min(정답, mid);
  } else {
    right = mid-1;
  }
}

 

- BOJ 1654(랜선 자르기), 2805(나무 자르기) >> 대표적인 이분탐색 문제

: 답을 범위를 정해놓고 이분탐색해서 찾아내는 문제

 

- BOJ 1365(꼬인 전깃줄) >> 이분탐색을 사용한 LIS

: Well-known 문제. 간단히 순서대로 선을 이어줄 때, 직전에 들어왔던 입력값보다 작은 값이 입력되면 꼬이게 된다

 

- BOJ 2343(기타 레슨) >> 매개변수 탐색

: 템플릿 (while(l<=r), l = mid+1, r = mid-1) 확인하기, 조건 확인하기 (https://www.acmicpc.net/source/65075124)

 

 

 

DP

- BOJ 2293(동전 1) >> DP 기준의 변화 (for문 안팎 전환)

: "동전의 순서가 달라도 같은 것으로 취급"

-> 금액 기준으로 사용가능한 동전의 경우의 수를 구하는것이 아니라, 사용가능한 동전을 기준으로 금액을 구함

 

 

 

DFS

- Softeer 출퇴근길 >> 중복 방문이 가능할 경우 dfs 역추적은 불가능한 것으로 보임

-> 방향성 그래프에서 중복방문이 가능할경우 한번 방문했다고 재방문을 막을경우 탐색하지 못하는 경로가 생길 수 있다.

-> 방향성 그래프에서 역방향 그래프를 만들면 해당 노드로 올 수 있는 점들을 한번의 탐색으로 구할 수 있다.

 

 

 

BFS

오답시 체크할 위치 : 인덱스 위치 잘못기재([i][j],[j][i]), 큐 or visited 초기화 로직, 큐 삽입조건문

- BOJ 2636(치즈) >> 고려해야 될 것이 여러개인 BFS

: 문제를 풀기전에 모든 조건을 완벽히 시뮬레이팅 해놓고 들어가야 헛수고를 덜함.

★ 추가로 BFS는 큐에 넣은 직후 갱신해주어야 시간초과가 나지 않음. ★

https://www.acmicpc.net/source/64076941과 https://www.acmicpc.net/source/64077141에서 bfs코드 부분을 비교해보면 알 수 있다.

 

- BOJ 13549(숨바꼭질 3) >> 큐의 앞쪽에 있는것이 무조건 낮은 depth를 가져야 함.

: BFS시 같은 루프단계에서도 우선순위가 존재한다면, 순서를 지켜주어야함

 

- BOJ 4179(불) >> BFS는 방문여부 체크 배열(visited) 필수라고 할 수 있음

- BOJ 11048(이동하기) >> BFS는 visited 배열 필수! 값으로만 체크하다보면 값이 같고 방문하지 않은 곳을 탐색하지 않을 수 있다

(https://www.acmicpc.net/source/81696419, https://www.acmicpc.net/source/81696800 차이 비교)

 

 

 

 

Backtracking

- BOJ 1987(알파벳) >> dfs+백트래킹인데 많이 헷갈린 문제

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

//시간복잡도가 어떻게되지?
//bfs는 백트래킹이 안되므로 불가
public class Main
{
    static int R, C;
    static char[][] board;
    static boolean[] visit = new boolean[26];
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static Stack<Node> stack = new Stack<>();
    static int max = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line_1 = br.readLine().split(" ");
		R = Integer.parseInt(line_1[0]);
		C = Integer.parseInt(line_1[1]);
		board = new char[R+1][C+1];
		
		for(int i=1; i<=R; i++) {
		    char[] line_R = br.readLine().toCharArray();
		    for(int j=1; j<=C; j++) {
		        board[i][j] = line_R[j-1];
		    }
		}
		
		stack.add(new Node(1, 1, 1));
		visit[board[1][1]-'A']=true;
		
		while(!stack.isEmpty()) {
		    Node n = stack.pop();
		    max = Math.max(max, n.depth);
		    
		    for(int i=0; i<4; i++) {
		        int nx = n.x+dx[i];
		        int ny = n.y+dy[i];
		        
		        if(1<=nx && nx<=C && 1<=ny && ny<=R) {
		            if(!visit[board[ny][nx]-'A']) {
		                visit[board[ny][nx]-'A'] = true;
		                stack.add(new Node(nx, ny, n.depth+1));
		                flag = true;
		            }
		        }
		    }
		    if(!flag) { //더이상 깊이탐색이 이루어지지 않음
		        stack..?
		    }
		}
	}
}

class Node {
    int x;
    int y;
    int depth;
    
    public Node(int x, int y, int depth) {
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}

 

 

트리

 

 

 

그래프

- BOJ 20040(사이클 게임) >> Union-find를 통한 사이클 판별

: union과 find 템플릿 익히기 (find를 while문이 아닌 재귀로 구현해야 하는 이유: https://www.acmicpc.net/problem/20040)

- BOJ 1446(지름길) >> Dijkstra

: map정보를 초기화해주고, 초기화한 map을 이용해서 dist를 초기화해야 함 (처음에 시작점과 연결된 점들의 dist 정보는 초기화되어있어야 함)

- BOJ 10282(해킹) >> Dijkstra

: 다익스트라는 BFS와 다르게 방문 직후에 방문설정을 하면 안된다.

- BOJ 2262(줄 세우기) >> 위상 정렬

: 진입 차수 배열을 만들고, 차수가 0인것이 다음 정렬 순서가 된다. 이를 반복해주면 된다.

 

그리디

- BOJ 5585 (거스름돈), BOJ 1931(회의실 배정) >> 그리디 well-known 문제들

그리디의 경우 코테에서 이정도 난이도로 출제된다. (가능성 낮음)