PS(Problem Solving)

알고리즘 공부
- 수단
  - 백준 강의
  - 유튜브 강의 - 종만북
- 구현력(순서도 활용)
  - 내가 어떤 프로그램을 만들고자 하는지 명확히
  - 무엇을 입력받아 어디에 저장하고 어떤 과정을 거쳐, 중간 결과로 무엇을 겅도 최종적으로 이런 결과물을 추력
- 문제해결능력
  - 양질의 문제 풀기
  - 접근한 다양한 방법들을 잘 정리
- 배경지식
  - 프로그래밍 문법
  - 알고리즘
  - 자료구조
  - 선형대수
  - 확률
양보다는 질좋은 문제
- USACO
- 한국정보올림피아드
- AtCoder
- Codeforces
좋은 랭작도 중요
- 코테를 준비한다면
  - 배열, 트리, 그래프, 힙, BST, 스택, 큐 등 자료구조
  - DFS/BFS, 백트래킹, 정렬, DP, 분할 정복, 최단거리 등 알고리즘
- 구현 능력을 키우기 위해 많이 푸는 것도 중요
- USACO Bronze, 정올 초등부, AtCoder/Codeforces 쉬운 문제
- BOJ 문제집(C++ 배우기)
오래 붙잡고 있는 것은 결코 도움이 되지 않음
- 솔루션이 떠오르지 않아 아무 진척도 없는 단계
- 약 1시간 정도
- 솔루션을 보고 코드를 본다면, 자신이 안 보고 코드를 작성해서 제출해야 함
좋은 멘토
구체적은 목표, 스스로의 기준 설정
함께 공부하기
- 스터디
- 블로그

PS study 단계

PS 입문

체계적으로 문제 풀기
코딩과 디버깅
분석과 증명
brute-force
정렬
재귀
분할 정복
구간 합
투 포인터
수학 기초
큐
스택
트리 기초
탐색(BFS, DFS)
그래프 기초
백 트래킹
우선순위 큐

PS 초급

이분 탐색(parametric search)
그리디
DP 기초
좌표 압축
수학 초급(소수 판정)
union-find
MST(크루스칼, 프림)
다익스트라
플로이드
벨만 포드
위상정렬
bitwise operation
trie
기하 기초
삼분 탐색(tenary search)

PS 중급

정수론(페르마 소정리, 에라토스 테네스)
DP 중급(tree DP, bitwise DP, ..)
세그먼트 트리
plane sweeping
sqrt decomposition
offline query
binary lifting, LCA in tree
큰거 작은거
meet in the middle
KMP
해싱(라빈 카프)
Z algorithm
euler tour trick
SCC, 2-SAT
convex hull
포함 배제의 원리
constructive
randomize
interactive

PS 고급

수학(확장 유클리드, 중국인의 나머지 정리, 가우스 소거법)
세그먼트 트리 lazy propagation
merge sort tree
persistent segment tree
단절점, 단절선
BCC
이분 매칭
네트워크 플로우
MCMF
min cut
Suffix Array
manacher
아호 코라식
스프라그-그런디
PBS
DP 최적화(Convex hull trick)
DP 최적화(D&C opt)
DP 최적화(knuth opt)

PS 고급+

Heavy-light decomposition
centroid decomposition
offline dynamic connectivity
수학(뫼비우스 반전 공식, 번사이드 보조정리, 홀의 결혼 정리)
FFT
connection profile DP
DP 최적화(Slope trick)
DP 최적화(Aliens trick)
DP 최적화(monotone queue opt)
DP 최적화(Hirschberg)
kitamasa
splay tree
link cut tree
general matching
matroid
eertree
voronoi

코딩테스트(?)

개발자의 기초적인 소양을 보는 시험 : 주어진 시간 동안 주어진 문제를 요구사항에 맞게 프로그래밍
- 기초 소양 : (문제 > 모델링(추상화) > 절차적 사고 > 구현)
  - 추상화(상황 분석) : 배열이 들어오고, 최소와 최대를 뺀 값
  - 절차적 사고 : 정렬? 시간복잡도.. 내장함수? 반복문?
  - 구현 능력
