낙서 코딩

개념

말 그대로 구간의 누적의 합을 구하는 알고리즘이다. 배열에 값을 저장하고 하나씩 더해가는 방식은 O(n^2)의 시간 복잡도를 갖는다. 하지만 누적합 알고리즘을 사용한다면 O(n)으로 시간복잡도를 줄일 수 있다. 보통 누적합은 부분 합을 구하기 위해서 사용하는데 만약 a부터 b까지의 합을 구한다고 하면 먼저 누적합을 만들고, b번째 요소에서 a-1번째 요소를 빼주면 구할 수 있다.

사용 하면 좋은 경우

1. 리스트에 일정 구간의 값의 합을 구할 때
2. 리스트에 일정 구간에 값을 넣어야 할 경우(시작과 끝 부분에 값 넣어놓고 누적합)

사용 방법

1. 구간의 합 구하기

import itertools

a = [3,2,1,6,8,4]
result = list(itertools.accumulate(a))

print(result)

🖨️ [3, 5, 6, 12, 20, 24]

1. 부분 합 구하기

import itertools

a = [3,2,1,6,8,4]
start = 3
end = 5
acc = list(itertools.accumulate(a))

result = acc[end] - acc[start-1]

🖨️ 18

누적합을 우선 구한 후 마지막 부분의 누적합 값에서 시작부분 전의 누적합을 빼서 부분 합을 구할 수 있다,

시간 복잡도

• O(N)

개념

그룹을 지을 때 사용할 수 있는 알고리즘이다. 처음에 자기 자신을 부모로 설정하고 조건에 따라 부모를 설정한다. Find는 자신의 최상위 부모를 찾는 역할을 한다. Union은 두 변수의 부모가 다르다면 하나의 최상위 부모를 다른 하나의 최상위 부모의 자식으로 만들어 두개의 그룹이 합쳐지는 기능을 수행한다.

• Union by Rank : 트리가 균형이 맞도록 한다. 각 집합에 대해 이 집합을 나타내는 트리의 높이를 rank 변수에 저장한다. 그리고 두 집합을 합칠 때 rank가 작은 집합을 rank가 큰 집합 아래에 붙힌다.
• Path Compression : 경로 압축(path compression)은 find 과정 가운데 경로 상의 모든 점들을 곧바로 루트 정점에 연결하는 방법이다. 이렇게 하면 위 그림과 같은 구조로 시간 복잡도가 훨씬 줄어들게 된다.

조건

• Cycle 구조가 생기면 안된다. 따라서 Union은 서로의 부모가 다를때만 해야한다.

사용하기 좋은 경우

1. 서로 중복되지 않는 부분 집합들로 나눌 때
2. 그룹의 수를 구할 때

구현 방법

1. Find

parent = [x for x in range(10)] # 자기 자신이 부모로 초기화

def find_parent(x, parent):
	if parent[x] == x: # x가 최상위 부모
			return x
	#x의 부모중 최상위 부모 찾기
	parent[x] = find_parent(parent[x], parent)
	return parent[x]

1. Union

def union_parent(a, b, parent):
	pa = find_parent(a)
	pb = find_parent(b)
	if pa == pb :
		pass
	elif pa < pb : # 더 큰애가 부모가 되게 설정
		parent[pa] = pb
	else:
		parent[pb] = pa

시간 복잡도

• O(M)+O(Mlog⋆N)+O(Nlog⋆N)=O((M+N)log⋆N)
• (M : find 연산 수, N : 트리가 바뀌는 횟수)

개념

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

https://blog.hexabrain.net/246 참고

조건

• 수들이 오름차순 또는 내림차순으로 정렬 되어 있어야 한다.
• 원하는 값을 찾으면 종료한다. (종료 조건1) → 값을 찾음
• 왼쪽값이 오른쪽 값보다 커지면 종료한다. (종료조건2) → 값이 없음

사용 하면 좋은 경우

1. 리스트에서 값을 찾을 때 시간을 단축해야 하는 경우
   • list에서 find() 함수를 사용하거나 반목문으로 값을 찾을 시 O(N)의 시간이 필요하기 때문에 이진 탐색을 사용하면 시간 효율성을 증가 시킨다.
2. 조건에 맞는 최소 또는 최대값을 찾아야 하는 경우
   • 이러한 경우에는 index를 left, right로 두지 않고 left = 가장 작은 값, right = 가장 큰 값 으로 설정하여 배열에서의 위치가 아닌 조건에 맞는 값을 구 할 수 있도록 한다.

구현 방법

기본 이진 탐색

1. 반복문

#include <iostream>
#include <vector>

using namespace std;

