그냥 코딩방

User Flow 설계도

발생한 error

문제 상황

원인

숫자로 변환할 수 없는 문자열이 입력값으로 들어왔을 때 발생

해결방안

입력값을 문자로 비교해서 해결

입력값이 숫자로서 값을 비교하거나 연산하는 것이 아니었기에 사용할 수 있었던 방법

Python 코드

import random
import time

def error_page(mini, maxi):
    print(str(mini) + "~" + str(maxi) + "사이에 숫자만 입력 가능합니다!")

def exit_page():
    print("게임을 종료합니다.", end="")
    for i in range(2):
        time.sleep(0.5)
        print(".", end="")
    exit()

def start():
    while True:
        minimum = 1
        maximum = 100
        print("=== UP & DOWN Game ===")
        print("1. 시작하기")
        print("0. 종료하기")
        action = input()
        if (action == "0"):
            exit_page()
        elif (action == "1"):
            rand_num = random.randint(1, 100)
            # print("rand_num: " + str(rand_num))
            while True:
                print("숫자를 입력해주세요(" + str(minimum) + "~" + str(maximum) + ") >>")
                num = input()
                if not num.isnumeric() or int(num) < minimum or int(num) > maximum:
                    error_page(minimum, maximum)
                    continue
                if (int(num) == rand_num):
                    while True:
                        print("정답입니다!")
                        print("1. 다시하기")
                        print("0. 종료하기")
                        action = input()
                        if (action == "0"):
                            exit_page()
                        elif (action == "1"):
                            minimum = 1
                            maximum = 100
                            rand_num = random.randint(1, 100)
                            break
                        else:
                            error_page(0, 1)
                elif int(num) < rand_num:
                    minimum = int(num)
                    print("UP!")
                elif int(num) > rand_num:
                    maximum = int(num)
                    print("DOWN!")
        else:
            error_page(0, 1)

# Game Start
start()

💡 이 글은 코리아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);
	}
}

기술 면접

팀프로젝트에서 무슨 역할을 맡았는지? 

왜 그 역할을 맡았는지? 

AWS 무료인데 왜 사용해보지 않았는지?

DP에 대해 알고 있는지?
다른 알고리즘과 차별점은 무엇인지?

종이 한 장 가지고 이커머스를 설계

테이블 설계 그리는 동안 왜 그렇게 하는지 중간중간 질문함

회원, 상품, 구매내역, 장바구니 4개 가지고 테이블 구체화 시작

구매내역과 주문내역 구분 해야 되지 않냐는 질문

멤버 아이디가 PK이면 자료형 뭐 쓸지 질문

비밀번호 암호화 안 했는지 질문

sha 알고 있는지 질문

복호화가 안 되는 기술인데 그러면 나중에 회원 비밀번호를 어떻게 비교할지 질문함

백준에서 간단한 for문 문제 손 코딩

문제지에 프로덕션 코드라고 생각하고 작성하라고 쓰여있음

주요 조건이 빠져있는데 의도를 파악하는 것도 테스트

문화 면접

성장이 뭐라고 생각하는지? 

다른 후보자와 비교했을 때 본인의 장점

다른 후보자와 비교했을 때 본인의 단점

(직무적인 게 됐든 생활적인 게 됐든)

스프링이란?

엔터프라이즈용 Java 애플리케이션 개발을 도와주는 오픈소스 경량급 애플리케이션 프레임워크

1. POJO

• 순수 자바 객체
• Java 스펙에 정의된 기술만 사용
• 외부 라이브러리나 모듈을 사용하지 않음
• 특정 기술이나 환경에 종속되지 않음

    2. IoC/DI

• 제어의 역전
• 의존성 주입

    3. AOP

• 공통된 관심사를 분리하여 모듈화 하는 프로그래밍 기법

    4. PSA (Portable Service Abstraction)

• 특정 기술과 관련된 서비스를 추상화하여 일관된 방식으로 사용할 수 있게 함
• 예) JDBC

스프링부트란?

스프링의 문제점을 해결해주기 위해 개발된 프레임워크

스프링 애플리케이션 개발을 빠르게 시작할 수 있도록 도와주는 프로젝트에서 시작

1. 간결한 설정 - xml이 필요 없다 
2. 내장 서버 - tomcat
3. 의존성 관리 간소화 - application.properties의 starter
4. 운영 편의성 - ???

디자인 패턴이란?

프로그래밍 중에 빈번하게 발생하는 문제의 해결방법을 정리해둔 규약

