본문 바로가기

Problem Solving/코딩 인터뷰 완전분석

비트 뒤집기 어떤 정수가 주어졌을때 이 정수의 비트 하나를 0에서 1로 바꿀 수 있다. 이때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하라. 1) 정수 20이 주어짐 10100 2) 길이 3 출력 3) 풀이 순서 1. STEP - ArrayList에 0과1의 길이를 오른쪽 부터 0의 길이 부터 번갈아 리스트에 저장 [ 2,1,1,1,27 ] 10100 기본적인 & 연산자와 쉬프트 연산자 이용 카운터값을 리스트에 저장 2. STEP 리스트에서 가장 긴 길이를 갱신해가며 반환 [ 2,1,1,1,27 ] 0을 기준으로 1로 바꿔야 하기 때문에 리스트의 인덱스 0,2,4번째의 짝수 순으로 판단 반복
2진수를 문자열로 0.25와 같이 0과 1사이의 실수가 double 타입으로 주어 졌을때, 그 값을 2진수 형태로 출력하는 코드를 작성하라. 길이가 32이하인 문자열로 2진수로 정확하게 표현할 수 없다면 ERROR을 출력하라. 1) 2.25를 2진수로 바꿔보자 0.25 * 2 = 0.50.5 * 2 = 1.0 2) 0과 1사이의 실수 0.25를 2진수 문자열로 출력해보자 3) 출력결과 : .01
4.6 후속자 이진 탐색 트리에서 주어진 노드의 다음 노드를 찾는 알고리즘(중위 순회)을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자 중위 순회 : 왼쪽, 현재, 오른쪽 순
4.5 BTS 검증 문제 - 주어진 이진 트리가 이진 탐색 트리인지 확인하는 함수를 작성하라 left.data
4.4 균형 확인 문제: 이진트리가 균형이 잡혀있는지 확인하는 함수를 작성하라. 0) 균형 잡힌 트리란? 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다. 1) 풀이 핵심 - 재귀사용 2) 개선 전 - O(N log N)루트부터 시작해서 높이를 구한후 균형 판단하고다시 반복적으로 루트 아래로 내려가면서 균형판단 3) 개선 후 - O(N)루트노두의 두서브 트리의 높이의 차를 한번만 구해오면서중간에 균형 판단 4) 공통점 - (최악의경우)균형판단의 횟수는 같음 5) 차이점 - 높이를 한번 구하냐 vs 높이를 계속 구하냐
루프 발견 구현
루프 발견 2.8 문제 - 루프 발견 순환 연결리스트가 주어졌을때, 순환되는 부분의 첫째 노드를 반환 하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는 변질된 방식 의 연결리스트를 의미한다. 입력: A > B > C > D >E> C (앞에 나온 C와 같음) // 입력 0 > 1 > 2 > 3> 4> 5> 6> 7> 8> 9> 10 > 3 출력 : C // 출력 3 문제 해결 방법 1. 연결리스트에서 순환 구조의 유무 검사 -탐색 속도가 다른 2개의 포인터를 이용. (RUNNER 기법) -SLOW: P만큼 나아갈때 1칸 -FAST: 2P만큼 나아간다 2칸 -이용해서 만나면 순환구조가 있다고 볼 수 있다. -루프가 아닌부분의 크기를 K 라고..

티스토리툴바