PS_TRAINING

알고리즘 PS 레포

• 프로그래머스, BOJ의 알고리즘 문제풀이 레포지토리
• 주 사용언어 : 파이썬, JS

📌 알고리즘 공부 정리 가이드

• 💾알고리즘 문제 풀이 블로그

📌 코테대비 마인드셋

1️⃣ 내가 공부한 것을 최대한 티내는 것이 본인에게 유리하다.

• 잘하라는 것이 아니다. 최댛나 공유하고 피드백 많이 받자.
• 자신이 정리한걸 보고 공부하는 것보다 정리가 잘되는 경우는 없다.

2️⃣ 질문하기 두려운 것이 아니다. 사실 귀찮은 것이다.

• 내가 무의식적으로 알고 있는 정보가 없는지 고민하고, 필요시 질문에 이를 추가한다.
• 자신이 이미 시도해본것들을 질문자에게 알린다.(중복답변 방지)
• 자신이 생각했던 부분과 다른 부분은 생각한 부분과 실제 부분을 정리한다.
• 질문을 질문답게 하는 것은 답변자에 대한 최소한의 배려이다.

3️⃣ 예상한대로 모든 일이 될 수는 없다. 그래도 계획은 필요하다.

4️⃣ 내가 기준이 돼야한다.

📌 PS 일지 작성법

• 양식은 보기좋게 작성하면 된다. 하지만 꼭 들어가야 하는 것들이 있다.
• 결과만 들어가는 것은 안되고, 과정이 보여야한다.

1️⃣ 문제를 요약하여 작성

• 2~3 문장으로 요약
• 문제 요약시 입출력에 대한 설명을 포함

2️⃣ 문제를 풀다가 막힌 경우

• 현재 시도하고 있는 방법과 그 근거를 작성
• 다른 방법으로 전환한 경우, 기존 방법에서 전환한 근거를 작성

3️⃣ 문제를 푼 경우

• 사용한 자료구조 및 알고리즘과 시간복잡도를 작성
• 푸는 과정에서 코드 오류가 발생한 경우, 따로 정리
• 문제의 함정이나, Key Point가 있다면 따로 정리

📌 공부 계획 짜보기

1️⃣ 인간은 기계가 아니다. Daily 계획은 성공률이 낮음.

• 월이나 분기별로 목표를 세우고 진행하는게 좋음
• 한번에 완벽한 계획은 불가능하니, 월마다 피드백을 하면서 맞게 반영하는게 좋다.

2️⃣ 적어도 한달에 한번은 실전연습을 해보자

• 현재 자신의 상태를 체크하고, 필요시 계획에 반영
• 시간배분 및 실전감각을 기를 수 있음

3️⃣ 문제 푸는 목표를 세울 때, 각 문제당 투자할 수 있는 시간을 정한다. (기간 내에 성과를 내야하므로 효율성이 중요)

4️⃣ 목표는 많은 사람에게 공유가 될수록 좋다.

📌 질문하는법

1️⃣ 답변자가 질문을 명확히 이해하고 답변을 달기 편하게 작성한다.

• 제목은 명확하게 작성
• 중요한 내용은 서두에 작성
• 코드 및 오류내용은 이미지로 올리지 않는다.

2️⃣ 질문은 명확하고 신뢰있게 하자.

• 비문을 되도록 사용하지 않고 완벽한 문장으로 깔끔하게 질문하자.
• 내 질문이 읽기 쉬운지 속으로 읽어보자.
• 내가 답변자에게 얻고자 하는 바가 무엇인지 명확하게 다시 한번 짧은 문장으로 정리한다.
• 이미 시도해봤던 것들은 반드시 작성한다.

3️⃣ 충분히 감사를 표시하고, 답변은 삭제하지 않는다.

• 답변자에 대한 기본적인 예의를 지키고, 원만한 관계가 유지되는게 유리하다.
• 다른 사람이 동일한 질문을 하는 경우가 많기 떄문에, 절대 삭제하지 않는다.
• 답변자와 커뮤니케이션 한 부분을 질문 밑에 요약해주면 굉장히 좋다.

📌 알고리즘 With Keyword

• 최적해 : DFS 제외, 그리디 제외, BFS를 충분히 고려해볼것
• 정렬된 상태의 데이터 : 이진탐색, 파라메트릭 서치 고려
• 삽입삭제가 빈번하게 일어남 : 힙 고려
• 최단 경로 : 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘 고려

📌 입력값 With Keyword

• 데이터 1000만개 이상 : 복잡도 NlogN 이상 알고리즘은 답이 될 수 없음.
• 데이터 10만개 이상 : 복잡도 N^2 이상 알고리즘은 답이 될 수 없음
• 데이터 1000개 이하 : 브루트포스(완전탐색) 고려할만함
• 데이터 양은 많지 않으나, 데이터간 간격이 큰 경우 : 데이터 값을 인덱스로 사용하면 Memory Exception 가능, 구조체로 표현 고려
• 주어진 정보 중 정형화하기 어렵고 데이터가 50개 미만인 경우, 하드코딩을 통해 데이터를 만들어 놓는게 해법일 수 있음.

📌 문제 풀이 팁

1. 최적화가 안될 것 같으면, 일단 정확도를 먼저 고려하고 최적화는 나중에 고민할것
2. 예외처리 부분은 기본 동작 부분과 분리해서 구현
3. 모듈화를 많이하면, 디버깅이 굉장히 유리함
4. 로그도 좋지만 되도록이면 breakpoint를 통한 디버깅이 유리함

📌 성공적인 디버깅을 위한 팁

• 코딩테스트 문제는 요구사항 분석 - 설계 - 구현 단계로 이루어지는데, 최대한 앞단계에서 디버깅을 진행할 수록 비용이 적게 든다.
• 즉 구현에 앞서 품질을 최대한 높이는 것이 중요하다.

1. 요구사항 분석시 애매모호한 사항과 예외 사항은 반드시 TC를 생성해서 정리한다.
2. 설계시 의사코드 작성 완료 후, 이를 기준으로 작성한 TC를 수행, 전부 완료될 때까지 의사코드 수정 반복
3. 구현시 각 모듈당 역할은 하나씩 수행하도록 함, 해당 모듈 수정시 최대한 기타 모듈에 대한 의존성이 적어야 함.