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) 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복함. 이런 식으로 배..
메모 9. 시스템 설계 및 규모 확장성 규모 확장성(scalability)은 가장 쉬운 종류의 문제임. 이런 류의 문제들은’마술’ 같은 것이 있지 않고, 단순히 여러분이 실제 세계에서 어떻게 행동할지를 보기 위해 설계된 문제들임. 이런 문제를 풀 떄는 실제 일을 하듯이 하면 됨. 질문을 하고, 면접관을 끌어들여라. 장단점을 토론하라. 시스템 설계는 좋은 해법과 나쁜 해법은 있지만 완벽한 해법은 없음. 문제를 다루는 방법 소통하라. 처음에는 포괄적으로 접근하라. 화이트보드를 사용하라. 면접관이 우려하는 부분을 인정하라. 가정을 할 때 주의하라. 잘못된 가정은 문제를 완전히 다르게 바꿔 버릴 수 있기 때문 여러분이 생각하는 가정을 명확히 언급하라. 필요하다면 어립잡아 보라. 뛰어들라. 이런 문제들은 최고의 ..
면접 문제 8.9 괄호 n 쌍의 괄호로 만들 수 있는 모든 합당한(괄호가 적절히 열리고 닫힌) 조합을 출력하는 알고리즘을 구현하라. 8.10 영역 칠하기 이미지 편집 프로그램에서 흔히 쓰이는 ‘영역 칠하기(paint fill)’ 함수를 구현하라. 영역 칠하기 함수는 화면(색이 칠해진 이차원 배열)과 그 화면상의 한 지점, 그리고 새로운 색상이 주어졌을 때, 주어진 지점과 색이 같은 주변 영역을 새로운 색상으로 다시 색칠한다. 8.11 코인 쿼터(25센트), 다임(10센트), 니켈(5센트), 페니(1센트)의 네 가지 동전이 무한히 주어졌을 때, n센트를 표현하는 모든 방법의 수를 계산하는 코드를 작성하라. 8.12 여덟 개의 퀸 8x8 체스판 위에 여덟 개의 퀸(queen)이 서로 잡아 먹히지 않도록 놓을..
면접 문제 8.4 부분 집합 어떤 집합의 부분 집합을 전부 반환하는 메서드를 작성하라. 8.5 재귀 곱셈 연산자를 사용하지 않고 양의 정수 두 개를 곱하는 재귀 함수를 작성하라. 덧셈(addition), 뺄셈(subtraction), 비트 시프티(bit shifting) 연산자를 사용할 수 있지만 이들의 사용 횟수를 최소화해야 한다. 8.6 하노이타워 전형적인 하노이타워(Towers of Hanoi)에서는 크기가 서로 다른 N개의 원반을 세 개의 기둥 중 아무 곳으로나 옮길 수 있다. 초기에 원반은 크기가 맨 위에서부터 아래로 커지는 순서대로 쌓여 있다. 그리고 이 문제에는 다음과 같은 제약조건이 있다. (1) 원반을 한 번에 하나만 옮길 수 있다. (2) 맨 위에 있는 원반 하나를 다른 기둥으로 옮길 ..
메모 8. 재귀와 동적 프로그래밍 재귀 관련 문제는 상당수가 패턴이 비슷함. 주어진 문제가 재귀 문제인지 확인해 보는 좋은 방법은 해당 문제를 작은 크기의 문제로 만들 수 있는지 보는 것임. 다음과 같은 문장으로 시작하는 문제는 재귀로 풀기 적당한 문제일 가능성이 높음. “n번째 … 를 계산하는 알고리즘을 설계하라” “첫 n개를 나열하는 코드를 작성하라.” “모든 … 를 계산하는 메서드를 구현하라.” 사람들이 직감적으로 이 문제가 재귀 문제 같다! 라고 했을 때, 실제로 그문제가 재귀 문제인 경우는 보통 50% 정도였음. 따라서, 재귀로 문제가 풀릴것 같더라도, 다른 방식으로 생각해보는 것을 게을리하면 안됨. 접근법 재귀적 해법 → 부분문제(subproblem)에 대한 해법을 통해 완성됨. ex) f(n..
메모 면접 문제 7.6 직소 N X N 크기의 직소(jigsaw) 퍼즐을 구현하라. 자료구조를 설계하고, 퍼즐을 푸는 알고리즘을 설명하라. 두 조각의 퍼즐 모서리가 주어졌을 때 그들이 들어맞는지 아닌지 알려주는 fitsWith 메서드는 제공된다. 7.7 채팅 서버 채팅 서버를 어떻게 구현할 것인지 설명하라. 특히, 다양한 백엔드 컴포넌트, 클래스, 메서드에 대해 자세히 설명하라. 어떤 문제가 가장 풀기 어려울 것으로 예상되는가? 7.8 오셀로 오셀로(Othello) 게임 규칙은 이러하다. 오셀로 말의 한쪽 면은 흰색, 반대 면은 검은색으로 칠해져 있다. 상대편 말에게 왼쪽과 오른쪽, 또는 위와 아래가 포위된 말은 색상을 뒤집어 상대편 말이 된 것으로 표시한다. 여러분은 여러분 차례에서 적어도 상대편 말 ..
메모 7. 객체 지향 설계 디자인 패턴들을 쏟아내도록 요구하는 것이 아님. 우아하고, 유지보수가 가능한 객체 지향적 코드를 만드는 방법을 이해하고 있는지 살펴보기 위한 것임. 이 문제들에서 낮은 성적을 받으면, 합격 전선에 빨간불이 켜질 수 있음. 접근법 객체 지향 설계에 관한 질문들은 거의 비슷한 방식으로 공략 가능함. 단계 #1: 모호성의 해소 면접관들은 여러분이 스스로 가정을 만들어내고 질문을 통해 명확히 해나가는 과정을 살펴보고 싶어하기 때문에 대부분의 문제들이 고의적으로 모호성을 띔. 객체 지향 설계에 관한 질문을 받으면 누가 그것을 사용할 것이며, 어떻게 사용할 것인지에 대한 질문을 던져야 함. 질문에 따라 육하원칙에 따른 질문을 던져야할 수도 있음. 상황에 따라 설계 자체가 완전히 뒤바뀌기 ..
메모 면접 문제 6.3 도미노 8x8 크기의 체스판이 있는데, 대각선 반대 방향 끝에 있는 셀(cell) 두 개가 떨어져 나갔다. 하나의 도미노로 정확히 두 개의 정사각형을 덮을 수 있을 때, 31개의 도미노로 보드 전체를 덮을 수 있겠는가? 여러분의 답이 옳다는 것을 증명하라(예를 들거나, 왜 불가능한지를 보이면 된다). 6.4 삼각형 위의 개미 개미 세 마리가 삼각형의 각 꼭짓점에 있다. 개미 세 마리가 삼각형 모서리를 따라 걷기 시작했을 때, 두 마리 혹은 세 마리 전부가 충돌할 확률은 얼마인가? 각 개미는 자신이 움직일 방향을 임의로 선택할 수 있는데, 같은 확률로 두 방향 중 하나를 선택한다. 또한 그들은 같은 속도로 걷는다. 이 문제를 확장해서 n개의 개미가 n각형 위에 있을 때 그들이 충돌할..
메모 소수 모든 자연수는 소수의 곱으로 나타낼 수 있는 규칙이 있음. 가분성(divisibility) 소수판별 어떤 소수 n이 소수인지 여부를 판단하는 방법 boolean primeNaive(int n) { if (n < 2) { return false; } for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } 가장 단순한 방법은 2에서 n-1까지 루프를 돌면서 나누어지는 경우가 있는지 확인하는 것임. 위 코드를 살짝 개선해 보면, 루프를 n이 아닌 n의 제곱근까지만 돌면 됨. boolean primeSlightlyBetter(int n) { if (n < 2) { return false; } int sqrt = ..
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120815 문제 풀이 1. remainder 활용 (내 풀이) class Solution { public int solution(int n) { int totalPiece = 6; int remainder = totalPiece % n; if (remainder == 0) { return totalPiece / 6; } else { while (remainder != 0) { totalPiece += 6; remainder = totalPiece % n; } } return totalPiece / 6; } } 먹은 조각이 먹은 사람으로 나누어 떨어져야 하므로 피자 한판 조각만큼 더하면서..