"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
고객은 투숙하기 원하는 방 번호를 제출합니다.
고객이 원하는 방이 비어 있다면 즉시 배정합니다.
고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.
원하는 방 번호
배정된 방 번호
1
1
3
3
4
4
1
2
3
5
1
6
전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
[제한사항]
k는 1 이상 10 이하인 자연수입니다.
12
room_number 배열의 크기는 1 이상 200,000 이하입니다.
room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.
코드
import heapq
import sys
sys.setrecursionlimit(10000)
#빈 방 찾기
def findParent(x, parents):
if x not in parents.keys(): # 방이 비었을 때 그 방의 부모를 다음방으로 한다.
parents[x] = x + 1
return x
p = findParent(parents[x], parents)
parents[x] = p + 1
return p
def solution(k, room_number):
answer = []
parents = {}
for n in room_number:
x = findParent(n, parents)
answer.append(x)
return answer
print(solution(10, [1,3,4,1,3,1]))
후기
처음에 parents를 딕셔너리가 아닌 리스트로 했는데 답은 다 맞는데 자꾸 런타임 에러가 떴다. 이유를 보니 k의 값이 너무 크면 그만큼의 리스트를 만드는데 시간이 오래 걸리고 메모리가 부족 할 수 있기 때문이라고한다. 따라서 딕셔너리를 통해 사용하는 방에 대한 정보만 갖고 있어야 하는 게 중요한 것 같다. 그리고 sys.setrecursionlimit으로 재귀 깊이를 늘려야 런타임 에러가 안난다고 한다.
레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.
예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)
손님 번호
주문한 단품 메뉴 조합
1
A B C F G
2
A C
3
A C
4
C D E
5
A C D E
6
B C F G
7
A C D E H
가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.
코스 종류
메뉴 구성
설명
요리 2개 코스
A C
1, 2, 4, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스
C D E
3, 4, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스
B C F G
1, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스
A C D E
4, 6번 손님으로 부터 총 2번 주문됐습니다.
[문제]
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
orders 배열의 크기는 2 이상 20 이하입니다.
orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
각 문자열은 알파벳 대문자로만 이루어져 있습니다.
각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
course 배열의 크기는 1 이상 10 이하입니다.
course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
course 배열에는 같은 값이 중복해서 들어있지 않습니다.
정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.
코드
import collections
from itertools import combinations
def solution(orders, course):
answer = []
for c in course:
d = collections.defaultdict(int)
for order in orders:
tmp = list(combinations(order, c))
for t in tmp:
t = list(t)
t.sort()
d["".join(t)] += 1
if len(d) != 0:
m = max(d.values())
if m <= 1:
continue
for k in d.keys():
if d[k] == m:
answer.append(k)
answer.sort()
return answer
print(solution(["XYZ", "XWY", "WXA"], [2,3,4]))
후기
순열(combination)을 사용하여 가능한 셋을 구한 후 두번 이상 사용한 애들 중에 가장 큰 값들을 정답에 넣은 후 정렬을 하는 문제였는데 어렵진 않았지만 문제를 풀면서 카카오는 정말 조건을 잘 봐야한다고 느꼈다.
안녕하세요. 이번 포스팅에서는 개발자로 취업하기 위해 공부해야하는 Computer Science 공부 방법에 대해 정리해보겠습니다. Computer Science는 컴퓨터 공학 전공 지식이라고 볼 수 있는데, 대학교에서 4년간 배우는 지식이다 보니 범위가 매우 많게 느껴질 수 있지만, 중요한 부분부터 차근차근 공부해나가도록 합시다. 처음에 공부하시는 분이라면, 어디서부터 어떻게 공부할지 매우 막막할 수 있는데, 우선 입문하기 좋은 사이트 먼저 추천드리겠습니다.
해당 사이트에 들어가보면 Computer Science 과목들이 카테고리별로 잘 정리되어있고, 각각의 항목에 대해 간단히 정리가 되어있습니다. 우선은 해당 사이트를 보면서 전반적인 개요에 대해 이해하고 시작하는 것을 추천드립니다.
Computer Science 스터디
우선 저는 학교 동기든, 같이 취준을 하는 친구든, 모르는 사람이든 4명정도 모아 스터디를 진행하는 것을 추천드립니다. 혼자서 많은양을 공부한다면 시간도 많이들고, 제한적인 정보만 습득할 수 있습니다. 따라서 스터디를 통해 주제를 나누고, 서로 해당 부분에 대해 토의하면, 기억에 남는것도 많고 더 deep 하게 공부하실 수 있을 것입니다. 저는 스터디를 어떻게 진행했는지 공유드리겠습니다.
1. CS 스터디 구하기
저는 처음에 대학 동기 8명과 함께 스터디를 진행했습니다. 하지만 워낙 친했던 사람들이였기 때문에, 체계가 잘 잡히지 않았고, 잡담하는 시간도 많아 집중이 잘 되지 않았습니다. 따라서 차라리 모르는 사람들과 진행하는게 낫다고 판단하여, 캠퍼스픽이라는 곳에서 스터디원을 구했습니다.
해당 사이트에서 스터디 - 프로그래밍 카테고리로 들어가면 다양한 스터디를 구할 수 있는데, 직접 구인글을 올려도 되고, 다른 사람의 구인글을 통해 들어가셔도 좋습니다. 저는 직접올렸고 생각보다 많은 사람들이 문의를 해주어서 스터디를 경성하는데 큰 어려움이 없었습니다.
2. CS 스터디 진행
스터디를 결성했다면, 체계적으로 서로에게 도움을 주며 진행하는 것이 중요 할 것입니다. 저희는 1주일에 1번 만나는 것으로 결정했고, 스터디룸 하나를 3시간정도 빌려 진행했습니다. 첫번째로, 위에서 소개해드린 규글 사이트에 컴퓨터 구조, DB, 자료구조, 네트워크, 운영체제, Software Engineering, 알고리즘 총 7개의 항목이 있는데, 1주일에 2개의 항목을 공부하는 것을 목표로 했습니다. 네명 모두 2개의 항목에대해서 공부하되, 개인이 특정 항목을 맡아 더 자세하게 공부를 해와서 발표하는 식으로 진행했습니다. 발표를 하면서 헷갈리거나, 자신이 알고 있는 정보들을 서로 토의하며 더 deep하게 공부할 수 있었습니다. 네명이 공유 파일을 하나 만들어 (저희는 노션에 진행) 각 항목에 대해 자세히 정리를 하였고, 토의를 하며 자료를 강화했습니다. 이렇게 진행하여 3주만에 CS를 한번 훑을 수 있었습니다.
3. 개발자 기술 면접 준비
대부분은 CS 공부를 기술면접 준비를 위해서 할 것입니다. 저희는 따라서 자료 정리를 마친 후 바로 기술면접 준비를 시작했습니다. 자신이 면접에 갈 기업이 있다면, 해당 기업의 질문들을 모았고, 아니면 이곳 저곳 면접 질문 후기들을 모아 한명씩 돌아가며 실전처럼 면접을 진행했습니다. 단 이때, 하나의 질문만 하는 것이 아니라, 그 질문에 계속 꼬리를 물고 깊게 파고 들어가며 진행했고, 저희가 정리했던 자료들에서도 질문을 하며, CS 지식들을 머리에 우겨넣었습니다. 저는 실제로 스터디에서 했던 질문들이, 기업에서 그대로 나오는 경우가 많았고 정말 도움이 많이 됐었다고 생각합니다. 여러분도 단순히 공부만 하지 말고, 이렇게 실전 면접 형식으로 진행해보는 것도 괜찮을 것이라고 생각합니다.
컴퓨터 공학 자격증 준비
컴퓨터 공학과 관련 자격증은 정말정말 많은데 기왕 공부할 거, 자격증도 함께 딴다면 1석 2조의 효과를 누릴 수 있을 것입니다. 저는 정보처리기사와 SQLD를 같이 준비했고, 준비를 하면서도 1석 2조라는 생각에 긍정적인 마인드로 공부를 할 수 있었던 것 같습니다. 앞 포스팅에 해당 자격증들에 대해 써놓은게 있어 공유드리겠습니다.
이 외에도 다양한 자격증이 있으니, CS 공부도 할 겸 1석 2조의 효과를 누리시길 바랍니다.
자기소개서에 쓴 CS 지식
규글에 나오는 것들을 모두 공부했다면, 기본적인 CS 공부는 한 것이지만, 면접은 대부분 자기소개서 위주로 질문을 하기 때문에, 자신이 적은 내용에 대한 지식 또한 필수적으로 공부를 해야합니다. 예를 들어 내가 java를 사용하여 어떤 프로젝트를 했다고 적었으면 Java 언어에 대한 공부를 진행해야합니다. 자바의 특징은 무엇인지, 상속화, 캡슐화 등등은 무엇이고 언제 쓰는지 등, 직접 써본 경험이 있는지까지 생각하며 공부해야합니다. 저는 첫 면접때 java에 관한 질문에서 이론적인 부분은 잘 대답했는데 써본적이 있냐는 질문에서 턱 막혔습니다. 언제 쓰는지, 써봤는지 정리를 해두시면 좋을 것 같습니다. 또한 삼성 자기소개서에서 시스템프로그래밍 수업에서 어셈블리 언어를 사용해봤다 적었는데, 아주 간단한 어셈블리어 질문에도 대답을 못하여 당황했던 경험이 있습니다. 따라서 자기소개서에 쓴 내용은 꼭!꼭! 공부해놓으시길 바랍니다.
마무리
CS 지식은 그 범위가 광범위하나, 저는 저 규글에 있는 지식 외의 범위에서 질문을 받아본 적은 없습니다. 명심해야할 것은 겉핥기 식으로 공부하시면 안되고 꼭 꼬리의 꼬리를 물고 아주 deep하게 공부를 하셔야합니다. 제가 정말 잘대답했다고 생각했고, 실제로 면접관분들이 서로 마주보며 고개를 끄덕였던 질문이 있습니다.
질문 : 퀵 소트와 머지 소트의 차이점에 대해 설명해주세요.
퀵 소트는 ~~ 이고, 머지 소트는 ~~입니다. 차이점은 퀵소트는 보통 빠르지만, 최악의 상황에선 머지소트보다 더 성능이 안좋고, 추가적인 공간을 할당해야한다는 단점이 있습니다.
까지만 말하면, 잘 대답한 것은 맞으나, CS 준비를 잘 한 사람이라면 누구나 할 만한 대답입니다. 저는 여기에 추가로
머지소트는 안정적이고, 최악의 상황에도 O(nlogn)의 시간복잡도를 갖기 때문에 많은 양의 데이터를 처리할 때는 머지소트가 더 적합합니다. 개발 언어들에 내장된 라이브러리에서도 실제로 머지소트로 되어있는 부분이 많은 것으로 알고 있고, 제가 주로 사용하는 Python 언어에서는 Merge Sort와 Injection Sort를 합친 Tim Sort라는 알고리즘을 사용하는 것으로 알고 있습니다.
이렇게 매우 딥한 부분까지 말씀을 드리니, 정말 만족해하셨고 면접도 합격 할 수 있었습니다. 따라서 여러분들도 질문에 대해서만 답변하는 것이 아니라, 사용 사례, 보완 사례, 등등 더 deep하게 들어가서 말씀드리면 성공적인 면접이 될 수 있을 것입니다.
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.
코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.
[조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
[문제]
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
info 배열의 크기는 1 이상 50,000 이하입니다.
info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
개발언어는 cpp, java, python 중 하나입니다.
직군은 backend, frontend 중 하나입니다.
경력은 junior, senior 중 하나입니다.
소울푸드는 chicken, pizza 중 하나입니다.
점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
query 배열의 크기는 1 이상 100,000 이하입니다.
query의 각 문자열은 "[조건] X" 형식입니다.
[조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
언어는 cpp, java, python, - 중 하나입니다.
직군은 backend, frontend, - 중 하나입니다.
경력은 junior, senior, - 중 하나입니다.
소울푸드는 chicken, pizza, - 중 하나입니다.
'-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.
코드
import collections
from itertools import combinations
def solution(info, query):
answer = []
info = list(map(lambda x: x.split(), info))
query = list(map(lambda x: x.split(), query)) #1 3 5sms and
d = collections.defaultdict(list)
for inf in info:
key = inf[:-1]
val = int(inf[-1])
for i in range(5):
for c in combinations(key,i):
d["".join(c)].append(val)
for k in d.keys():
d[k].sort()
for q in query:
tmp = ''
if q[0] != '-':
tmp += q[0]
if q[2] != '-':
tmp += q[2]
if q[4] != '-':
tmp += q[4]
if q[6] != '-':
tmp += q[6]
val = int(q[7])
if len(d[tmp]) == 0 :
answer.append(0)
continue
if len(d[tmp]) == 1 :
if d[tmp][0] >= val:
answer.append(1)
else:
answer.append(0)
continue
left = 0; right = len(d[tmp]);
while left < right:
mid = (left + right) // 2
if d[tmp][mid] >= val:
right = mid
else:
left = mid + 1
answer.append(len(d[tmp]) - left)
return answer
print(solution(["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"],
["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]))
후기
정말정말 어려웠는데 난이도가 파랑이라는게 믿기지 않는다... 푸는 방법은 순열 + 이분탐색 + 해쉬를 사용해야만 효용성을 통과 할 수 있다. 처음에 단순 비교를 했는데 정답은 다 맞았지만 효용성을 하나도 통과하지 못했다.
프로그래머스 고득점 Kit을 전부 완료하였다면 이젠 실전 연습을 해야할 때입니다. 기업의 코딩테스트는 보틍 2~4시간 정도 주고, 4~7문제 정도를 풀어야합니다. 이때 중요한 점은, 부분점수는 아무 의미가 없다는 것입니다. 한 문제당 100점 or 0점이라고 생각하셔도 무방합니다. 보통 50%이상 맞추면 합격권이기 때문에, 선택과 집중을 잘하여 풀수 있는 문제를 완벽하게 푸는 것이 핵심입니다.
코딩테스트 전략
코딩테스트는 제한 시간이 있고, 빠르게 최대한 많은 문제를 풀어야 합니다. 하지만 그렇다고 조바심 내서 이문제 저문제 풀다보면 결국 풀 수 있는 문제도 못풀고 시간만 낭비하게 될 것입니다. 그렇다면 어떻게 전략을 짜야 할까요? 네, 바로 풀 수 있을 문제에 선택과 집중을 해야합니다. 어려운 문제에 더 높은 점수를 주는 기업도 있지만, 보통은 쉽든 어렵든 푼 문제 수로 갈리기 때문에, 내가 풀 수 있는 문제가 무엇인지 파악하는 것이 중요합니다.
1. 문제 파악하기
문제를 읽으면서 어떤 알고리즘을 써야할지 먼저 알아내야합니다. 저희는 고득점 Kit를 푼 상태이기 때문에 해당 유형의 문제가 나오면 무조건 파악할 수 있습니다. 여러 코딩테스트를 봐보았을때 문제가 다 거기서 거기고, 그냥 내용만 살짝 바뀌는 정도였습니다. 따라서 내가 아는 유형인지 먼저 파악하고, 파악이 안될 시 우선 과감히 버리는 것을 추천드립니다. 그렇게 먼저 내가 아는 유형부터 문제를 풀도록 합니다.
2. 문제 손으로 먼저 풀기
알고리즘 문제를 풀 때 절대 문제를 읽으면서 바로 코딩해서는 안됩니다. 우선 문제를 모두 읽으면서 이해하고, 손으로 직접 풀어본 후, 그것을 코딩으로 옮기는 것이 순서입니다. 무작정 시작한다면 중간에 꼬여서 코드를 수정하고, 또 다시 문제를 읽고 예외를 발견하여 또 수정하고, 이러다 보면 코드도 더러워지고 나중엔 마구마구 꼬여버릴 수 있습니다. 제 경험상 다 이해하고 손으로 풀고, 코드로 옮기는 것이 훨씬 빨랐습니다.
3. 30분 내로 못풀면 넘어가기
문제를 풀다보면, 분명 잘 푼거 같은데 정답이 아닌 경우가 있습니다. 이런 경우는 보통 3가지 이유로 나뉩니다.
(1). 내가 생각 못한 예외 상황이 있다.
(2). 아예 잘못된 알고리즘을 선택했다. (시간 복잡도를 고려 못했을 경우)
(3). 코드상 문법이 잘못된 부분이 있다. (Segmentation Fault, Runtime Error 등..)
어떤 이유든지 이러한 경우에는 우선 넘어가도록 합시다. 거의 다 풀었다고 생각하지만, 해당 문제만 붙잡고 있을 순 없는 노릇입니다. 넘어가서 다른 문제를 풀다보면 해결방안이 생각 날 수도 있고, 그때 돌아와서 풀는게 낫습니다. (2)번 같은 경우에는 코드를 싹 다 갈아 엎어야하는 문제가 있고, 또한 모르는 알고리즘이여서 원래부터 못푸는 문제였을 확률이 매우 높습니다. (3)번 또한 컴파일러를 보통 사용할 수 없기 때문에, 디버깅하는데 너무 많은 시간을 허비해야하기 때문에, 우선 풀 수 있는 다른 문제들로 넘어가고, 시간이 남거나 해결방안이 떠올랐을 때 돌아가도록 합시다. 시간 배분하는 것이 매우 중요합니다.
추가로 알아두면 좋은 알고리즘
코딩테스트를 볼때 보통 맨 밑에 보면 조건이 있습니다. 데이터의 사이즈와, 시간 제한이 있는데, 저희가 사용하려는 알고리즘이 해당 제한 내에서 돌아갈 수 있는지 판단하는 것이 중요합니다. 계산해보고 안되는데 더 줄일 방법이 없는 경우에는 저희가 모르는 알고리즘이 있다는 뜻이겠죠!? 따라서 시간복잡도를 줄이는데 주로 사용되는 알고리즘들에 대해서 소개하겠습니다.
저는 이러한 공부 방법으로 라인을 제외하고는 모든 기업의 코딩테스트에서 합격했습니다. 라인은 시간 분배를 못하고, 앞에 문제에서 끙끙대다가 풀 수 있는 문제도 못풀고, 시간분배를 못해 떨어졌다고 생각합니다. 여러분은 꼭 시간 분배를 잘 하시길 바랍니다! 제가 코딩테스트를 본 기업은 네이버, 카카오, 신한은행, 삼성전자, 네이버 클라우드 등이 있는데 나중에 시간이 된다면 각 기업의 코딩테스트에 대해 리뷰해보도록 하겠습니다. 오늘도 읽어주셔서 감사합니다. 개발자, 취준생 여러분 항상 응원하겠습니다.
안녕하세요. 개발자로 취업하기 자격증 편, 리눅스 마스터에 대해 알아보겠습니다. 리눅스 마스터는 리눅스 기반 시스템의 관리능력을 평가하는 1급 자격과 리눅스 운영시스템의 프로그램 사용능력을 평가하는 2급 자격으로 구분되어있습니다. 이 중에서 리눅스 마스터 2급을 많이 준비하실텐데요! 2차는 기초 활용 능력을 평가하는 시험이기에 기출 문제를 기반으로 암기하면 어렵지 않게 취득하실 수 있는 자격증 중 하나 입니다. 그럼 리눅스 마스터 시험에 대해 알아볼까요?
시험일정
리눅스 마스터 1급 시험은 매년 1차, 2차 시험 각 2회씩 진행됩니다. 2급은 1차, 2차 각 4회씩 진행됩니다. 밑에 표는 KAIT에 기재되어 있는 내용입니다.https://www.ihd.or.kr/guidecert1.do 일정 잘 참고하셔서 좋은 결과 있으시길 바라겠습니다!
저도 리눅스 마스터 2급을 현재 공부 중에 있습니다. 1차 시험의 경우 온라인 시험이라 큰 부담이 없이 합격할 수 있다고 하니, 현재는 2차 시험을 위주로 공부하고 있습니다. 공부 베이스는 기출 문제 위주로 공부하고 있고, 필요에 따라서 인터넷 강의를 참고하고 있습니다! 다른 자격증의 경우 항상 벼락치기로 공부하던 습관이 있어서 시험 보기전에 불안했던 경험이 있어서 이번에는 한달의 기간을 잡고 하루 1~2시간씩 공부하고 있습니다. 저와 함께 리눅스 마스터 2급 자격증 시험을 준비하시는 분들 모두 합격하시길 바랍니다.
개발자 취준생 여러분 모두 좋은 결과 있기를 응원합니다. 다음에 또 찾아뵙도록 하겠습니다. 감사합니다!
자기소개서까지 합격하신 여러분 축하드립니다. 하지만 아무리 자기소개서를 잘 썼다고 해도 코딩테스트에서 떨어지면 말짱 도루묵이겠죠! 코딩테스트는 갑자기 준비할 수 없는 영역입니다. 따라서 미리미리 준비를 해놓아야 합니다. 보통은 4문제 ~ 7문제로 이루어져있고, 문제의 절반정도 풀면 합격할 수 있습니다. 문제의 난이도는 회사마다 매우 상이하지만, 보통 1문제는 엄청 쉽고 2문제 부터 백준 실버 ~ 골드, 프로그래머스 level 2 ~3 정도라고 생각합니다.
코딩테스트 준비 사이트
이전에 알고리즘을 해본적이 없거나, 기초가 부족하다면 바로 문제를 풀기는 어려울 것입니다. 코딩 문제를 풀 수 있는 사이트는 백준, 프로그래머스 등이 있는데, 백준도 물론 좋은 사이트지만 저는 프로그래머스를 강력 추천드립니다. 백준에는 너무도 많은 문제가 있어, 무엇을 풀어야할 지 감이 안오고, 또한 컴파일러가 저는 프로그래머스가 훨씬 좋다고 느꼈습니다. 시험 자체도 프로그래머스 사이트에서 보는 기업이 꽤 있기에, 프로그래머스 사이트를 강력 추천드립니다.
바로 코딩테스트 고득점 Kit 입니다. 해당 페이지에는 자주 나오는 유형별로 문제가 나누어져있고, 각 테마마다 level 1~3까지의 문제들이 구비되어 있습니다.
자, 그렇다면 해당 사이트에서 어떻게 공부를 해야할까요? 우선 해당 개념을 먼저 익혀야합니다. 무작정 문제 먼저 푼다고해서 절대 문제를 풀 수 없습니다. 코딩도 수학과 마찬가지로 공식을 먼저 이해해야 문제를 풀 수 있습니다. 알고리즘은 수학의 공식과 똑같습니다. 이를 이해하지 못한다면 문제는 손도 못댈것입니다.
코딩테스트 고득점 Kit 공부 방법
한 항목의 개념을 익히셨다면, level 1 문제만 우선 풀어보도록 합시다. level 2 부터는 절대 쉽지 않습니다. 우선 각 항목의 개념을 익히면서 level 1 문제만 푸는 것을 목표로 합니다. 그렇게 모든 항목의 level 1 문제를 풀고나면, 다시 시작입니다. 다시 각 항목의 개념을 공부합니다. 항목이 10개가 되기 때문에 기억이 잘 안날 수 있고, 다시 보면 분명 더 알아가는 것이 있을 것입니다. 그 후에 level 2 문제에 도전합니다. 아마 이때부터 쉽지 않을 것입니다. 하지만 지금부터가 중요합니다. level 2 정도만 스스로 풀 수 있어도 웬만한 코딩테스트는 합격할 수 있을 것입니다.
level 2 부터는 무조건, 스스로 풀어야합니다. 시간을 1 ~ 2시간정도로 잡아두고, 문제 풀이를 시작합니다. 이 시간 동안에는 절대 남의 코드를 찾아보지 않기로 약속해야합니다. 계속 틀리고 고치고를 반복하다가, 기준 시간이 다 됐음에도 못풀겠을때, 그때 해당 문제를 검색해서 다른 사람의 풀이를 보면서 이해합니다. 이때 그 사람의 코드를 그대로 따라하면, 그건 그 문제를 푼게 아니라, 그냥 타이핑 연습하는 것이겠죠? 머리로 이해했다해도, 남의 코드를 그대로 적는건 기억에 남지 않습니다. 따라서 다른 사람의 코드를 이해만 하고, 다시 자신의 코드로 직접 문제를 푸는것이 핵심입니다. 절대로 조급해 하지마세요. 여러 부분을 얕게 아는 것보다, 하나를 정확히 아는것이 코딩테스트에 도움이 됩니다. 왜냐면 코딩테스트는 부분점수가 없기 때문이죠. 0점이나 90점이나 똑같이 fail입니다. 무조건 100점을 목표로 문제를 풀어야합니다.
level 2까지 모두 푸셨다면 여러분은 이미 합격권에 있을 확률이 높습니다. 하지만 naver, kakao 같은 IT 기업은 문제가 조금 더 어렵습니다. 따라서 level 3까지 도전해봐야 안정적으로 대부분의 코딩테스트를 합격할 수 있을 것입니다. level 3 부터는 아마 남의 코드를 봐도 어렵고 짜증날 수 있습니다. 하지만 한번 풀어놓으면, 해당 알고리즘을 사용하는 문제들은 그냥 껌씹듯이 풀 수 있을 것입니다. 조급해하지말고, 기출문제 풀려하지말고, 그냥 우선 코딩테스트 고득점 Kit 부터 정복하시길 추천드립니다.
마무리
프로그래머스에서 고득점 Kit를 모두 정복하셨다면, 아마 대부분 기업의 코딩테스트에서 절반 이상은 맞출 수 있을 것입니다. 하지만 해당 사이트에 없는 알고리즘도 분명 나올 수 있습니다. 다음 포스팅에서는 코딩테스트 꿀팁과, 심화 알고리즘에 대해 소개하도록 하겠습니다. 개발자, 취준생 여러분 모두 응원하며 마무리하겠습니다. 감사합니다.
list에서 부분 합 배열을 구하는 경우 O(MN)의 시간이 필요하지만 Index Tree를 이용 할 경우 O(MlogN)의 시간으로 단축 시킬 수 있다.
특정 인덱스의 변경이 지속적으로 일어 날 경우
부분 합 배열에서 특정 인덱스를 고칠 경우 그 인덱스를 포함하는 모든 합을 다시 구해야 하기 때문에 O(MN)의 시간이 필요한데 Index Tree를 이용 할 경우 O(MlogN)으로 시간을 단축 시킬 수 있다.
구현 방법
기본 이진 탐색
트리 사이즈 정하기
tydef long long ll;
ll getIndex(int num) { //num은 원소의 갯수
ll tmp = 1;
while(tmp < num) {
tmp <<= 1;
}
return tmp * 2;
}
트리의 말단 노드에 모든 원소를 배치해야 하고 부모까지 배치해야하기 때문에 트리 배열의 사이즈는 $2^n$ ≥ (원소의 개수) 가 되는 n을 찾고 그거의 2배를 해야 부모 노드 까지 배치 할 수 있다.
노드 값 채우기
ll index = getIndex(n);
ll p = index/2;
for(int i = 0; i < n; i++) { //말단 노드에 원소 입력
scanf("%lld", &t[p]);
p++;
}
for(ll i = (index/2) - 1; i > 0; i--) {
t[i] = t[i*2] + t[i*2 + 1]; //왼쪽 자식과 오른쪽 자식의 합
}
트리의 말단 노드에 원소들을 입력 받고 부모 노드들에 자식들의 합을 대입한다. 부모 노드는 아래에서 부터 대입해야 한다.
b 위치의 값을 c로 바꾸기
ll idx = (index/2) + (b-1);
ll pp = idx;
if(t[idx] >= c) {
ll gap = t[idx] - c; //바꾸려는 값과 원래의 값 차이
t[idx] -= gap; //차이만큼 빼기
pp >>= 1; // 부모 노드로 가기
while(pp > 0) { //최상단 노드(1번째 인덱스)까지 업데이트
t[pp] -= gap;
pp >>= 1;
}
}
else {
ll gap = c - t[idx];
t[idx] += gap;
pp >>= 1;
while(pp > 0) {
t[pp] += gap;
pp >>= 1;
}
}
특정 말단 노드의 값을 바꾸면 해당 노드의 부모 노드들의 값을 같이 바꿔준다.
구간 합 출력하기 (b~c번째 인덱스)
ll left = (index / 2) + (b - 1);
ll right = (index / 2) + (c - 1);
ll answer = 0;
while(left <= right) {
if(left % 2 == 0) { //왼쪽에 있는 노드가 부모기준에 왼쪽에 있을때
left /= 2; // 부모 노드로 이동
}
else{//부모 기준 오른쪽에 있을때
answer += t[left];
left ++; // 해당 값을 더해주고 오른쪽 옆으로 이동
if(left == right) { //왼쪽과 오른쪽이 만나면 해당 값 더해주고 종료
answer += t[left];
break;
}
else { //왼쪽과 오른쪽이 다르면 왼쪽의 부모로 이동
left /= 2;
}
}
if(right % 2 == 0) { //오른쪽 노드가 부모 기준 왼쪽에 있을 때
answer += t[right];
right --; //해당 값을 더해주고 왼쪽 옆으로 이동
right /= 2; //새로운 노드의 부모로 이동
}
else {
right /= 2; //부모 노드로 이동
}
}
노드의 위치를 통해 부모 노드로 값을 구할 수 없으면 정답에 더해주고 부모 노드에 포함 된다면 값을 더하지 않고 부모 노드로 이동한다.