int BinarySearch(vector<int> num, int target) {
    int left = 0, right =(int) num.size(), mid = 0;
    sort(num.begin(), num.end()); //숫자 오름차순 정렬
    //num : {1, 2, 4, 5, 15, 56, 123, 125, 199, 3215}
    while(left <= right) { //종료 조건
        mid = (left + right) / 2;
        if(num[mid] == target) {// target을 찾았을 때
            return mid;
        }
        else if(num[mid] > target) { //target보다 클 때 -> 왼쪽 수들을 확인
            right = mid - 1;
        }
        else { //target보다 작을 때 -> 오른쪽 수들을 확인
            left = mid + 1;
        }
    }
    return -1;
}

1. 재귀 함수

#include <iostream>
#include <vector>

using namespace std;
//재귀 함수는 num을 정렬 해서 함수 호출
int RecurBinarySearch(vector<int> num, int target, int left, int right) {
    if(left > right) return -1; //종료 조건
    int mid = (left + right) / 2;
    if(num[mid] == target) { //target을 찾았을 때
        return mid;
    }
    else if(num[mid] > target) { // target보다 클 때
        return RecurBinarySearch(num, target, left, mid-1);
    }
    else { //target보다 작을 때
        return RecurBinarySearch(num, target, mid+1, right);
    }
}

int main(int argc, const char * argv[]) {
    vector<int> num {1,5,2,199,56,3215,125,123,15,4};
    sort(num.begin(), num.end());
    int left = 0, right = (int)num.size();
    cout << RecurBinarySearch(num, 199, left, right) << endl;
    return 0;
}

UpperBound

목표값보다 큰 값이 처음 발견되는 곳 찾기

int UpperBound(vector<int> num, int target) {
    int left = 0, right = (int) num.size(), mid = 0;
    sort(num.begin(), num.end());
    int ans = 0;
    while(left <= right) {
        mid = (left + right) / 2;
        if(num[mid] <= target) { // 목표보다 작거나 같으면 오른쪽 보기
            left = mid + 1;
        }
        else { // 목표보다 크면 답의 후보로 두고 왼쪽 보기
            ans = mid;
            right = mid - 1;
        }
    }
    return ans;
}

LowerBound

목표값보다 작은 값이 처음 발견되는 곳 찾기

int LowerBound(vector<int> num, int target) {
    int left = 0, right = (int) num.size(), mid = 0;
    sort(num.begin(), num.end());
    int ans = 0;
    while(left <= right) {
        mid = (left + right) / 2;
        if(num[mid] >= target) { //목표보다 크거나 같으면 왼쪽 보기
            right = mid - 1;
        }
        else { // 목표보다 작으면 답의 후보로 두고 오른 쪽 보기
            ans = mid;
            left = mid + 1;
        }
    }
    return ans;
}

결과

int main(int argc, const char * argv[]) {
    vector<int> num {1,5,2,199,56,3215,125,123,15,4};
    sort(num.begin(), num.end());
    int left = 0, right = (int)num.size();
    for(int i = 0; i < num.size(); i++) {
        cout << num[i] << " ";
    }
    cout << endl;
    cout << "재귀 : " << RecurBinarySearch(num, 199, left, right) << endl;
    cout << "반복문 : " << BinarySearch(num, 199) << endl;
    cout << "UpperBound : " << UpperBound(num, 199) << endl;
    cout << "LowerBound : " << LowerBound(num, 199) << endl;
    return 0;
}

시간 복잡도

• O(logN)

안녕하세요. 개발자로 취업하기, 교육 3편은 엘리스 SW 엔지니어 트랙에 대해 다뤄보겠습니다. 해당 교육은 프론트엔드 개발자 취업 준비생을 위한 16주 집중 교육입니다. 다른 부트캠프와는 다르게 6개월 미만의 소프트웨어(SW) 교육이기에 단기간에 프로그래밍에 빠른 성장을 이루고 싶은 분들에게 추천하는 트랙입니다. 엘리스 트랙은 유튜버로 활동 중이신 '생활코딩'님이 직접 강의를 진행해주시는 것으로 유명합니다.

지원 과정 및 자격

엘리스 SW 엔지니어 트랙(https://elice.training/track/sw)은 K-Digital Training(K-디지털 트레이닝)으로 국민내일배움카드가 있으면 참여하실 수 있습니다.

국민내일배움카드는 국민 누구나 신청 가능한 훈련비 지원 제도로, 인근 고용센터를 통한 방문 신청 또는 HRD-Net (www.hrd.go.kr) )을 통한 온라인 신청이 가능합니다.

선발 단계

