nose딩

결과:

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

*  2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기

저번시간에 이어 또 다른 징검다리 문제.

이번엔,, 카카오,,,, 쏘 큩

*이분탐색 문제로, 여느 이분탐색과 같이 풀어준다.

mid는 우리가 찾고자 하는 값, 즉 징검다리를 건널 수 있는 사람의 수이다.

단지 여기서 사용되는 check 메소드는 징검다리를 건널 수 있는지 확인하는 메소드이다.

count가 연속된 0의 개수를 나타내기 떄문에, k보다 클 경우는 못 건너는 경우이므로 false를 리턴해준다.

회의 일자 : 

2021.08.10 21:00 ~ 24:00 

목표 : 

-  알고리즘 문제 해결 (프로그래머스) : 2019 카카오 개발자 겨울 인턴십 -> 징검다리 건너기

결과:

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

*  이분탐색 - 징검다리

처음 문제 이해 부터 오래 걸렸던 문제 ,,

예시가 이렇게 나와 있었는데,

저 각 바위 사이의 거리가 0부터 도착지점까지해서 정말 그 바위 사이 사이 거리였고,

거리의 최솟값은 각 바위 사이의 거리중 최솟값이었다.

사실 문제만 보고 이분탐색이 떠오르지 않았다.

하지만 이 제한사항이 그걸 나타낸다고 한다.

이분탐색의 특징이란,, 문제를 딱 봤을때 어려운 늑힘 && 10억이 나왔을 때 ,,

그러니 저 10억을 보고 이분탐색으로 해결 해야한다는 것을 캐치해야한다고 한다..

친구가 이런,, 알고리즘 꿀팁을,,주었다,, 감사합니다.

*

이분탐색의 기본은,, 정렬 이기에 먼저 정렬을 해준다.

또 여느 이분탐색 문제처럼 해결 !

left는 최적, right은 최악을 나타낸다. 따라서 이와 같이 설정!

mid는 중간값으로 찾으려는 값이고, 

지운바위를 체크하기 위해 count 이용 ! 

또한 prev는 이전바위를 나타낸다.

즉 rocks[i]에서 prev를 빼줌으로써 이전바위와의 거리를 측정하고

mid값보다 작으면 바위를 지우고, 그렇지 않으면 바위를 지우지 않은것이기 때문에 prev를 업데이트 해준다.

break문은 지운 바위의 수(count)가 n보다 크면 더이상 반복문 안 돌아도 되기때문에 종료하는 것이다.

count가 n보다 작게되면 덜 지운거기 때문에 left를 mid+1로!

그렇지 않으면 더 많이 지운거기 때문에 right을 mid-1로 설정 ! 

이러한 조건에 맞추어,

answer는 최솟값 중 가장 큰 값을 구하기 위해 저렇게 설정한다. 

회의 일자 : 

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 

목표 : 

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