ㅇㅅㅎ

[ 해시테이블 vs STL map ] 1. 해시테이블과 STL map을 비교하여 장단점을 논하라. 2. 해시테이블은 어떻게 구현되는가? 3. 입력의 개수가 적다면, 해시테이블 대신 어떤 자료구조를 활용할 수 있겠는가? 1. 해시테이블 STL map 키에 대한 해시 함수를 호출하여 저장 키를 기준으로 만든 이진 탐색 트리에 키/값 쌍으로 저장 충돌 처리 필요(보통 체이닝 사용) 충돌 처리 필요 없음 삽입 및 탐색 시간(충돌이 적을 경우) O(1) 삽입 및 탐색 시간 O(log N) 2. 해시테이블은 보통 연결리스트 배열로 구현합니다. 키와 값의 쌍을 저장하려면 해시 함수를 사용해서 키 값을 배열의 인덱스 값으로 대응시킨 다음에 해당 위치에 있는 연결리스트에 값을 삽입합니다. 해시테이블은 연결리스트의 배열이..

[ 클래스와 상속 ] C++에서 모든 데이터 멤버와 메서드는 기본적으로 private입니다. public 키워드를 사용하면 그 값을 변경할 수 있습니다. Person이라는 class를 제작하고 Person을 상속하는 Student라는 class를 만들면 다음과 같습니다. #include using namespace std; # define NAME_SIZE 50 // 매크로 정의 class Person{ int id; char name[NAME_SIZE]; public: void aboutMe(){ count aboutMe(); // "I am a student" 출력 Person * p = new Student(); p->aboutMe(); // "I am a person" 출력 파생 클래스에서 재정의..

[ 널리 사용되는 정렬 알고리즘 ] 👀 버블 정렬 | 평균 및 최악 실행 시간: O(n^2), 메모리: O(1) : 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복합니다. 이 과정을 완전히 정렬된 상태가 될 때까지 반복합니다. JAVA(위키백과) void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i < arr.length - 1; i++) { for(int j= 1 ; j < arr.length-i; j++) { if(arr[j]

[ 문제를 다루는 방법 ] 면접관과 소통 처음에는 포괄적으로 접근 종이를 사용하여 계획 및 설명 면접관이 우려하는 부분을 인정 가정 시 주의 가정을 명확히 언급 필요하다면 어림잡아 보기 적극적으로 문제 해결하기 [ 시스템 설계: 단계별 접근법 ] 문제의 범위를 한정 합리적인 가정을 만들기 중요한 부분을 먼저 생각하기 핵심 문제점을 파악하기 핵심 문제점을 해결할 수 있도록 다시 설계하기 [ 규모 확장을 위한 알고리즘: 단계별 접근법 ] 질문하기 현실적 제약을 무시하기 현실적 제약에 적용하기 문제를 풀기 [ 시스템 설계의 핵심 개념 ] 👀 수평적(horizontal) vs 수직적(vertical) 규모 확장 수직적 규모 확장 : 특정 노드의 자원의 양을 늘리는 방법 ex) 서버에 메모리 추가하여 서버의 처리..

[ 트리플 스텝 ] 어떤 아이가 n개의 계단을 오를 때 한 번에 1 계단 오르기도 하고, 2 계단이나 3 계단을 오르기도 합니다. 계단을 오르는 방법이 몇 가지가 있는지 계산하는 메서드를 구현하라. ✔️ 브루트포스 def countWays(n): if n -1: return memo[n] else: memo[n..

[ 접근법 ] : 재귀적 해법은 부분문제에 대한 해법을 통해 완성됩니다. 따라서 많은 경우, 단순히 f(n-1)에 대한 해답에 무언가를 더하거나, 제거하거나, 아니면 그 해답을 변경하여 f(n)을 계산해 냅니다. 아니면 데이터를 반으로 나눠 각각에 대해서 문제를 푼 뒤 이 둘을 병합하기도 합니다. 👀 상향식 접근법 : 계산하면서 아래로 내려가는 형태를 말하며 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작합니다. 핵심은 이전에 풀었던 사례를 확장하여 다음 풀이를 찾는 것입니다. 👀 하향식 접근법 : 출력형태를 만들어놓고 회수하는 형태로 어떻게 하면 N에 대한 문제를 부분 문제로 나눌 수 있을지 생각해 봐야 합니다. 나뉜 부분문제의 경우가 서로 겹치지 않도록 주의해야 합니다. 👀 반반 접근법 : 데..

콜 센터 고객 응대 담당자, 관리자, 감독관 이렇게 세 부류의 직원들로 구성된 콜 센터가 있을 때, 콜 센터로 오는 전화는 먼저 상담이 가능한 고객 응대 담당자로 연결되어야 합니다. 고객 응대 담당자가 처리할 수 없는 전화는 관리자로 연결되고, 관리자가 처리할 수 없는 전화는 다시 감독관에게 연결됩니다. 이 문제를 풀기 위한 자료구조를 설계하라. [ Rank ] from enum import Enum class Rank(Enum): DIRECTOR = 0 MANAGER = 1 RESPONDENT = 2 def __next__(self): if self.value != 0: return Rank(self.value - 1) else: return ValueError("You are Director.") 👀..

카드 한 벌 카드 게임에 쓰이는 카드 한 벌을 나타내는 자료구조를 설계하라. 그리고 블랙잭 게임을 구현하려면 이 자료구조의 하위 클래스를 어떻게 만들어야 하는지 설명하라. 👀 카드 게임과 블랙잭 게임에 대해서 알지 못하여 아래 사이트의 java코드를 바탕으로 python 코드로 재구성해보았습니다. GameAutomator에 필요한 부분은 작성하지 않았습니다. https://github.com/czepeda/Java-Cracking-the-Coding-Interview/tree/master/Chapter%208/8.1%20Deck%20of%20Cards%20and%20BlackJack/src/pkg8/pkg1/deck/of/cards/and/blackjack GitHub - czepeda/Java-Crac..

[ 객체 지향 프로그래밍 ] 프로그램을 수많은 '객체(object)'라는 기본 단위로 나누고 이들의 상호작용으로 프로그램을 제작합니다. 여기서 객체란 하나의 역할을 수행하는 '메서드와 변수(데이터)'의 묶음입니다. [ 객체 지향 프로그래밍 요소 ] 👀 캡슐화 → 정보 은닉 : 변수와 함수를 하나의 단위로 묶는 것을 의미합니다. 👀 상속 → 재사용+확장 : 자식 클래스가 부모 클래스의 특성과 기능을 그대로 물려받는 것을 의미합니다. 👀 다형성 → 사용편의 : 하나의 변수, 또는 함수가 상황에 따라 다른 의미로 해석될 수 있는 것을 의미합니다. 오버라이딩(Overriding) : 부모 클래스에 정의되어 있는 메서드를 자식클래스에서 재정의하여 사용하는 것입니다. 오버로딩(Overloading) : 같은 이름을..

[ 소수 ] 소수는 약수가 1과 자기 자신뿐인 자연수입니다. 모든 자연수는 소수의 곱으로 나타낼 수 있다는 규칙이 있습니다. 👀 가분성(divisibility) 어떤 수 x로 y를 나눌 수 있으려면 x를 소수의 곱으로 분할하였을 때 나열되는 모든 소수는 y를 소수의 곱으로 분할하였을 때 나열되는 모든 소수들의 부분집합이어야 합니다. 즉, x/y를 만족하려면 모든 i에 대해서 j_i 2){ return false; } int sqrt = (int) Math.sqrt(n); for(int i=2; i