- 요구사항 : 구현 조건이 복잡한 언어 영역(조건문, 함수 구현), 문제를 읽고 분해하는 연습이 필요
  - 구현 : 파싱, 해싱, 정렬, 시뮬레이션
  - 탐색 : 탐색(BFS, DFS), 완전탐색(백트래킹)
  - 자료구조 : 스택, 큐 힙 등
  - 알고리즘 : Greedy, DP, 이분탐색 등
- 구현 : 어떤 내용이 구체적인 사실로 나타나게 함 -> 문제 조건을 코드로 작성하게 돌아가게 함
  - 모든 프로그래밍 = 구현 문제
- 환경 체크(사용 언어) : 장/단점에 따라 언어를 바꿔 사용하는 것이 포인트
  - C++ : 비교적 문법은 어렵지만 빠른 속도, STL 등의 장점(재귀함수, 자료구조 사용 시)
  - Python : 쉽고 문법이 간단, 범용성이 넓음, 하지만 느린 단점(string, 정렬, 파싱 등 객체를 다룰 시)
  - Java : 비교적 문법도 어렵고 느린 편, 하지만 Java를 필요하는 직군이 많음
- 에러
  - 컴파일 에러(CE) : 문법 오류
  - 시간 초과(TLE) : 최적화 필요 (반복문, 무한루프)
  - 메모리 초과(MLE) : 최적화 필요 (스택, 힙 메모리)
  - 런타임 에러(RE) : 과정 오류 (0으로 나눈 경우, index 오류, 무한 루프)
  - 틀렸습니다(WA) : 수 많은 이유..
    - 제한 및 대소 관계 (이상, 이하, 초과, 미만, mix, max)
    - 예외 처리 (단, 없는 경우 -1을 출력한다~)
    - 입력과 출력 (공백, 양식, 순서, 정렬 유무)
    - 시간 제한과 메모리 제한 (알고리즘, 자료구조 선택)
    - 알고리즘이 맞는가?
    - 생각한 로직대로 구현했는가? (중복 처리, 예외처리, 불필요한 반복문)
    - 불필요한 반복문이 있는가?
    - 중복을 처리했는가?
- 디버깅의 반복 + 멘탈 관리가 중요
- 각 단계별 보완
  - 모델링
    - 수치 및 조건 정리 (미리 변수와 함수를 세팅)
    - 전체적인 흐름 그리기
    - 입출력 예제 이해
  - 절차적 사고
    - 필수 알고리즘은 암기
    - 설명과 함께 풀어보기
    - 유형 많이 풀어보기
  - 구현
    - 디버깅 연습 필수
    - print() 를 활용하여 디버깅
    - 쉽고 간단한 문제를 많이 풀기
    - 본인만의 스타일 만들기

코딩테스트 준비

가장 기본적인 준비
- C++ / Python 기본 문법 공부
  - 코드업 기초 100제
    - CodeUp
  - 그리디, 탐색유형(BFS, DFS), DP 유형 문제 풀이
    - BFS/DFS + 재귀가 가장 기본 (구현)
      - 부분 상태 탐색 (위치 이동, 수) : 상태에 대한 체크 함수
      - 전체 상태 탐색(전체 map) : N차원 배열을 조정하는 방법
      - 그외 : Flood Fill, 트리 순회
    - 알고리즘 지식
      - 위상정렬(Topological Sort)
      - 최소신장트리(MST)
      - 최단 거리
  - BOJ
  - 특정 기업 대상 기출문제
    - 삼성전자(BOJ, SW역평기출)
    - 카카오(프로그래머스 기출)
PS 연습
- 삼성전자
  - SWEA
    - 난의도 3~5
  - BOJ
- 브루트 포스, DP, 큐/스택, DFS, BFS, 탐욕법
- 카카오
- SW 역량테스트
  - SWEA
  - B형 공부
운영체제
- 공룡책

Python

Python 의 기본 자료형

single
- Integer
  - 수의 크기 제한이 없음
  - str(123)로 쉬운 형변환
  - 연산, 함수 사용 시, float 로 변환되는 경우를 체크
    - 나눗셈은 / 가 아닌 // 로 안전하기 나누기 (또는 divmod 사용)
- Float
  - 연산에서는 사용하지 말자! (실수 오차 발생), (필요할 경우 Decimal 사용)
  - 유리수 연산은 가능하면 tuple 등으로 분자/분모를 따로 처리
