그냥 코딩방

💡 이 글은 코리아IT아카데미 알고리즘 스터디 그룹과 공유하기 위해 작성되었습니다

목차

1. 연습 제작 기준
2. 백준 사용법
3. 핵심 자료구조 & 알고리즘
4. 시간복잡도 계산 방법

연습 제작 기준

• 주에 한 연습씩 (월요일 ~ 일요일)
• 각 연습은 하나의 주제를 가짐 (ex. 스택, dp, bfs, ...)
• 각 연습은 총 7문제 (1일 1문제 컨셉, 필수는 아님)
• 문제 난이도: 브론즈 3개, 실버 2개, 골드 1개, 플래티넘 1개
  (적당한 문제가 없을 시 변동 가능)
• 정답률 높은 문제 위주 (왜? 함정 없이 정석적인 문제)

백준 사용법

📑 JAVA 정답 제출 방법

푼 문제의 ‘제출’ 메뉴에 아래 두가지를 지켜서 제출

1. package 삭제
2. class명 Main으로 수정

위를 지키지 않을 경우 아래의 에러 발생

🏅 solved.ac 연동 방법

solved.ac를 백준에 연동하면 문제&개인 티어를 볼 수 있습니다

1. 백준 사이트 접속
2. 상단 ‘설정’ 클릭
3. 좌측 ‘solved.ac’ 클릭 후 연동 수행

1. 좌측 ‘보기’ 클릭
2. ‘solved.ac 티어’ 메뉴에서 보기로 변경

📊 연습 진행 상황 읽는 법

핵심 자료구조 & 알고리즘

🗃️ 자료구조

• array
• stack
• queue
• graph
• priority queue
• tree
• heap
• dequeue
• linked list
• b-tree
• hash table

*제가 생각하는 중요도 순으로 작성했습니다.

*다른 의견 있으시면 적극 반영하겠습니다.

🤖 알고리즘

• dp
• greedy
• bruteforce
• dfs
• bfs
• 구현
• 수학
• 그래프 이론
• 투포인터
• 게임 이론
• 백트래킹
• prefix sum
• 최단 경로
• 다익스트라
• 이진 탐색

시간복잡도 계산 방법

⏱️ 1억 == 1초

아래 코드는 모두 1초가 걸림

Problem details

https://www.acmicpc.net/problem/17287

Ideas

1. 열린 괄호는 stack에 저장하고, 닫힌 괄호가 나오면 stack에서 빼낸다.
2. 숫자가 나왔을 때, stack에 저장된 모든 열린 괄호의 점수가 해당 숫자의 점수다.

Answer code (Java)

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String n = sc.nextLine();
		Stack<Boolean> point = new Stack<Boolean>();
		int maxi = 0;
		
		for (int i = 0; i < n.length(); i++) {
			if (n.charAt(i) == '[') {
				point.add(true);
				point.add(true);
				point.add(true);
			} else if (n.charAt(i) == '{') {
				point.add(true);
				point.add(true);
			} else if (n.charAt(i) == '(') {
				point.add(true);
			} else if (n.charAt(i) == ']') {
				point.pop();
				point.pop();
				point.pop();
			} else if (n.charAt(i) == '}') {
				point.pop();
				point.pop();
			} else if (n.charAt(i) == ')') {
				point.pop();
			} else if ('0' <= n.charAt(i) && n.charAt(i) <= '9') {
				if (maxi < point.size())
					maxi = point.size();
			}
		}
		System.out.println(maxi);
	}
}

Problem details

https://school.programmers.co.kr/learn/courses/30/lessons/258711

Ideas

1. 들어오는 선 없이 나오는 선이 2개 이상인 점이 정점이다.
2. 정점에서 나오는 선의 갯수가 전체 그래프의 수이다.
3. 정점과 정점에 연결된 선을 지우고 나서, 연결된 선이 없거나 들어오는 선이 하나고 나오는 선이 없는 정점의 갯수가 막대 모양 그래프의 갯수이다.
4. 정점과 정점에 연결된 선을 지우고 나서, 나오는 선이 2개인 정점의 갯수가 8자 모양 그래프의 갯수이다.
5. 전체 그래프의 수에서 막대 모양 그래프의 갯수와 8자 모양 그래프의 갯수를 빼면 도넛 모양 그래프의 갯수이다.

