[Section 2] 코딩 테스트 준비

현이·2023년 3월 21일
0

백엔드 부트캠프 TIL

목록 보기
20/37
post-thumbnail

사진은 퐁피두 센터에서 내려다본 파리 해지는 풍경 - 제일 행복했던 순간! 작품들 보다가 밖에 석양이 너무 예뻐서 뛰쳐나와서 구경했다. 피카소 칸딘스키 뒤샹 작품들을 두고 나올만큼 아름다웠던 🌇

오늘 너무 힘들었다... 어제 너무 힘들어서 오늘은 꼭 파이팅해서 해보자 다짐했는데 아침 도서관 오는 길부터 너무 험난했다ㅠㅠ 내일은 진짜 6시에 딱 일어나서 버스 더 일찍 타기!!! DP 문제가 너무 어려워서 결국은 레퍼런스 코드 보고 했다... 시간 초과로 못푸니까 이렇게 아쉬울 수가 없는데 DP 문제 점화식 못세우는건 맞으니까 곡 연습 많이 해서 끝내버리기!!!

마음에 드는 알바가 있어서 지원해볼까 생각중

용어 정리

알고리즘

  • 문제를 해결하는 최선의 선택
  • 문제 이해 -> 의사코드 작성 -> 코딩

의사 코드 (pseudo code)

  • 구체적으로 자연어로 작성!

시간 복잡도

  • Big-O 표기법
  • O(1) < O(log n) < O(n) < O(n^2) < O(2^n)



탐욕 알고리즘 (Greedy)

  • 당장 최적의 상황만 쫓아서 결론 도출
  • 전체적으로 봤을 때 최적의 상황은 x 근접 알고리즘

Algorithm with greedy Algorithm 코플릿 연습문제

코플릿 [DP] 금고를 털어라! 문제

내 코드

public class Solution { 
	public long ocean(int target, int[] type) {
    // TODO:
        Arrays.sort(type);
        long answer = 0;
        for (int j = target / type[type.length-1]; j >= 0; j--){
            if(type.length==1) return target%type[0]==0? 1 : 0;
            if (type[type.length-1]*j == target) {
                answer++;
                continue;
            }
            answer += ocean(target- j*type[type.length-1], Arrays.copyOfRange(type, 0, type.length-1));
        }
        return answer;
	} 
}

--> 예제는 답 나오나, 시간 초과로 통과 못함!
for 문 안에 재귀함수 돌리기 ~> 최악...

이럴때는 눈치껏 target최대 값 보고 배열 생성 후 DP 이용하기!
=> "만들 수 있는 모든 값을 배열에 만들어가며 저장 후 값 구하기"




구현 -시뮬레이션(Simulation)

  • 문제에서 모든 과정과 조건 제시 -> 그대로 구현하면 되는데 그 과정이 까다로움 (언어에 대한 이해도 높아야 함)
  • 조건 빠짐없이 처리



완전 탐색 알고리즘(Brute-Force Algorithm)

  • 무차별 대입 방법
  • 컴퓨터 성능만 믿고 일단 다해보는... -> 안좋음!!
  • e.g. 순차 검색, 문자열 매칭, 선택 정렬



이진 탐색 알고리즘(Binary Search Algorithm)

  • 업다운 게임 같은 원리
  • 정렬되어 있어야 구현 가능! && 배열에만 구현 가능

0개의 댓글