목록기본개념/알고리즘공부 (11)
VioletaBabel
테스팅 관련 질문1. 실생활에서 접하는 객체를 테스트하라2. 소프트웨어 하나를 테스트하라3. 주어진 함수에 대한 테스트 코드를 작성하라4. 발생한 이슈에 대한 해결책을 찾아라 --평가할 요소 1. 큰 그림을 이해하고 있는가 : 어느게 더 중요하고 어느게 덜 중요한지 우선순위를 매길 수 있는가. 2. 퍼즐 조각을 제대로 맞출 줄 아는가 : 소프트웨어가 어떻게 동작하는지와 그 소프트웨어가 더 큰 생태계의 일부로 어떻게 귀속되는지 이해하는가 3. 조직화 : 문제에 구조적으로 접근하고 있는가, 아니면 생각나는 대로 지르는가. 4. 실용성 : 실제로 적용 가능한 합리적인 테스트 계획을 세울 수 있는가 --실제 세계에서 객체 테스트하기 1단계 : 사용자는 누구인가? 제품의 사용 목적은 무엇인가?문제를 풀기 전에 해..
자주 쓰이는 정렬 1. 버블 정렬배열의 첫 원소보다 그 다음 원소를 비교해가며 두 원소를 바꾸는 작업을 계속한다.평균 및 최악 실행 시간 O(n^2), 메모리 O(1) 2. 선택 정렬선형 탐색을 하며 매 탐색마다 가장 작은 원소를 맨 앞으로 보내는 방식을 반복한다.평균 및 최악 실행 시간 O(n^2), 메모리 O(1) 3. 병합 정렬배열을 절반씩 나누어 각각 정렬한 후, 둘을 합하여 다시 정렬하는 방법.평균 및 최악 실행 시간 O(nlogn), 메모리는 상황에 따라 다름 4. 퀵 정렬무작위로 선정한 한 원소를 이용해, 작은 원소는 앞으로, 큰 원소는 뒤로 보낸다.평균 실행 시간 O(nlogn), 최악 실행 시간 O(n^2), 메모리 O(logn) 5. 기수 정렬각 자릿수를 순회해 나가며 각 자리의 값에 ..
문제를 다루는 방법 1. 소통하라 : 시스템 설계 문제는 의사소통 능력을 평가하기 위함이므로 끊임없이 의사소통하도록 한다. 질문을 던지고 발생할 수 있는 문제점을 열린 마음으로 받아들여라. 2. 처음엔 포괄적으로 접근하라 : 알고리즘으로 바로 뛰어들지 말라. 한 부분만 과도하게 파고들지 마라. 3. 화이트보드를 사용하라 : 내가 제안하는 그림을 그리며 설명하라. 4. 면접관이 우려하는 부분을 인정하라 : 면접관이 짚은 문제점을 인정하고 적절하게 수정하라. 5. 가정을 할 때 주의하라 : 잘못된 가정을 주의하라. 6. 가정을 명확히 언급하라 : 내가 실수를 했을 때 바로잡아줄 수도 있고, 내가 어떤 가정을 했는지를 다른 사람들도 알 수 있게 해준다. 7. 필요하다면 어림잡아 보라 : 내가 알고 있는 다른 ..
객체 지향 설계 : 기술적 문제나 실제 생활에서 접하는 객체들을 구현하는 클래스, 메서드들을 대략적으로 그려봄 유지보수가 용이한 객체 지향 코드를 만드는 법을 이해하고 있는지를 가림. --접근법 단계 1 : 모호성의 해소가장 중요한 것은 누가 어떻게 사용할 것인지를 아는 것. 질문에 따라서는 누가, 무엇을, 어디서, 언제, 어떻게, 왜가 필요할 수도 있다. 단계 2 : 핵심 객체의 설계시스템에 넣을 핵심 객체(core object)가 뭔지를 생각해야 한다. 단계 3 : 관계 분석객체 사이의 관계를 분석해야 한다.어떤 객체가 어떤 객체의 멤버이거나 상속을 받아야하거나 다대다 관계인지 일대다 관계인지를 알아야 한다.설계가 얼마나 일반적이어야 하는지는 충분한 질문과 상의를 거쳐야 한다. 단계 4 : 행동 분석..
& = and| = or^ = xor (비트가 달라야 1)~ = not> = ÷ --x^0 = xx^1 = ~xx^x = 0 x&0 = 0x&1 = xx&x = x x|0 = xx|1 = 1x|x = x x+x = x*x = x
트리는 사이클이 없는 연결 그래프이다. 그래프는 노드와 노드를 연결하는 간선을 하나로 모은 것이다. 사이클이 없는 그래프를 비순환 그래프라고 한다. 모든 정점 간에 경로가 존재하는 그래프를 연결 그래프라고 한다. --인접 리스트 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include #include using namespace std;struct node{ node *next, *prev; int num;}; node *head[9], *foot; void init(..
트리 트리는 그래프의 일종. 허나 사이클이 없다. 트리는 하나의 루트 노드를 가진다.루트 노드는 0개 이상의 자식 노드를 가지고 있다.자식 노드는 0개 이상의 자식 노드를 가지고 있다. 이는 반복된다. --이진 트리는 각 노드가 최대 둘의 자식을 가지는 트리이다. 이진 탐색 트리는 왼쪽 자식들 left = new node; root->right = new node; root->left->left = new node; root->left->right = new node; root->right->left = new node; root->right->right = new node; root->left->left->left = leaf; root->left->left->right = leaf; root->lef..
FIFO.프린터처럼 먼저 들어간 종이가 먼저 나옴. --배열로 구현 123456789101112131415161718192021#include int main(){ int num[100], count = 0; char command; int comnum; while (1) { printf("입력 - i / 삭제 - d\n : "); scanf("%c", &command); if (command == 'i') { printf("입력할 자연수 : "); scanf("%d", &comnum); num[count++] = comnum; } else if (command == 'd' && count > 0) printf("%d\n", num[--count]); while (getchar() != '\n'); }}..
LIFO에 따라 자료를 배열.프링글스같은 느낌임(공장에서 가장 마지막에 넣은 과자를 우린 가장 먼저 쳐먹지) ---배열 이용 123456789101112131415161718192021#include int main(){ int num[100], count = 0; char command; int comnum; while (1) { printf("입력 - i / 삭제 - d\n : "); scanf("%c", &command); if (command == 'i') { printf("입력할 자연수 : "); scanf("%d", &comnum); num[count++] = comnum; } else if (command == 'd' && count > 0) printf("%d\n", num[--count]..
연결된 노드를 표현해주는 자료구조.각 노드는 이전 노드와 다음 노드를 가리킨다.장점은 시작이나 끝 지점에 아이템을 추가, 삭제 시 O(1)에 가능함.다만 특정 인덱스는 상수 시간에 접근할 수 없음(시작이나 끝 지점부터 타고타고 넘어가야 함.) --양방향 예제 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201..