Answer code (Java)

class Solution {
    public int[] solution(int[][] edges) {

        // 배열 생성
        int[] shootCnt = new int[1000000 + 1];
        int[] receiveCnt = new int[1000000 + 1];
        for (int i = 0; i < edges.length; i++) {
            shootCnt[edges[i][0]]++;
            receiveCnt[edges[i][1]]++;
        }
        // 사용하지 않는 점 제거
        for (int i = 1; i <= 1000000; i++) {
            if (shootCnt[i] == 0 && receiveCnt[i] == 0) {
                shootCnt[i] = -1;
                receiveCnt[i] = -1;
            }
        }
        
        // 정점 찾기
        int totalGraphsNum = 0;
        int point = 0;
        for (int i = 1; i <= 1000000; i++) {
        	// Idea1 : 들어오는 선 없이 나오는 선이 2개 이상인 점이 정점이다.
            if (shootCnt[i] >= 2 && receiveCnt[i] == 0) {
                point = i;
                // Idea2 : 정점에서 나오는 선의 갯수가 전체 그래프의 수이다.
                totalGraphsNum = shootCnt[point];
            }
        }
        // 정점 제거
        shootCnt[point] = -1;
        receiveCnt[point] = -1;
        
        // 정점과 연결된 선 제거
        for (int i = 0; i < edges.length; i++) {
            if (edges[i][0] == point || edges[i][1] == point) {
                shootCnt[edges[i][0]]--;
                receiveCnt[edges[i][1]]--;

                edges[i][0] = 0;
                edges[i][1] = 0;
            }
        }
        
        int stickGraphsNum = 0;
        int eightGraphsNum = 0;
        for (int i = 1; i <= 1000000; i++) {
            // Idea3 : 정점과 정점에 연결된 선을 지우고 나서, 연결된 선이 없거나 들어오는 선이 하나고 나오는 선이 없는 정점의 갯수가 막대 모양 그래프의 갯수이다.
            if ((shootCnt[i] == 0 && receiveCnt[i] == 0) || 
                (shootCnt[i] == 0 && receiveCnt[i] == 1)) {
                stickGraphsNum++;
            }
            
            // Idea4 : 정점과 정점에 연결된 선을 지우고 나서, 나오는 선이 2개인 정점의 갯수가 8자 모양 그래프의 갯수이다.
            if (shootCnt[i] == 2) {
                eightGraphsNum++;
            }
        }
        // Idea5 : 전체 그래프의 수에서 막대 모양 그래프의 갯수와 8자 모양 그래프의 갯수를 빼면 도넛 모양 그래프의 갯수이다.
        int doughnutGraphsNum = totalGraphsNum - stickGraphsNum - eightGraphsNum;
        
        int[] answer = {point, doughnutGraphsNum, stickGraphsNum, eightGraphsNum};
        return answer;
    }
}

Problem details

https://codeforces.com/contest/1956/problem/B

Ideas

1. You can only score points if you have two cards of the same number.

Answer code (Java)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t, n, a, ans;
		
		boolean[] checkArr;
		
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			n = sc.nextInt();
			
			ans = 0;
			checkArr = new boolean[200000 + 1];
			for (int j = 0; j < n; j++) {
				a = sc.nextInt();
				if (checkArr[a]) { // You can only score points if you have two cards of the same number.
					ans++;
					continue;
				}
				checkArr[a] = true;
			}
			System.out.println(ans);
		}
	}
}

Problem details

https://school.programmers.co.kr/learn/courses/30/lessons/258712

Ideas