선발 단계로는 서류 접수 -> 프리트랙 수강 -> 역량 테스트 -> 화상 면접 순으로 진행됩니다. 자세한 내용은 아래를 참고해주시면 되겠습니다.

 서류 접수

 지원 동기/수강이 필요한 이유
취업에 대한 탐색, 노력 경험/취업 계획
개발 관련 성취 경험
협업 경험
지원할 당시에는 위 4개의 질문을 토대로 자기 소개서 작성을 진행했으나, 현재는 질문의 상이할 수 있습니다.
합격 팁이라고는 말씀드리기 어렵지만, 어떤 자기 소개서든지 최대한 솔직하게 답변해서 작성하는 게 좋을 것 같습니다. 최대한 추상적인 말을 지양하고 직접적인 경험을 바탕으로 작성해야 합니다.

프리트랙 수강

 엘리스 SW 엔지니어 트랙은 역량 테스트(논리, 알고리즘)를 보기 전, 프로그래밍 기초를 쌓을 수 있는 강의를 제공해줍니다. 프리트랙은 GSAT와 같은 논리 문제와 JavaScript 강의, 알고리즘 문제 풀이로 구성되어 있습니다.
프로그래밍을 한 번이라도 접해보셨거나, 기초 지식이 있으신 분들이라면 진행하는 데 큰 문제가 없습니다.
논리력 문제는 GSAT 문제집을 한 번 풀어보고 가시는 걸 추천드립니다. 정작 시험은 온라인으로 진행되기에 실제 문제 풀이에 큰 도움이 되지는 않지만, 문제 유형에 대해 미리 알고 가시는 게 긴장감을 덜어낼 수 있습니다.

역량 테스트

엘리스에서 정해준 날짜 중 원하는 시간에 테스트를 응시하시면 됩니다.
시험 순서는 논리 -> 알고리즘 순으로 진행됩니다.

논리 문제의 경우에는 최대한 집중해서 아는 문제를 빠르게 풀고 넘어가는 것이 중요합니다. 알고리즘 문제는 프로그래머스 1~2단계의 난이도였습니다. 역량 테스트 응시 전 미리 문제를 풀어보고 오신다면 큰 어려움 없이 풀어내실 수 있습니다.

화상 면접

 역량 테스트 응시 후 면접 대상자에 선정이 되시면, 정해진 시간에 면접 담당자와 간단한 질문을 주고 받게 됩니다. 면접 질문은 대체적으로 자기 소개서에 작성된 내용으로 진행됩니다. 면접 분위기는 딱딱하게 진행되지는 않았고, 편안한 분위기에서 진행됩니다.

교육 과정

 교육은 온라인으로 진행되고, 약 4개월 정도 진행됩니다. 2개월 동안 JS, HTML, CSS 기본을 가르치고 나머지 2달 동안 React를 가르치며 총 두 개의 스터디, 두 개의 프로젝트가 진행됩니다. 강의 중간에 간단한 백엔드 강의가 진행되지만, 프로젝트를 진행하기 위한 간단한 교육이기에 백엔드에 관심이 있으신 분들은 개인적인 학습이 필요합니다. 스터디는 4~5명으로 구성된 팀에서 원하는 주제로 진행됩니다. 프로젝트의 경우 1차는 쇼핑몰, 2차는 자유 주제로 진행됩니다.

마무리

 솔직하게 말하자면, SSAFY, SW마에스트로, 42SEOUL, 우테캠, 네부캠 등등 기업에서 운영하는 부트캠프들이 유명한 것은 사실입니다. 그러나, 프로그래밍에 대한 기초가 부족하고 경험이 부족하다면 진입 장벽이 높습니다. 저도 기초와 경험이 부족했고 기초부터 차근차근 다져갈 수 있는 엘리스 부트캠프를 지원했고, 프로그래밍에 많이 가까워 졌습니다. 또한 엘리스는 국비 교육으로, 국비 프로그래밍 교육은 좋지 않다는 인식이 많지만, 엘리스 교육은 높은 수준의 교육을 제공해줍니다.
또한 엘리스 트랙에 합류하기 위해서는 4개의 전형을 통과해야 올 수 있기에 다들 열정이 넘칩니다. 프로그래밍에 대해 관심이 많고 기초를 쌓고 싶은 분들에게는 꼭 한 번 도전해보라고 추천합니다. 개발자, 취준생 여러분 항상 응원하겠습니다.

개발자로 취업하기위해서는 프로젝트 경험과 학점 같은 것도 중요하지만, 꾸준히 Spec Up을 하는것도 중요합니다. 자소서에 한줄이라도 더 추가해야 취업시장에서 우위를 점할 수 있습니다. 우리는 당장에 취업이 하고 싶고 시간도 많지 않기 때문에 빠르게 Spec Up을 할 수 있는 방법 위주로 추천드리고자 합니다. 가장 우선 컴퓨터공학과의 자격증이라고 할 수 있는 정보처리기사에 대해 설명드리겠습니다.