- String
  - String은 변하지 않는(immutable)변수이므로 list로 변환하여 사용
  - ’+’ 연산과 ‘*’ 연산 조심하기
    - join() method 활용
  - .split() .replace() .find() 등 다양한 method 활용
  - Slicing이 자유로움
  - char를 ord와 chr로 다루기 (ASCII code 사용 시)
- Boolean
  - 논리 연산과 활용
  - Short Circuit (앞 항에서 결과가 결정되면 뒷 항은 확인하지 않음)
    - or 연산 앞 항이 참이거나 and 연산에 앞 항이 거짓일 경우
  - 모든 문제의 기본 : True/False
container
- List (like array)
  - List Comprehension 사용
    - list_arr = [i for i in range(100)]
  - sort, sorted 구분
    - lst.sort() : 원본 객체가 정렬된 결과로 변경
    - sorted(lst) : 정렬이 된 객체를 반환하고 원본 객체는 변하지 않음
  - len, sum, max, min 등 활용
  - slicing, [-1] 등 음수 인덱스 활용
    - # 첫 번째 인덱스에 값을 삽입하는 방법 lst = [1] + lst lst[:0] = [1] # 마지막 인덱스 원소 확인 lst[-1]
  - reduce, filter 도 활용
- Tuple
  - 초기 상태 표현 시 간결하게 사용 가능
    - a, b, c = 0, 0, 0
  - Map과 함께 사용하여 입력 받기
    - # a, b 를 한 줄에 입력받는 경우 a, b = map(int, input().split())
  - 동시에 변해야하는 객체에 효율적으로 표현 가능
    - # Swap a, b = b, a
- Dictionary
  - Keys()나 values()를 사용하여 효율적으로 필요한 데이터만 추출
  - 반복문
  - 문자열 자체를 index로 사용할 경우
- Set
  - 중복 체크 가능
  - 합집합, 여집합, 차집합 등 집합 연산 가능 (단, 시간복잡도가 큼)

취업

명확한 분야 선택
- 웹, 앱, 4차산업관련(IOT, 인공지능, 음성처리 등)
  - 웹, 앱 쪽은 학원
    - JavaScript
    - node.js 서버
    - typeScript
    - vue
    - react
  - 코테 준비는 사용 언어를 선택하고 코딩스터디
    - 책으로 이론 병행하면서(세미나처럼) 문제도 풀고 풀이를 칠판에 or 구두로 설명하는 스터디
  - 토이 프로젝트 스터디
- 백엔드
  - https://www.mindmeister.com/ko/530652609/_?fullscreen=1
  - https://okky.kr/article/467416
중소기업?
- 보통 유지보수 업무가 대다수
  - 어떤 업무를 하고, 사용 기술스택이 무엇인지 확인, 최신 기술일수록 배울 수 있는게 많아짐
교육
- 멀티캠퍼스
- KFQ

AI 역량검사