1. 각자의 선물 지수를 따로 기록해둔다.
2. 서로 선물을 주고 받은 내용을 2차원 맵으로 기록해둔다.
   (기록을 이름으로 검색하고 싶어서 맵을 사용했지만, 약간의 스킬을 쓰면 2차원 배열로도 저장이 가능하다.)

Answer code (Java)

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(String[] friends, String[] gifts) {
    	
        Map<String, Integer> answerList = new HashMap<String, Integer>();
        Map<String, Integer> pointList = new HashMap<String, Integer>();
        Map<String, HashMap<String, Integer> > board = new HashMap<String, HashMap<String, Integer> >();
        String[] splStr;
        
        String giver, taker;
        
        for (String gift: gifts) {
            splStr = gift.split(" ");
            giver = splStr[0];
            taker = splStr[1];
            
            // 각자의 선물 지수를 따로 기록해둔다.
            pointList.put(giver, pointList.getOrDefault(giver, 0) + 1);
            pointList.put(taker, pointList.getOrDefault(taker, 0) - 1);
            
            // 서로 선물을 주고 받은 내용을 2차원 맵으로 기록해둔다.
            HashMap<String, Integer> mp = board.getOrDefault(giver, new HashMap<String, Integer>());
            mp.put(taker, mp.getOrDefault(taker, 0) + 1);
            board.put(giver, mp);
        }
        
        for (int i = 0; i < friends.length - 1; i++) {
            for (int j = i + 1; j < friends.length; j++) {
                HashMap<String, Integer> mp = board.getOrDefault(friends[i], new HashMap<String, Integer>());
                int AToB = mp.getOrDefault(friends[j], 0);
                HashMap<String, Integer> mp2 = board.getOrDefault(friends[j], new HashMap<String, Integer>());
                int BToA = mp2.getOrDefault(friends[i], 0);
                
                int aPoint = pointList.getOrDefault(friends[i], 0);
                int bPoint = pointList.getOrDefault(friends[j], 0);
                
                if (AToB > BToA) {
                    answerList.put(friends[i], answerList.getOrDefault(friends[i], 0) + 1);
                } else if (BToA > AToB) {
                    answerList.put(friends[j], answerList.getOrDefault(friends[j], 0) + 1);
                } else if (aPoint > bPoint) {
                    answerList.put(friends[i], answerList.getOrDefault(friends[i], 0) + 1);
                } else if (bPoint > aPoint) {
                    answerList.put(friends[j], answerList.getOrDefault(friends[j], 0) + 1);
                }
            }
        }
        
        int answer = 0;
        for (String key: answerList.keySet()) {
            if (answerList.get(key) > answer) {
                answer = answerList.get(key);
            }
        } 
        
        return answer;
    }
}

Problem details

https://codeforces.com/contest/1956/problem/A

Ideas

1. The a(1) is the smallest number of all a(k).
2. All players of order greater than or equal to a(1) are kicked out.

Answer code (Java)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t, k, q, a;
		
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			k = sc.nextInt();
			q = sc.nextInt();
			
			a = 0;
			for (int j = 0; j < k; j++) {
				if (a == 0) a = sc.nextInt();	// The a(1) is the smallest number of all a(k).
				else sc.nextInt();
			}
			
			for (int j = 0; j < q; j++) {
				System.out.print(Math.min(a - 1, sc.nextInt()) + " ");	// All players of order greater than n(i) are kicked out.
			}
			System.out.println();
		}
	}
}

Problem details

https://codeforces.com/problemset/problem/1955/B

Ideas

1. The b(1,1) is the smallest number of all b(i,j).
2. The numbers in array b and progressive square must be equal in number.

