메모 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; } } 먹은 조각이 먹은 사람으로 나누어 떨어져야 하므로 피자 한판 조각만큼 더하면서..
메모 면접 문제 5.4 다음 숫자 양의 정수가 하나 주어졌다. 이 숫자를 2진수로 표기했을 때 1비트의 개수가 같은 숫자 중에서 가장 작은 수와 가장 큰 수를 구하라. 5.5 디버거 다음 코드가 하는 일을 설명하라. ((n & (n - 1)) == 0 5.6 변환 정수 A와 B를 2진수로 표현했을 때, A를 B로 바꾸기 위해 뒤집어야 하는 비트의 개수를 구하는 함수를 작성하라. 5.7 쌍끼리 맞바꾸기 명령어를 가능한 한 적게 사용해서 주어진 정수의 짝수 번째 비트의 값과 홀수 번째 비트의 값을 바꾸는 프로그램을 작성하라(예: 0번째 비트와 1번째 비트를 바꾸고, 2번째 비트와 3번째 비트를 바꾸는 식으로). 5.8 선 그리기 흑백 모니터 화면은 하나의 바이트 배열에 저장되는데, 인접한 픽셀 여덟 개를 한..
메모 05. 비트조작 코드를 최적화할 때 융요하게 사용되는 기법으로 활용됨. 코드를 작성하는 것 뿐만 아니라 손으로도 그릴수 있도록 익숙해지는 것이 좋음. 손으로 비트 조작 해보기 세번째 열 트릭은 다음과 같음. 0110 + 0110 = 0110 * 2 와 같음. 따라서 0110 을 왼쪽으로 한 번 시프트 한 것과 같음. 0100은 4와 갓고, 4를 곱하는 것은 왼쪽으로 두 번 시프트하는 것과 같음. 따라서 0011을 왼쪽으로 두 번 시프트하면 1100이 됨. 어떤 비트와 그 비트를 부정한 값을 XOR 하면 항상 1이 됨. 따라서 a^(~a) 를 하면 모든 비트가 1이 됨. ~0을 하면 모든 비트가 1이 됨. 따라서 ~0