자기소개
지원동기
성격장단점
상황질문
- 나는 편의점에 걸어가고 싶은데 고등학생들이 담배를 사달라며 돈을 2배로 준다고 한다. 어떻게 하겠는가?
- 이성친구 집에 놀러갔는데 어머니께서 해주신 음식이 너무 맛이 없어서 못 먹을 정도였을 때 어떻게 할 것인가?
- 나는 음식점 주인이다. 그런데 고객이 음식을 반이나 먹은 상태에서 환불해달라고 할 때 어떻게 할 것인가?
- 나는 신입사원이다. 친구들과의 여행이 주말에 오래전부터 잡혀있었다. 그런데 상사가 주말에 프로젝트 때문에 출근을 하라고 한다. 어떻게 할 것인가?
- 친구들과의 모임이 잡혔다. 나는 친구와 함께 모임에 갔고, 나는 이 모임이 즐거웠는데 같이 간 친구가 자신은 너무 지루하다며 집에 가고싶다고 한다. 어떻게 할 것인가?
- 나는 신입사원이다. 상사가 과도한 업무를 주었다. 최대한 마감하려고 하지만 불가능할 것 같다. 이 때 상사에게 어떻게 말할 것인가?
- 나는 신입사원이다. 같이 입사한 동기의 태도가 매우 불량하다. 자꾸 나에게 일을 미루려고 한다. 그 일을 처리함에 있어서 문제는 없지만 자꾸 지속적으로 나에게 일을 미룬다. 이 때 어떻게 할 것인가?
- 나는 고속버스를 기다리고 있는데 갑자기 모르는 사람이 와서 지갑이 없는데 돈을 빌려달라고 한다. 어떻게 할 것인가?
- 나는 옷가게 주인이다. 환불을 하러 어떤 고객이 왔는데 옷을 입은 흔적이 보인다. 어떻게 하겠는가?
- 나는 은행에서 일을 하고 있다. 손님과 일을 하고 있는데 급하게 온 다른 손님이 정말 급한 일이 있으니 먼저 해결해 달라고 한다. 어떻게 하겠는가?
- 나는 신입사원이다. 상사가 A 방향에 대한 업무를 지시했는데 회의를 진행하면할수록 회사에 막대한 피해가 생길 것 같다. 팀장님께 어떻게 말할 것인가?
- 나는 친구와 함께 살고 있다. 그러나 친구가 전혀 청소를 하지 않는다. 이에 한 마디를 하려고 하는데 어떻게 말할 것인가?
- 나는 신입사원이다. 상사와의 회식이 있는데 상사가 회사의 공금을 사적으로 쓴다는 이야기를 했다. 어떻게 할 것인가?
- 친구들과의 모임에서 나를 빼고 모두가 여행을 다녀온 사실을 알게 되었다. 어떻게 하겠는가?
- 회의를 준비 끝에 PT를 완성했는데, 내가 준비한 자료 발표 직전에 잘못된 것을 발견했다. 어떻게 말할 것인가.
- 갑자기 경영환경이 어려워져 동기가 퇴사하려 한다. 이 때 어떻게 말할 것인가.
- 갑작스럽게 지방영업점으로 발령을 받았다. 너무 가기 싫다. 이 때 과장님께 어떻게 말할 것인가.
- 대학생이다. 부모님께서는 공무원을 준비하라고 하신다. 하지만 나는 가수가 되고 싶다. 어떻게 말하겠는가.
- 나는 오늘 이사를 했다. 근데 이삿짐 센터에서 냉장고를 놓고 갔다. 그래서 친구와 냉장고를 옮겼다. 이삿짐 센터에 뭐라고 말할 것인가.
- 나는 약국에서 아르바이트를 하고 있다. 약사가 부재중인데, 약사의 아들이 돈이 없다며 외상을 한다고 한다. 나는 어떻게 할 것인가.
- 가장 친한 친구가 중고거래사이트에서 사기를 쳤다고 자랑한다. 나는 어떻게 말할 것인가.
- 마음에 드는 이성과 비싼 레스토랑에서 소개팅을 하고 있다. 계산을 하려고 하는데 지갑을 두고 온 것을 알게 되었다. 어떻게 할 것인가.
- 상사가 100명 한테 고객만족도 조사를 하라고 하였다. 하지만 시간이 너무 부족하다. 끝낼 수 없을 것 같을 때 상사에게 어떻게 말 할 것인가.
- 평소에 친하지 않은 친구에게 연락이 와서, 교통사고 합의금 300만원을 빌려 달라고 한다. 친구에게 어떻게 말 할 것인가.
- 세 명이서 프로젝트를 진행하고 있는데, 한 명이 계속해서 무임승차를 하려고 한다. 뭐라고 말하겠는가.
- 교수님이 추천한 기업에 인턴으로 들어갔다. 반복적인 업무만 주어진다. 교수님이 어땠는가 물으면 어떻게 답 할 것인가.
- 공연 관람을 위해 1시간 넘게 기다리고 있는데, 내 앞으로 누군가 새치기를 했다. 어떻게 말하겠는가.
- 본인이 중고로 핸드폰을 팔았다. 근데 구매자가 액정이 깨져 있다며 환불을 요청한다. 어떻게 대처할 것인가.
- 너무나 몸이 아파 병가를 내고 출근하였더니, 3일 내로 끝내야 하는 프로젝트가 있다. 어떻게 대처할 것인가.
- 사수가 일을 줘서 처리하고 있는데, 팀장님이 일을 주며 먼저 처리하라고 한다. 뭐라고 말 할 것인가.

Part 1.
Part 2.

면접