Answer code (Java)

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t, n, c, d, b;
		String ans;
		
		Map<Integer, Integer> bMap;
		int miniVal, tmpSum;
		
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			n = sc.nextInt();
			c = sc.nextInt();
			d = sc.nextInt();
			bMap = new HashMap<Integer, Integer>();
			
			miniVal = 1000000001;
			
			for (int j = 0; j < n * n; j++) { // n * n < 25 * 10000
				b = sc.nextInt();
				bMap.put(b, bMap.getOrDefault(b, 0) + 1);
				
				if (b < miniVal) {
					miniVal = b;
				}
			}
			
			ans = "YES";
			for (int j = 0; j < n; j++) {						// n < 500
				for (int k = 0; k < n; k++) {					// n < 500
					tmpSum = miniVal + k * c + j * d;			// Idea1 : The b(1,1) is the smallest number of all b(i,j).
					if (bMap.getOrDefault(tmpSum, 0) <= 0) {
						ans = "NO";
						break;
					}
					bMap.put(tmpSum, bMap.get(tmpSum) - 1);		// Idea2 : The numbers in array b and progressive square must be equal in number.
				}
				if (ans.equals("NO")) break;
			}
			System.out.println(ans);
		}
	}
}

Problem details

https://codeforces.com/contest/1955/problem/A

Ideas

1. If 2a > b, then buy as much as you can at the b price.
   If 2a < b, then buy as much as you can at the a price.
2. If n is odd, then you should buy at least one at the a price.

Answer code (Java)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t, n, a, b, ans;
		
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			ans = 0;
			n = sc.nextInt();
			a = sc.nextInt();
			b = sc.nextInt();
			
			// Idea2 : If n is odd, then you should buy at least one at the a price.
			if (n % 2 == 1) {
				ans += a;
				n--;
			}
			
			// Idea1 : If 2a > b, then buy as much as you can at the b price.
			//         If 2a < b, then buy as much as you can at the a price.
			if (2 * a > b) {
				ans += n / 2 * b;
			} else {
				ans += n * a;
			}
			System.out.println(ans);
		}
	}
}

문제 잘 풀어놓고 이상한 곳에서 삽질했다

JAVA11에서 제출 시에 체크할 사항 정리해 보자

package problem_solve;

import java.util.Scanner;

public class Boj28701 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int sum = (1+n)*n/2;
		
		System.out.println(sum);
		System.out.println(sum*sum);
		System.out.println(sum*sum);
	}
}

위는 문제 풀이 코드다

여기서 제출 전에 작업해 줄 것이 2가지 있다

1. package 지우기

2. class명 Main으로 수정

제출을 위해 수정한 코드는 아래와 같다

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int sum = (1+n)*n/2;
		
		System.out.println(sum);
		System.out.println(sum*sum);
		System.out.println(sum*sum);
	}
}

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int[] v = new int[100];
		int num;
		
		for (int i = 0; i < n; i++) {
			num = in.nextInt();
			System.out.println(num);
			v[i] = num;
		}
		for (int i = 0; i < n; i++) {
			System.out.println(v[i]);
		}
		
		in.close();
	}

}

• Scanner 및 배열 사용 숙달중..

https://codeup.kr/problem.php?id=1403&rid=0

package problem_solve;

public class CodeUp1083 {
	
	/*
	 * 3 6 9 게임은?
	 * 여러 사람이 순서를 정해 순서대로 수를 부르는 게임이다.
	 * 만약 3, 6, 9 가 들어간 수를 자신이 불러야 하는 상황이면, 대신 "박수" 를 쳐야 한다.
	 * 33까지 진행했다면? "짝짝"과 같이 박수를 두 번 치는 형태도 있다.
	 * */

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int one, ten;
		int cnt = 0;
		for (int i = 0; i < 100; i++) {
			one = i%10;
			ten = i/10;

			cnt = 0;
			if (one!=0 && one%3==0) cnt++;
			if (ten!=0 && ten%3==0) cnt++;
			if (cnt == 0) {
				System.out.println(i);
			} else if (cnt == 1) {
				System.out.println("박수");
			} else if (cnt == 2) {
				System.out.println("짝짝");
			}
		}
	}
}

실수 포인트!

- 1의 자리나 10의 자리가 0인 경우에 박수를 치지 않아야 한다