정보처리기사란?

정보처리기사는 소프트웨어 개발 자격증으로, 1년에 3회의 시험이 있습니다. 자격 요건은 다음 사이트에서 확인해보시길 바랍니다.

http://www.gisafirst.com/info/info_02_3.php

정보처리기사 시험은 필기 시험과 실기 시험으로 나누어 지는데, 필기를 붙으면 2년동안 실기에 응시할 수 있습니다. 실기와 필기 내용이 비슷하니 기왕이면 필기를 따자마자 실기시험을 보는 것을 추천드립니다. 정보처리기사 필기는 총 5과목에 각 과목이 40/100점 이상, 전체 60/100점 이상 맞으면 합격이고, 실기는 과락 없이 100점 만점에 60점 이상이면 합격입니다.

정보처리기사 과목은 다음과 같습니다.

내용이 많은 것 같지만, 저희는 빠르게 Spec Up 하는 것이 목표이기 때문에 빠르게 취득할 수 있는 효율적인 공부 법에 대해 소개해드리겠습니다.

정보처리기사 취득 꿀팁

1 . 책으로 공부하기

저는 시나공이라는 책으로 공부를 했는데, 해당 문제집에는 기출문제도 끼워져 있고 내용이 기출이 많은 순으로 A,B,C,D로 등급이 나누어져 있어 책에서 A,B 위주로 공부를 했습니다. 책은 처음 사면 엄청 두껍게 느껴지는데, 문제 위주로 풀며 A,B만 공부한다면 3일이면 다 볼 수 있습니다. 내용을 꼼꼼이 다 외운다기 보다는 어떤 내용이 있는지 훑는 느낌으로 빠르게 한번 완독하는 것이 중요합니다.

2. 기출 문제 풀기

정처기는 이전에 나왔던 기출 문제들이 그대로 나오는 경우가 많고, 자주 나오는 카테고리들이 정해져 있기 때문에 책을 다 봤으면 이제 기출문제들을 풀어보는 것이 중요합니다. 기출문제는 '수제비'라는 네이버 카페에서 구할 수 있습니다. 

https://cafe.naver.com/soojebi

기출을 풀때는 그냥 푸는 것이 아니라, 해당 기출문제 관련 개념을 책에서 한번 더 찾아보며 외우는 것이 중요합니다. 저희는 다 맞는 것이 목표가 아니라 자격증 취득이 목표이기 때문에, 기출문제를 풀어보며 자주 나오는 부분들은 체크해두었다가 꼭 시험 전날 , 당일날에 달달 외우시길 바랍니다.

정처기 취득 요약

1. 우선 시험 자격 요건과 시험 날짜를 확인하고 바로 신청하세요! 신청부터 하면 공부는 하게 되어 있습니다.

2. 그 후에 책을 사서 문제 풀이 + 기출에 자주 나오는 개념 위주로 한번 훑습니다. 책은 시나공, 수제비가 가장 유명한데 어떤 책을 사도 상관 없습니다.

3. 책을 다 훑었다면, 네이버 카페 '수제비'에서 기출문제를 다운받아 풀어봅니다. 이때 문제를 푸는것에 집중하기보다는 기출문제에 관련된 개념들을 책을 보며 다시 공부하는 것이 중요합니다. 헷갈리거나 자주 나오는 개념들은 체크해두도록 합니다.

4. 체크해 두었던 부분들을 시험 전날/ 당일날 달달 외웁시다! 

5. 실기와 필기의 내용이 비슷하니 필기를 합격하자마자 실기에 도전합시다!

저는 이와 같은 방법으로 필기 3일/ 실기 1일 공부하여 자격증 취득에 성공했습니다. 저는 전공자였기 때문에 조금 더 수월했다고 생각했을 수 있지만 책을 처음 딱 폈을 때 거의 다 모르는 내용이였습니다 ㅎㅎ;; 

마무리

정처기 자격증은 요새 취급 안해준다는 말도 많지만, 공기업/ 은행권에서는 정처기 자격증이 있으면 가산점이 주어지고, 사기업에서도 자격증 쓰는 칸에 아무것도 없는 것 보다 몇개 있는 사람을 분명히 더  선호합니다. 정처기 자격증은 따는데 크게 어려움도 없고 CS 면접 준비도 겸사겸사 같이 할 수 있기 때문에 얼른 따는 것을 강추합니다!

개발자 취준생 여러분 모두 응원하며 이번 글은 여기서 마무리 하도록 하겠습니다!! 화이팅입니다!!