1분 자기소개
- 목표 : 1분 자기소개가 끝난 후 나한테 추가적으로 질문이 들어오는 것(어그로)
- Point
  1. 진정성
  2. 특이 경험
  3. 어그로
- 작성 틀
  - 나는 ~한 사람입니다.
    - 나의 특징, 성격, 가치관, 주변의 평, 성격의 장단점, 특이 경험, 성공 경험
    - 나를 표현할 수 있는 단어 저는 매일 책을 읽는 OO입니다. 저는 국토대장정을 스스로 만든 OO입니다. 저는 무엇이든 하면 5년 이상 하는 끈기를 가진 OO입니다.
  - 나의 경험
    - 1) 경험 A,
    - 2) 경험 A, 경험 B,
    - 3) 경험 A, 지식 공부 B 상황 액션 결과에서 액션을 빼고 이야기해서 궁금증을 유발시켜라! 저는 카페 알바를 하면서 매출 20%를 올린 경험이 있습니다.
  - 진정성 강조하는 요약
    - 내가 이런 성공 경험을 할 수 있었던 것은 나의 캐릭터 때문이었어요로 요약 안녕하세요 저는 무엇이든 하면 5년 이상 하는 끈기를 가진 OO입니다. 성공 경험 + 제가 이런 성공을 만들 수 있었던 이유는요 어떤 특별한 혁신적인 아이디어나 전략적인 사고능력을 통해서 만든 것은 아닙니다. 작은 일이라도 한번 시작하면 끝을 보자 라는 마음으로 한번 시작한 것들을 꾸준히 해 나갔고, 그 결과 좋은 성과를 이루었다고 생각합니다. 제가 지원한 이 ~ 업무에 있어서도 대단한 혁신이나 아이디어를 통해서 개선할 것이 많으리라고 생각되진 않습니다. 하지만 한발 한발 꾸준히 해 나가는 것으로 제 성과를 증명해 보도록 하겠습니다.
  - 나의 포부
    - 내가 성공할 수 있었던 요인이 ~직무에서도 ~게 발휘될 것이다. 해당 역량이 그 직무에 어떻게 적용될 것인가.
- 다섯가지 주제
  1. 가치관
    - 나는 ~한 사람입니다.
      - 가치관
      - 가치관 - A 역량
    - 나의 경험
      - 경험 1~2개
      - 경험 1개, 지식공부 경험 1개
    - 진정성 강조하는 요약
      - 내 캐릭터와 경험 연결 원리 요약
    - 나의 포부
  2. 특색있는 경험
    - 나는 ~한 사람입니다.
    - 나의 경험
      - 경험 1~2개
      - 경험 1개, 지식공부 경험 1개
    - 꿈보다 해몽
      - 내 캐릭터와 경험 연결 원리 요약
    - 나의 포부
  3. 유사 경험
    - 나는 ~한 사람입니다.
    - 나의 경험
      - 유사 경험 1~2개(직무 or 산업)
    - 진정성 강조 요약
      - 내 캐릭터와 경험 연결 원리 요약
      - 텍스트나 영상으로 체득할 수 없는 부분 강조
    - 나의 포부
  4. Basic 역량
    - 나는 ~한 사람입니다.
    - 나의 경험
      - (성공) 경험 2개
    - 진정성 강조 요약
      - 내 캐릭터와 경험 연결 원리 요약
    - 나의 포부
  5. 지식 어필
    - 나는 ~한 사람입니다.
    - 나의 경험
      - 지식을 어떻게 적용해 봤다
      - 지식을 얻기 위한 나의 노력
    - 진정성 강조 요약
      - 내 캐릭터와 경험 연결 원리 요약
    - 나의 포부
Technical-Interview guidelines
기타
- AI 해커톤

reference
PS를 공부하는 방법
PS/CP 공부 유형 및 보완법
문제 풀이 연습
알고리즘 공부
알고리즘 공부 방법/순서
PS 시작하기
코딩테스트 문제 리스트와 연습 팁

기술면접

https://github.com/gyoogle/tech-interview-for-developer
https://goodgid.github.io/Prepared-for-Computer-Science/
https://github.com/JaeYeopHan/Interview_Question_for_Beginner

PS Study

PS(Problem Solving)

PS study 단계

코딩테스트(?)

코딩테스트 준비

Python

취업

AI 역량검사

면접

기술면접