MVC 패턴이란?

디자인 패턴 중 하나

프로젝트를 구성할 때 구성요소를 모델, 뷰, 컨트롤러 3가지 역할로 구분

모델

데이터와 데이터를 가공하는 컴포넌트

1. 사용자가 편집하길 원하는 모든 데이터를 가지고 있어야한다 
2. 뷰나 컨트롤러에 대해서 어떤 정보도 알고 있으면 안 된다
3. 변경이 일어나면 변경 통지에 대한 처리 방법이 구현되어 있어야 한다

뷰

사용자에게 보여지는 인터페이스

데이터와 객체의 입력과 출력을 담당

1. 모델이 가지고 있는 정보를 따로 저장해서는 안 된다
2. 모델이나 컨트롤러에 대해 어떤 정보도 알고 있으면 안 된다
3. 변경이 일어나면 변경 통지에 대한 처리 방법이 구현되어 있어야 한다

컨트롤러

모델과 뷰를 잇는 다리 역할

사용자 이벤트를 처리

1. 모델과 뷰에 대해 알고 있어야 한다
2. 모델이나 뷰의 변경을 모니터링 해야 한다

MVC패턴을 쓰는 이유

각자의 역할에 집중하여 개발하면 유지보수성과 확장성, 유연성이 증가

객체 - 실재하는 모든 것

추상화, 상속, 다형성, 캡슐화가 특징

1. 추상화 - 공통의 속성과 기능을 모아 추출하는 것
2. 상속 - 기존에 클래스를 재활용 하여 새로운 클래스를 만드는 것
3. 다형성 - 어떤 객체의 속성이나 기능이 상황에 따라 다양한 형태를 띠는 것, 메서드 재정의, 메서드 중복정의가 이에 해당
4. 캡슐화 - 서로 연관있는 속성과 기능을 하나의 캡슐로 묶어서 외부로부터 보호하는 것

깃헙 블로그를 만들기 위해 테마를 찾아봤다

내 기준 예쁜 테마 목록을 추려봤다

1. Webjeda Slides

http://jekyllthemes.org/themes/slides/

• PPT 슬라이드에 적합
• 슬라이드 넘어가는 모션이 트렌디함

2. Agency

http://jekyllthemes.org/themes/agency/

• 회사 소개 기본 양식
• 연혁표가 존재

3. Modern Blog

https://inded.xyz/Jekyll_modern-blog/

• 블로그에 적합
• 게시글 클릭 시 모션이 화려함

4. dentistSmile

http://obaez.com/dentistsmile/

• 고객 예약 사이트에 적합
• 서비스에 대한 자세한 설명 작성 가능

5. Spectral

http://jekyllthemes.org/themes/spectral/

• 짧은 설명을 여러 개 쓰기에 적합
• 뒤에 고정된 사진 덕에 스크롤 내리는 모션이 트렌디해 보임
• 화면이 작아지면 스크롤 시에 다르게 동작함

6. Jalpc

http://jekyllthemes.org/themes/Jalpc-jekyll-theme/

• 포트폴리오에 적합
• 연혁표 작성 가능
• 스킬 스탯 표시 7각 그래프 표시 가능

7. ???

https://fullit.github.io/#2section

• 스크롤 시 모션이 화려함
• 글만으로 설명하기에 적합

8. simple-texture

https://yizeng.github.io/jekyll-theme-simple-texture/

• 스크롤에 따른 화면 이동이 트렌디함
• 글만으로 설명하기에 적합

9. Neumorphism

http://jekyllthemes.org/themes/neumorphism/

• 포트폴리오에 적합
• 개발자스러운 디자인
• 반응형 요소가 많음
• 연혁표 작성 가능
• 디자인이 다소 촌스러움

10. jekyll-theme-WuK

http://jekyllthemes.org/themes/neumorphism/

• 스크롤 모션이 트렌디함
• 간결한 디자인
• 글로만 설명하기에 적합

11. uBuild

http://jekyllthemes.org/themes/ubuild/

• 앱, 홈페이지 등의 IT 서비스 소개에 적합
• 깔끔한 디자인

12. Event

http://jekyllthemes.org/themes/event-jekyll-theme/

• 첫 화면 사진으로 이목 끌기 적합

13. web-portfolio

https://github.com/congchu/web-porfolio?tab=readme-ov-file

• 포트폴리오에 적합
• 디자인 예쁨
• 수치 표현할 수 있는 그래프 존재

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();
		}
	}
}