조합 모든 경우의 수를 표현하기 위해 자주 사용되는 또다른 전략 중 하나는 조합이다. 조합으로는 어떤 상황이 놓였을 때 선택에 대한 경우의 수를 표현할 수 있다. 예를 들어 다음과 같은 회사 목록이 있다고 가정해보자. vector company = { "Apple", "Google", "Amazon", "Facebook" }; N개의 원소에서 K개를 고르는 조합 이 회사 목록에서 3개의 회사를 선택하는 모든 경우의 수를 생각해보자. 다음과 같은 선택지들이 있을 것이다. "Apple", "Google", "Amazon", "Apple", "Google", "Facebook" "Apple", "Amazon", "Facebook" "Google", "Amazon", "Facebook" 이처럼 어떤 N개의 원소..
무차별 대입법 (Brute Force) 무차별 대입법은 모든 가능한 값을 다 시도해보는 형태의 전략을 의미한다. 그 중에서도 알고리즘 분야에서는 중첩 루프를 이용하여 표현하는 전략을 의미한다. 무차별 대입을 하는데 있어 필요한 개념들을 정리해보자. 순서쌍 다음과 같은 문제를 생각해보자. 두 자연수 n과 k에 대해 (1
비트마스크 현대의 모든 CPU는 이진수를 이용하여 자료를 표현한다. 이러한 구조 덕분에 컴퓨터는 이진법 관련한 연산들을 아주 빠르고 쉽게 수행할 수 있다. 그리고 이 특성을 프로그래밍에서도 활용할 수 있는데, 그 활용 기법을 비트마스크라고 부른다. 비트마스크를 이용하면 다음과 같은 이점들을 얻을 수 있다. 1. 매우 빠른 시간에 동작한다. 2. 간결하게 코드를 작성할 수 있다. 3. 메모리 절약이 가능하다. 4. 중첩 컨테이너를 단순 컨테이너로 대체할 수 있다. ex) // 기존 map // 비트마스크 활용 vector 5. 집합 개념으로 활용될 수 있고 집합 관련한 연산들을 매우 쉽게 표현할 수 있다. (매우 중요) ex) 다음과 N개의 원소가 있을 때, 이에 대한 모든 부분집합을 나열해보자. vect..
코딩테스트 연습 > 2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 시행착오 x 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Extra/Solutions/Programmers/%ED%81%AC%EB%A0%88%EC%9D%B8%20%EC%9D%B8%ED%98%95%EB%BD%91%EA%B8%B0%20%E..
상호 배타적 집합 어떤 학교에 N명의 사람이 있다고 가정해보자. 학교에서 이 사람들은 처음에는 흩어져 있다가, 서로 같은 학과임을 확인하면 같이 그룹을 만든다. 만약 두 그룹이 서로가 같은 학과임을 확인하면 두 그룹을 합한 더 큰 그룹을 만든다. 이 상황을 표현하기 위해 사용되는 개념이 상호 배타적 집합(서로소 집합)이다. 상호 배타적 집합은 흩어져 있는 원소들을 묶어서 표현한다. 중요한 점은, 이 집합에서는 서로 다른 두 집합에 대해서 교집합이 생기는 상황을 가정하지 않는다. 즉 교집합이 있다면, 그것은 상호배타적 집합이라 할 수 없다. 이것을 알고리즘으로 표현하려면 어떻게 해야 할까? 상호 배타적 집합을 표현하기 위해서는 기본적으로 다음과 같은 연산들이 필요하다. Find : 어떤 원소가 속한 그룹을..
코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT 오픈채팅방 programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 시행착오 1. 빈 log를 answer에 집어넣음 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/Solutions/Programmers/%EC%98%A4%ED%94%88%EC%B1%84%ED%8C..
코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT 문자열 압축 programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 시행착오 시행착오 1. 문자열을 무조건 제일 앞부터 잘라야 한다는 조건을 제대로 읽지 않았음. 2. 한번 자른 문자열이 계속 나타나는지 확인하는것이 아니라, 고정된 크기로 자른 문자열이 연속적으로 같은지 판단해야하는데 이 부분을 잘못 이해함 3. 탐색 범위 오류 (i < s.size()..
Binary Search Tree vs Hash Table 기본적으로 Binary Search Tree와 Hash Table은 모두 키 & 값 형태로 자료를 저장하는 자료구조이다. 그렇기 때문에 사용성 측면에서는 굉장히 유사한 인터페이스를 갖고 있고, 지원하는 연산들도 아주 흡사하다. 그런 이유로, 자주 비교대상이 되는 자료구조로써 각각의 장단점을 한번쯤 정리해볼 필요가 있다. 기능적인 측면 탐색, 삭제, 삽입과 같은 기본기능들에 대해서, 해시 테이블 : O(1) 이진탐색트리 : O(logN) 정도 성능으로 동작한다. 해시 테이블의 해시 함수의 비용과, 충돌 해결비용까지 고려하더라도 데이터가 엄청 많아지는 경우에는 해시 테이블이 효과적이라고 볼 수 있다. 그리고 만약 입력 사이즈를 알고 있다면, 입력 사..
객체 복사 C#, Java, Python 같은 다른 많은 언어에서는 객체에 대해 = 연산을 수행하였을 경우 객체 복사를 수행하지 않는다. 하지만 C++에서는 class가 = 연산을 수행하였을 경우 복사가 일어난다. #include #include using namespace std; class Data { public: int data1; int data2; string data3; }; void Print(const Data& data) { cout
해시 테이블 먼저 배열에 대해 생각해보자. 배열은 컴퓨터 프로그래밍에 있어서 가장 근본이 되는 자료구조이다. 레지스터가 메모리 어드레싱을 통해 특정 번지의 값을 바로 참조해올 수 있는 것처럼, 배열도 특정 주소의 공간을 바로 참조해올 수 있다. 사실 이 특성은 굉장히 유용하게 활용될 수 있다. 특정 위치를 탐색비용 없이 참조해 올 수 있다는 것은, 어떤 데이터들을 저장할 때, 각 데이터가 저장될 위치를 결정할 수 있다고 가정했을 때, 아무런 탐색비용 없이 그 데이터를 저장하고 참조해올 수 있는 자료구조를 설계할 수 있다는 의미이다. 리스트와 같은 일반적인 컨테이너가 저장비용으로 O(1), 데이터 참조 비용으로 O(N) 인 것을 감안했을 때, 저장비용 O(1), 참조비용 O(1)은 자료구조로서 엄청나게 효..
이진 탐색 트리 (Binary Search Tree) 이진탐색트리는 키(Key)를 기반으로 한 데이터들을 트리 구조로 관리하는 노드기반 자료구조이다. 루트 데이터의 키를 기준으로 더 작은 키 값을 갖는 데이터들은 왼쪽 하위 서브트리에 위치시키고, 더 큰 키 값을 갖는 데이터들은 오른쪽 하위 서브트리로 위치시킨다. 그리고 각 서브트리들은 재귀적으로 같은 전략을 통해 새로운 데이터들을 위치시킨다. 일반적인 리스트 형태로 구조화된 자료구조에서는 데이터를 탐색하기 위한 비용이 O(N) 정도인 반면, 이진 트리 형태로 자료를 구조화시키고 나면, 이진탐색을 통해 원하는 데이터를 찾기 위한 탐색비용을 O(logN)까지 줄일 수 있다. 예를 들어 7을 키로 갖는 데이터를 찾고자 한다면, 다음과 같은 순서로 찾을 수 있..
소수 소수판별 어떤 자연수 N을 입력으로 받았을 때, 그 자연수가 소수인지 아닌지 판단하는 알고리즘을 작성해보자. 어떤 자연수 N이 소수라고 한다면, 그 수는 1과 자기자신 외의 약수를 가지지 않는다. 그러므로 가장 간단하게 알고리즘을 작성한다면 2부터 N-1까지의 모든 자연수로 나누어 보고, 한번이라도 나누어진다면, 소수가 아니고, 단 한번도 나누어지지 않았다면 소수라고 할 수 있을 것이다. 하지만, 합성수의 대한 개념을 이용하면, 이 알고리즘을 조금 더 최적화시킬 수 있다. 합성수란, 1과 자기자신 외의 다른 약수를 갖고있는 수를 의미한다. 예를 들어 6은 2*3으로 표현될 수 있으므로 합성수이다. 소수와 완전 반대되는 개념을 갖으므로, 어떤 수가 합성수라면, 소수가 아니다. 어떤 자연수 N이 입력으..
C++ Data Types C++의 모든 타입은 기본 타입, 파생 타입, 사용자 정의 타입으로 구분할 수 있다. 기본 타입 (Primary Type) 기본 타입은 C++에서 기본적으로 사용되는 타입들을 의미한다. 다음과 같은 기본 타입들이 존재한다. // primitive types bool a = false; char b = 'a'; unsigned char c = 255; short d = 32767; unsigned short e = 65535; int f = 2147438647; unsigned int g = 4294967295; long h = 2147438647; unsigned long i = 4294967295; long long j = 9223372036854775807; unsigned..
메모리 구조 프로세스의 메모리 (RAM) 구조는 다음과 같은 형태로 구성된다. 코드 영역 메모리의 코드 영역은 실행할 프로그램의 코드(명령어) 자체가 저장되는 영역이다. 텍스트 영역이라고도 불리는데, 이 영역에서 CPU는 저장된 명령어를 하나씩 가져가서 처리한다. 데이터 영역 메모리의 데이터(data) 영역은 프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역이다. 데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸한다. ex) 다음 변수들은 데이터 영역에 저장된다. int global_value = 10; void temp() { static int static_value = 10; } 스택 영역 메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매..
Managed 언어 Managed 언어란 특정 런타임 환경 내에서, 프로그램을 생성하도록 설계된 언어를 의미한다. 이러한 언어들은 대부분 인터프리터나, VM(Virtual Machine)을 지원하고, 프로그램의 코드가 이 위에서 동작하도록 설계되어 있다. 소스코드를 컴파일하는 과정은 VM 위에서 이루어지고, 실행파일 또한 VM 위에서 동작하게 된다. 추가로 VM은 메모리 관리(Garbage Collector .. ), 운영체제 차원의 보안성을 위한 관리 등의 역할을 수행한다. Python, JavaScript, Java, C# 등등의 언어가 managed 언어에 속한다. Unmanaged 언어 따로 VM과 같은 런타임 환경의 관리를 받지 않는 모든 언어는 unmanaged 언어라고 할 수 있다. 우리가 ..
컴파일 과정 소스코드를 작성하고 빌드를 하게되면 일반적으로 다음과 같은 과정을 통해 실행파일이 만들어진다. 소스코드(Input) -> 전처리기 -> 컴파일러 -> 어셈블러 -> 링커 -> 실행파일(Output) 전처리기는 소스코드 자체에 대한 수정을 담당한다. 컴파일러는 소스코드를 어셈블리 코드로 번역한다. 어셈블러는 어셈블리 코드를 목적코드로 번역한다. 링커는 생성된 목적코드들을 링킹하여 실행파일을 만든다. 컴파일타임 & 런타임 전체 컴파일 과정과 그 이후 과정 중, 실행파일이 만들어지는 순간까지를 컴파일타임이라 부르고, 실행파일이 실행된 후의 시간대를 런타임이라 부른다. 소스코드(Input) -> 전처리기 -> 컴파일러 -> 어셈블러 -> 링커 -> 실행파일(Output) -> 실행 컴파일타임 런타임..
기본 개념 정렬은 컨테이너에 저장된 데이터를 크기 순으로 나열하는 알고리즘을 말한다. 정렬 알고리즘은 굉장히 많은 알고리즘들의 기초 토대가 되기 때문에, 잘 알고 있어야한다. 다음과 같은 수열이 있다고 가정해보자. 3, 500, 2, 600, 5, 150, 800, 1, 2500, 800 수열을 작은 수에서부터 큰 수로 나열하는것을 오름차순 정렬이라 한다. 1, 2, 3, 5, 150, 500, 600, 800, 800, 2500 수열을 큰 수에서부터 작은 수로 나열하는것을 내림차순 정렬이라 한다. 2500, 800, 800, 600, 500, 150, 5, 3, 2, 1 어떤 정렬 알고리즘으로 수열을 정렬하였을 때 같은 크기의 원소가 정렬 후에도 순서가 유지된다면, 그 정렬을 Stable Sort라 부..
별찍기 - 7 www.acmicpc.net/problem/2444 2444번: 별 찍기 - 7 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 소스코드 #include #include using namespace std; int main() { // 별찍기 - 7 int n; cin >> n; // scanf // 5가 들어왔을 경우 -4 ~ 4 for (int y = -(n - 1); y to; reverse(v, from, to); } print(v); return 0; } 미로 탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 ..
코딩테스트 연습 > 해시 > 완주하지 못한 선수 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/Solutions/Programmers/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%20%EB%AA%BB%ED%95%9C%20%EC%84%A0..
코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT 신규 아이디 추천 programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 시행착오 6단계에서 연산 후 . 문자열을 제거해야하는데, 문제를 꼼꼼히 읽지 않아서 시간을 좀 소모함. 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/String/Solutions/Progr..
friend 키워드 C++에서는 캡슐화를 위한 접근지정자(private, protected, public)들을 갖고 있다. 그 중 private과 protected로 지정된 함수 및 변수들은 외부에서 접근이 불가능하다. (protected는 하위클래스에서 접근 가능) 이러한 상황에서 어떤 특정 객체 or 함수에서만 예외적으로 접근을 허용하도록 하기 위해 friend 키워드를 이용한다. ex) Item이라는 클래스가 있다. 이 클래스는 Init이라는 함수를 통해 내부 변수들을 초기화한다. 그러므로 외부에서 Item 객체 생성 후 반드시 Init 함수를 따로 호출해야한다. 그리고, Item 클래스는 반드시 ItemManager 클래스를 통해 생성되어야한다. (이유는 여러가지겠지만, ItemManager에서 ..
