알고리즘 문제 질문입니다 고수님들 답변좀 부탁드려요 ㅎ
날애
질문 제목 : 알고리즘 문제 질문입니다 고수님들 답변좀 부탁드려요 ㅎ알고리즘 문제 질문입니다 고수님들 답변좀 부탁드려요 ㅎ질문 내용 :
문제내용:
만층의 건물에서 유리잔들 떨어뜨렸을때 유리잔이 안깨지는 층의 위치를 찾는 알고리즘인데요,,,,
어떤 알고리즘을 쓸때에 가장 적게 유리잔을 깨드리면서 유리잔이 안깨지는 층의 위치를 찾을 수이있을까요?
답변 부탁드려요 ㅎ
-
큰아
답변 감사합니다. ^^
-
드리
100층의 강화유리잔
-
비치나
수다님처럼 이진트리로 생각하시면 될것 같습니다. 단 이진트리가 잘 구성되어 있어야 겠죠
아래와 같은 모양으로요
5000
2500 7500
1250 3750 6250 8750
시간복잡도를 o(logn)
1
2
3
4
위와 같은 불균형 트리에서는
o(n)이 됩니다. -
든솔
이런 걸 알고리즘 문제라고 할 수 있나...? -_-
-
흡뜨다
ㅋㅋㅋㅋㅋ 명답변이네요
-
설희
1층부터 깨지지 않을까요 ?
-
흰추위
2진검색을 응용하면 됩니다.
-
지율
아무래도 낮은 곳에서 떨길때 잘 안깨지겠죠. 그렇다고 1층씩 올라가자니 넘 감질날 것 같구요
1층부터 시작하되 100층씩 건너뛰며 101, 201, 301, 401 식으로 검사하다
깨지는 층이 401에서 나오면 301과 401 사이를 다시 10층간격으로 302, 312, 322 식으로 검사후
332층에서 깨지면 322, 323, 324 식으로 1층 간격으로 다시금 검사하면 되지않을까요?
일단 시작 위치가 문제될뿐 나머지는 같은 방식으로 해야 할 것
| 번호 | 제 목 | 글쓴이 | 날짜 |
|---|---|---|---|
| 2700368 | if에 관해서 질문이요... | Orange | 2025-07-04 |
| 2700339 | 이거 결과값이 왜이런건지.. (4) | 그댸와나 | 2025-07-04 |
| 2700313 | 파일 읽어서 저장하는데 빈파일일 경우 문재가 발생하네요.. (2) | 크나 | 2025-07-03 |
| 2700287 | 구조체 동적할당 연습을 하는데 오류가 뜹니다...(해결) (3) | 아련나래 | 2025-07-03 |
| 2700264 | 문자와 숫자 동시에 입력??? | 글고운 | 2025-07-03 |
| 2700236 | txt파일로만 쓰고 읽게 하려면 어떻게 해야 하나요..?? (8) | 미국녀 | 2025-07-03 |
| 2700211 | 전위 연산자 (2) | 어른처럼 | 2025-07-02 |
| 2700183 | C에서 파일이름을 받고, 그 파일의 사이즈를 출력해줘야하는데 내용이 출력이 안되네요 ;ㅅ; | 피스케스 | 2025-07-02 |
| 2700150 | 꼭좀 도와주세요ㅠㅠㅠ | 호습다 | 2025-07-02 |
| 2700095 | 연산문제...질문... | 오빤테앵겨 | 2025-07-01 |
| 2700070 | while문 , 3의배수 출력하는 프로그램좀 짜주세욤. | 횃불 | 2025-07-01 |
| 2700041 | 초보인데요 ㅎ 배열안에 배열을 집어넣을수 있나요?? | 헛장사 | 2025-07-01 |
| 2700012 | 배열// (1) | 전갈자리 | 2025-07-01 |
| 2699895 | 무한루프에 빠집니다.!! 해결좀부탁드려요 (10) | 선아 | 2025-06-30 |
| 2699842 | 질문을 너무 많이 하네여.....죄송.... (2) | 해님꽃 | 2025-06-29 |
| 2699816 | 오류 질문입니다.. (1) | 해비치 | 2025-06-29 |
| 2699763 | 질문입니다 ! 꼭 좀 도와주세요ㅠㅠ (2) | 미라 | 2025-06-28 |
| 2699555 | c언어 다항식을 입력을 했는데 왜 출력이 안될까요? | 피스케스 | 2025-06-27 |
| 2699528 | C언어 포인터연산 질문입니다. (3) | 안녕나야 | 2025-06-26 |
| 2699476 | 끌어올림;;달력 짜봤는데요 이 소스 줄일 수 있나요? - 스샷첨부 (2) | 클라우드 | 2025-06-26 |