메모 면접 문제 4.7 순서 정하기 프로젝트의 리스트와 프로젝트들 간의 종속 관계(즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두 번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻)가 주어졌을 때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다. 4.8 첫 번째 공통 조상 이진 트리에서 노드 두 개가 주어졌을 때 이 두 노드의 첫 번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성하라. 자료구조내에 추가로 노드를 저장해 두면 안 된다. 반드시 이진 탐색 트리일 필요는 없다. 4.9 BST 수열 배열의 원소를 왼쪽에서부터 차례로 트리에 삽임함으로써 이진 탐색 트리를 생성할 수 있다. 이진 탐색 트리 안에서 원소가 중복되지 않는다고 할 때, ..
메모 면접 문제 4.1 노드 사이의 경로 방향 그래프가 주어졌을 때 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성하라. 4.2 최소 트리 오름차순으로 정렬된 배열이 있따. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을 때 높이가 최소가 되는 이진 탐색 트리를 만드는 알고리즘을 작성하라. 4.3 깊이의 리스트 이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야 한다. 4.4 균형 확인 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다...
메모 그래프 트리는 그래프의 한 종류임. 모든 그래프가 트리는 아님. 트리는 사이클이 없는 하나의 연결 그래프임. 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 것임. 그래프에는 방향성이 있을 수도 있고 없을 수도 있음. 그래프에는 여러 개의 고립된 부분 그래프(isolated subgraphs)로 구성될 수 있음. 모든 정점 쌍간에 경로가 존재하는 그래프는 ‘연결 그래프’라고 부름. 그래프에는 사이클이 존재할 수도 있고, 존재하지 않을 수도 있음. 사이클이 없는 그래프는 ‘비순환 그래프’(acyclic graph) 라고 부름. 프로그래밍으로 그래프를 표현할 때 일반적으로 다음 두 가지 방법을 사용함. 인접 리스트 (adjacency list) 그래프를 표현하는 가장 일반적인 방법 모든 정점..
메모 04 트리와 그래프 트리에서 탐색(search) 하는 것은 배열이나 연결리스트처럼 선형으로 구성된 자료구조에서 탐색하는 것보다 훨씬 까다로움. 최악의 수행 시간과 평균적 수행 시간이 매우 크게 바뀔 수 있어서, 알고리즘을 살펴볼 때, 두 가지 측면 모두를 반드시 따져봐야 함. 트리와 그래프를 밑바닥부터 능숙하게 구현할 수 있는 능력을 갖추면 분명히 도움이 될 것임. 트리의 종류 트리를 이해하기 가장 좋은 방법은 재귀적 설명법을 사용하는 것임. 트리는 노드로 이루어진 자료구조임. 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖고 있다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의됨. 트리에는 사이클이 존재할 수 없음. 노드들은 특정 순서로..
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120808 문제 풀이 1. 유클리드 호제법이 생각나지 않아서 생각나는 대로 품. class Solution { public int[] solution(int numer1, int denom1, int numer2, int denom2) { int[] answer = {}; int num = numer1 * denom2 + numer2 * denom1; int den = denom1 * denom2; int minVal = Math.min(num, den); int i = 1; while (i 0; i--) { if (num % i == 0 && den % i == 0) { num /= ..
메모 면접 문제 3.3 접시 무더기 접시 무더기를 생각해 보자. 접시를 너무 높이 쌓으면 무너져 내릴 것이다. 따라서 현실에서는 접시를 쌓다가 무더기가 어느 정도 높아지면 새로운 무더기를 만든다. 이것을 흉내 내는 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다(다시 말해, pop()은 정확히 하나의 스택이 있을 때와 동일한 값을 반환해야 한다). 힌트 각 부분 스택의 크기를 알고 있어야 한다. 스택이 꽉 차면 새로운 스택을 만들어야 한다. 특정 부분 스택엑서 원..
메모 03 스택과 큐 스택 말 그대로 데이터를 쌓아 올린다(stack)는 의미 LIFO(Last-In-First-Out)으로 자료를 배열함. pop() : 스택에서 가장 위에 있는 항목을 제거 push(item) : item 하나를 스택의 가장 윗 부분에 추가 peek() : 스택의 가장 위에 있는 항목을 반환 isEmpty() : 스택이 비어있을 경우 true 반환 i 번째 항목에 상수 시간 접근이 불가능 단, 데이터 추가, 삭제는 상수 시간에 가능 배열처럼 원소를 하나씩 옆으로 밀어줄 필요가 없음. 같은 방향에서 아이템을 추가하고 삭제한다는 조건하에 연결리스트로 구현할 수 있음. public class MyStack { private static class StackNode { private T da..
면접 문제 2.3 중간 노드 삭제 단방향 연결리스트가 주어졌을 때 중간(정확히 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다.)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다. 예제 입력 : 연결리스트 a → b → c → d → e 에서 노드 c 결과 : 아무것도 반환할 필요는 없지만, 결과로 연결리스트 a → b → d → e가 되어 있어야 한다. 힌트 리스트 1 → 5 → 9 → 12를 그려보자. 9를 지우면 1 → 5 → 12가 된다. 9 노드에만 접근할 수 있다. 정답처럼 보이게 만들 수 있겠는가? public class Solution { public static boolean deleteNode(LinkedListNode n) { if (n..
메모 02 연결리스트 차례로 연결된 노드를 표현해주는 자료구조임. 단방향, 양방향이 있음. 연결리스트는 배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없음. 연결리스트의 장점은 시작 지점에 아이템을 추가하거나, 삭제하는 연산을 상수 시간에 할 수 있음. 연결리스트 만들기 class Node { Node next = null; int data; public Node(int d) { data = d; } void appendToTail(int d) { Node end = new Node(d); Node n = this; while (n.next != null) { n = n.next; } n.next = end; } } 이 코드는 LinkedList 자료구조를 사용하지 않음. 연결리스트에 접근할 때 he..
메모 면접 문제 1.4 회문 순열 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다. public class Solution { public static void main(String[] args) { String pali = "Rats live on no evil star"; System.out.println(isPermutationPalindrome(pali)); } public static boolean isPermutationPalindrome(String s) { Map characterInteg..
요약 면접 문제 배열과 문자열 해시 테이블 구현을 위해 연결리스트와 해시 코드 함수가 필요함. 충돌을 고려해야 함. ArrayList와 가변 크기 배열 적 가변 크기 기능이 내재되어있는 배열과 비슷한 자료구조를 원할 때 보통 ArrayList 를 사용함. 상환 입력 시간은 왜 O(1)이 되는가 배열 복제가 자주 일어나지 않기 때문 StringBuilder 필요한 경우에만 문자열을 복제함. 면접 문제 메모 9. 면접 문제 www.CrackingTheCodingInterview.com 에서 전체 해법을 다운 받을 수 있음. 01. 배열과 문자열 배열이나 문자열에 대한 문제들은 서로 대체 가능함. 해시 테이블 효율적인 탐색을 위한 자료구조로서 키를 값에 대응시킴. 간단한 해시테이블을 구현하기 위해선 연결리스트..
요약 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)) 오답에 대한 대처법 알고 있던 문제가 면접에 나왔을 때 면접용으로 ‘완벽한’ 언어 널리 사용되는 언어 언어 가독성 잠재적인 문제점 언어가 얼마나 장황한지 사용하기 쉬운 언어 어떤 코드가 좋아 보이나 포기하지 말라 합격한 뒤에 합격 또는 거절 통지에 대처하는 요령 입사 결정 기한과 연장 입사 제안 거절 탈락 통보 대처 입사 제안 평가 재정 관련 사항 경력 개발 회사의 안전성 행복의 척도 연봉 협상 입사 후 튼튼한 관계 수립 원하는 것을 요구하라 꾸준히 면접을 보라 메모 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)) 어떤 문제를 푸는 데 상상할 수 있는 모든 해법 중 수행 시간이 가장 빠른..