nose딩

회의 일자 : 

2021.08.03 21:00 ~ 24:00 

목표 : 

-  알고리즘 문제 해결 (프로그래머스) : 이분탐색_2

결과:

*이분 탐색(Binary Search)

-> 정렬되어 있는 배열에서 값을 찾으려 할 때,

탐색 범위를 절반씩 줄여가며 찾는 탐색 방법!

<프로그래머스 문제 풀기> 

*  이분탐색 - 입국심사

모든 사람이 심사를 받는데 걸리는 시간의 최소값 찾기!

우선 정렬을 해준다.

이후 left를 최적의시간, right을 최악의 시간으로 하여 이분탐색으로 찾는다.

따라서 while문의 조건은 left가 right보다 작거나 같을때 !

mid는 중간값으로 찾으려는 시간이 된다.

인원 체크를 하기 위해 sum을 이용 !

for문을 돌려 심사관이 각각 할 수 있는 인원을 더해나간다. 그게 곧 sum.

sum이 n보다 작게되면 인원이 미달인 것으로 left를 mid + 1로 설정 !

그렇지 않으면 인원이 넘치는 경우이기때문에 right을 mid-1로 설정한다. 그후 mid 값을 answer로!

최적의 해, 즉 최소값을 찾기 위한 것이기 때문에 종료조건(left가 right보다 작거나 같지 않을 경우) 까지 반복해서 찾는다.

회의 일자 : 

2021.07.27 21:07 ~ 24:00 

목표 : 

-  알고리즘 문제 해결 (프로그래머스) : 이분탐색

결과:

<프로그래머스 문제 풀기> 

*  완전탐색 - 소수 찾기

구글신의 도움을 받아 ,,, 완벽한 다른 위대하신 분의 코드 ,, 를 참고했다(가져왔다). ^^

그냥 외우기로 했다.

이 부분은 어쩔 수 없는 거 같아요.

시간 단축에 직빵인 StringBuilder, ,,

만들 수 있는 모든 숫자를 만들어 Set에 넣은 후,

Set을 검사해 소수일 때 answer를 증가시키는 방법이다.

흔한,,dfs ,, if문을 통해 즉, sb(StringBuilder)의 길이가 depth랑 같아지면 set에 넣어주고 리턴해준다.

true이면 continue를 통해 패스하고, 아니면 true로 바꾼후 sb에 append 후 dfs ,, 후 delete를 통해 뒤에 한글자씩 제거하고 false로 ,,,

사실,,dfs,, 외우기로 했다,,,  ^ ^

소수를 판별하는 함수,, 이것도 외우기로 다짐 ^^ 오늘의 나는 외웠다 이 코드 ,,

*  완전탐색 - 카펫

입출력 예를 보고 처음에 든 생각은 x랑 y랑 최대한 가까운 숫자로 만들어야겠다는 생각이 들었다.

따라서 brown과 yellow를 더한 값을 x와 y의 곱으로 표현하되, 이 둘은 x >=y이며 차이는 최대한 적게! 만들고자 했다.

하지만 테스트케이스에서 세 개를 계속 틀려서 헤맸었는데,  노란색, 갈색 개수가 맞는지 확인해보라는 친구의 힌트를 통해 조건에 넣어줬다.

brown은 yellow의 테두리에 생기기 때문에, 전체를 x, y라 했을 때 yellow는 x-2, y-2가 될 것이다.

따라서 이 값이 yellow가 되야한다는 조건도 넣어줬다.

brown은 yellow가 맞게되면 일치할 것이기 때문에 굳이 넣어주지 않았다. 

헌데, 구글에서 다른 풀이들을 살펴보니 보통은 이렇게 풀지는,,,않더라구요 ,, ㅎ ,,

회의 일자 : 

2021.07.20 21:00 ~ 24:00 

목표 : 

-  알고리즘 문제 해결 (프로그래머스) : 완전탐색

결과:

<프로그래머스 문제 풀기> 

*  탐욕법(Greedy) - 큰 수 만들기

pick은 자리 수를 나타내는데, 이 중에 몇 개를 고른다! 느낌으로 진행하였다. (pick인 이유 ,,)

앞에서 부터 최대값을 구하는데 이 때 고른 최대값 뒤에는 적어도 pick 개는 존재해야한다.

따라서,  number.length()-pick 을 통해 최대 인덱스를 설정해주었다. 

(사실 이 부분에서 제일 헤맸는데 지금 생각해보면 이건 진짜 수학문제가 아닐까? 잃어버린 내 수학적 머리 찾아요,,)

char 형 같은 경우 '0'을 빼주면 int 형 ,, , ,,,,

하지만 다른 사람들을 보니 굳이 저렇게 하지않고 char 형 그대로 max를 구하는 경우도 많던데,

미처 생각하지 못한 부분이었다.

고른 최대값을 stringBuilder에 append 해주면,, 된다,,

maxindex를 증가시켜주는 이유는 그 다음 인덱스부터 진행하기 위해서이다.

또한 시간 단축을 위해 StringBuilder를 사용하였다.

*  탐욕법(Greedy) - 구명보트

우선 Arrays.sort()를 통해 정렬을 진행한다.

따라서 처음 min은 첫번째값, max 값은 마지막 값이 된다.

min이 max보다 작아질 때 까지 다음은 반복되게 된다.

최소와 최대의 합이 limit보다 작거나 같은 경우에는 min값을 증가시킨다.  

또한 반복문의 매 경우 answer는 증가시키고 max를 감소시킨다.

즉, 합이 limit보다 작거나 같은 경우에는 보트에 두명을 태우는 경우이고

그렇지 않은 경우에는 보트에 한명만 태우는 경우가 된다.(라고 이해하였다^^.)

회의 일자 : 

2021.07.13 21:00 ~ 24:00 

목표 : 

-  알고리즘 문제 해결 (프로그래머스) : 탐욕법

결과:

*  탐욕법(Greedy)

: 각 단계에서 가장 최선의 선택을 하는 알고리즘

=> 따라서 최적의 해를 보장할 수 없을 때도 많음!

(하지만 코딩테스트에서의 문제는 최적의 해가 종합적으로도 최적의 값이 되도록 출제됨)

ex) 활동 선택 문제, 거스름돈 문제

<프로그래머스 문제 풀기> 

*  탐욕법(Greedy) - 체육복

탐욕법에서 체육복 문제를 해결하였다.

먼저 n+1 크기의 all 이라는 배열을 만들어주었다. 모든 사람에 대한 배열이다.

편의를 위해 크기를 n+1 로 잡고, 인덱스 0은 쓰지않는 것으로 하기로 했다.

먼저 reserve, 즉 체육복 여유분을 가지고 있는 사람 (빌려줄 수 있는 사람)을 값을 1 증가시켜 all 배열에 표시한다. 

그 후 lost, 잃어버린 사람을 체크하여 값 1을 감소시킨다.

그렇게 되면, 빌려줄 수 있는 사람은 1의 값을 가지고 있을 것이고, 잃어버린 사람은 1씩 감소될 것이고, 나머지는 다 0으로 들어갈 것이다.

비교적 낮은 레벨에서 시간을 많이 소모한 것 같다.

오랜만에 문제를 푸는 것도 있고, 그동안 공부를 안해온 거에 대한 자기 반성의 시간도 가졌다.

다음 모각코 회차에서는 더 발전된 모습으로 나아가고자 한다.