16. 중간 난이도 연습문제 16.16 부분 정렬 정수 배열이 주어졌을 떄, m부터 n까지의 원소를 정렬하기만 하면 배열 전체가 정렬되는 인덱스 m과 n을 찾으라. 단, n - m을 최소화하라 (다시 말해, 그런 순열 중 가장 짧은 것을 찾으면 된다). 16.17 연속 수열 정수 배열이 주어졌을 때 연속한 합이 가장 큰 수열을 찾고 그 합을 반환하라. 16.18 패턴 매칭 패턴 문자열과 일반 문자열 두 개가 주어져있다. a와 b로 이루어진 패턴 문자열은 일반 문자열을 표ㅕ현하는 역할을 한다. 예를 들어 catcatgocatgo는 aabab 패턴과 일치한다(여기서 a는 cat이 되고, b는 go가 된다). 이 문자열은 a, ab, b 패턴과도 일치한다. 일반 문자열이 패턴 문자열과 일치하는지 판단하는 메서..
16. 중간 난이도 연습문제 16.13 정사각형 절반으로 나누기 2차원 평면 위에 정사각형 두 개가 주어졌을 떄, 이들을 절반으로 가르는 직선 하나를 찾으라. 정사각형은 x축에 평행하다고 가정해도 좋다. 16.14 최고의 직선 2차원 평면 위에 점이 여러 개 찍혀 있을 때 가장 많은 수의 점을 동시에 지나는 직선을 구하라 16.15 Master Mind Master Mind 게임의 룰은 다음과 같다. 빨간색(R), 노란색(Y), 초록색(G), 파란색(B) 공이 네 개의 구멍에 하나씩 들어 있다. 예를 들어 RGGB는 각 구멍에 차례대로 빨간색, 초록색, 초록색, 파란색 공이 들어 있다는 뜻이다. 여러분은 공의 색깔을 차례대로 맞춰야 한다. 구멍에 들어 있는 공의 색깔을 정확히 맞췄다면 ‘히트’를 얻게 되..
16. 중간 난이도 연습문제 16.10 살아 있는 사람 사람의 태어난 연도와 사망한 연도가 리스트로 주어졌을 때, 가장 많은 사람이 동시에 살았던 연도를 찾는 메서드를 작성하라. 모든 사람이 1900년도에서 2000년도에 살아 있었다고 봐야 한다. 예를들어 어떤 사람이 1908년에 태어나서 1909년에 사망했다면 이 사람은 1908년과 1909년 모두에 삶을 살았던 사람이 된다. 16.11 다이빙 보드 다량의 널빤지를 이어 붙여서 다이빙 보드를 만들려고 한다. 널빤지는 길이가 긴 것과 짧은 것 두 가지 종류가 있는데, 정확히 K개의 널빤지를 사용해서 다이빙 보드를 만들어야 한다. 가능한 다이빙 보드의 길이를 모두 구하는 메서드를 작성하라. 16.12 XML 인코딩 XML은 너무 장황하게 표현된 경우가 많..
16. 중간 난이도 연습문제 16.7 최대 숫자 주어진 두 수의 최댓값을 찾는 메서드를 작성하라. 단, if-else나 비교 연산자는 사용할 수 없다. 16.8 정수를 영어로 정수가 주어졌을 때 이 숫자를 영어 구문으로 표현해주는 프로그램을 작성하라. 예를 들어 1,000이 입력되면 ‘One Thousand’, 234가 입력되면 ‘Two Hundred Thirty Four’를 출력한다. 16.9 연산자 덧셈 연산자만을 사용하여 정수에 대한 곱셈, 뺄셈, 나눗셈 연산을 수행하는 메서드를 작성하라. 연산에 대한 결과는 항상 정수가 되어야 한다.
16. 중간 난이도 연습문제 16.4 틱-택-토의 승자 틱-택-토(tic-tac-toe) 게임의 승자를 알아내는 알고리즘을 설계하라. 16.5 계승(factorial)의 0 n!의 계싼 결과에서 마지막에 붙은 연속된 0의 개수를 계산하는 알고리즘을 작성하라. 16.6 최소의 차이 두 개의 정수 배열이 주어져 있다. 각 배열에서 숫자를 하나씩 선택했을 때 두 숫자의 차이(절댓값)가 최소인 값을 출력하라.
16. 중간 난이도 연습문제 16.1 숫자 교환 임시 변수를 사용하지 않고 숫자를 교환(swap)하는 함수를 작성하라. 16.2 단어 출현 빈도 어떤 책에 나타난 단어의 출현 빈도를 계싼하는 메서드를 설계하라. 이 알고리즘을 여러 번 수행해야 한다면 어떻게 해야 할까? 16.3 교차점 시작점과 끝점으로 이루어진 선분 두 개가 주어질 때, 이 둘의 교차점을 찾는 프로그램을 작성하라.
15. 스레드와 락 스레드로 알고리즘을 구현하라는 문제를 출제하는 일은 흔하지 않음. 하지만 스레드, 특히 교착상태(deadlock)에 대한 일반적 이해도를 평가하기 위한문제느 어떤 회사에서도 상대적으로 자주 출제하는 편임. 자바의 스레드 자바의 모든 스레드는 java.lang.Thread 클래스 객체에 의해 생성되고 제어됨. 독립적인 응용 프로그램이 실행될 때, main() 메서드를 실행하기 위한 하나의 사용자 스레드(user thread)가 자동으로 만들어짐. 이를 주 스레드(main thread) 라고 함. 자바에서 스레드를 구현하는 방법은 2가지가 있음. java.lang.Runnable 인터페이스 구현하기 java.lang.Thread 클래스 상속받기 Runnable 인터페이스를 구현하는 방법 ..
14. 데이터베이스 SQL 질의문에는 수많은 변종이 있음. 여러분은 그 가운데 하나를 사용했을 것임. SQL 문법과 그 변종들 묵시점(implicit) JOIN과 명시적(explicit) JOIN은 둘다 동등함. 어느 쪽을 사용할 것이냐는 개인 취향의 문제임. 비정규화 vs. 정규화 데이터베이스 정규화 데이터베이스는 중복을 최소화하도록 설계된 데이터베이스임. 대신 상당수의 일상적 질의를 처리하기 위해 JOIN을 많이 하게 되는 단점이 있음. 비정규화 데이터베이스는 읽는 시간을 최적화하도록 설계된 데이터베이스임. 대신 데이터베이스에 데이터를 중복해서 저장할 수 있음. 소규모 데이터베이스 설계 면접장에서 데이터베이스를 설계해 보라는 요청을 받을 수 있음. 1단계 : 모호성 처리 데이터베이스에 관계뙨 문제는 ..
12. C와 C++ 좋은 면접관은 지원자에게 익숙하지 않은 언어로 코딩하라고 요구하지 않음. 만약 C++로 코딩해 보라는 요구를 받았다면, 이력서에 C++를 적어놨기 때문임. API를 모두 기억하지 못해도 괜찮지만, 관련된 문제를 쉽게 풀 수 있도록 기본적인 C++ 문법은 공부해 둘 것을 추천함. 클래스와 상속 C++ 클래스는 다른 객체 지향 언어의 클래스와 비슷한 특성을 가짐. C++에서 모든 데이터 멤버와 메서드는 기본적으로 private 임. public 키워드를 사용하여 그 값을 변경할 수 있음. 생성자와 소멸자 생성자 : 객체가 생성되면 자동으로 호출됨. 소멸자 : 객체가 소멸될 때 자동으로 호출됨. 기본값 함수 선언 시, 기본값(default values)을 명시할 수 있음. 반드시 함수 선언..
11. 테스팅 테스팅과 관련된 질문들은 보통 다음 네 가지 범주 중 하나에 속함. 실생활에서 접하는 객체를 테스트하라 소프트웨어 하나를 테스트하라. 주어진 함수에 대한 테스트 코드를 작성하라. 발생한 이슈에 대한 해결책을 찾아내라. 입력 형식이 깔끔하다거나, 사용자가 예측 가능한 행동만 할 것이라고 가정하면 안됨. 아주 이상한 방식으로 시스템이 사용될 수 있으니 그에 대비해야 함. 면접관이 평가하는 것 큰 그림을 이해하고 있는가 테스트케이스 간의 우선순위를 적절히 매길 수 있는가? 퍼즐 조각을 제대로 맞추는 방법을 아는가 소프트웨어가 어떻게 동작하는지 아는가 각 소프트웨어가 보다 더 큰 생태계의 일부로 어떻게 귀속되는지 이해하는가 조직화 문제에 구조적으로 접근하고 있는가 시스템을 구조적으로 잘 나누면 테..
면접 문제 10.5 드문드문 탐색 빈 문자열이 섞여 있는 정렬된 문자열 배열이 주어졌을 때, 특정 문자열의 위치를 찾는 메서드를 작성하라. 10.6 큰 파일 정렬 한 줄에 문자열 하나가 쓰여 있는 20GB짜리 파일이 있다고 하자. 이 파일을 정렬하려면 어떻게 해야 할지 설명하라. 10.7 빠트린 정수 음이 아닌 정수 40억개로 이루어진 입력 파일이 있다. 이 파일에 없는 정수를 생성하는 알고리즘을 작성하라. 단, 메모리는 1GB만 사용할 수 있다. 10.8 중복 찾기 1부터 N(≤32,000)까지의 숫자로 이루어진 배열이 있다. 배열엔 중복된 숫자가 나타날 수 있고, N이 무엇인지는 알 수 없다. 사용 가능한 메모리가 4KB일 때, 중복된 원소를 모두 출력하려면 어떻게 할 수 있을까? 10.9 정렬된 행..
메모 10. 정렬과 탐색 널리 사용되는 정렬 및 탐색 알고리즘을 완벽히 이해하는 건 굉장히 가치 있는 일임. 많은 정렬 및 탐색 문제는 잘 알려진 알고리즘들을 변용하여 출제됨. 여러 가지 정렬 알고리즘의 차이점을 잘 이해하고, 해당 상황에서 어떤 알고리즘이 어울릴지 살펴두는 것이 좋음. 널리 사용되는 정렬 알고리즘 아래 정리한 다섯 알고리즘 가운데, 병합 정렬(merge sort), 퀵 정렬(quick sort), 버킷 정렬(bucket sort)관련 문제가 가장 자주 출제됨. 버블 정렬(bubble sort) | 평균 및 최악 실행 시간 : O(n^2), 메모리 : O(1) 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복함. 이런 식으로 배..
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
