끄적끄적

# 싸피란 무엇인가요?삼성 청년 SW 아카데미(SSAFY)는 삼성의 SW 교육 경험과고용노동부의 취업지원 노하우를 바탕으로 취업 준비생에게 SW 역량 향상 교육 및 다양한 취업지원 서비스를 제공하여 취업에 성공하도록 돕는 프로그램입니다. 선별을 위해 전공자들과 비전공자들을 별도로 모집하고 있으니 비전공자분들도 걱정하지 않으셔도 됩니다! # 에세이(essay) 작성하기우선 싸피에서 바라는 인재상을 살펴보겠습니다.논리적 사고, 전공자들은 코딩테스트, 비전공자들은 GSAT을 필수적으로 치게 됩니다. 여기서 이 부분을 평가할 수 있습니다. 그렇다면 나머지 열정과 학습의지는 어떨까요? 이 부분을 에세이를 통해 보여줘야 됩니다. 싸피는 기업이 아닌 교육집단입니다. 에세이를 작성할 때 내가 무엇을 잘하고, 무엇을 해..

트라이(Trie) 문자열에서 검색을 빠르게 도와주는 자료구조이다. 정수형에서 이진탐색트리를 이용하면 시간 복잡도는 O(logN)이 나오게 된다. 문자열에서 적용했을 때, 문자열의 길이만큼 탐색을 진행해야 하기 때문에 길이를 M이라 하면 O(M*logN)이 걸리게 된다. 하지만 트라이 자료구조를 사용하게 된다면 시간복잡도를 O(M)에 끊을 수 있다. 다음 문자열 집합 {"rebro", "replay", "hi" , "high", "algo"} 를 트라이로 구현한 것이다. 그림에서 보면 알수 있듯이 문자열의 접두사에 대응되는 노드는 서로 연결된 트리이고 빨간 노드는 문자열의 끝을 의미한다. 트라이의 중요한 속성 중 하나는 root에서 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻..

Linked List 노드(Node)라는 개별적인 단위로 저장되는 자료구조이며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(Link)로 구성됩니다. 간략적인 노드 구현은 다음과 같습니다. class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } Linked List 사용하는 이유가 무엇인가요? 크기가 동적으로 변하는 데이터를 관리하기 위해 사용이 됩니다. 그리고 데이터의 삽입과 삭제가 용이하고, 메모리를 유연하게 활용할 수 있습니다. 이 자료구조의 장점과 단점을 각각 말해주세요. 장점으론 데이터 삽입 및 삭제가 효율적으로 이뤄지고 동적으로 변하는 데이터를 저장할 수 있습니다. 단점으..

문제 효주는 포도주 시식회에 갔다. 그곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6..

문제 한 배열 A [1], A [2], …, A [n]에 대해서, 부 배열은 A [i], A [i+1], …, A [j-1], A [j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A [i]+…+A [j]를 의미한다. 각 원소가 정수인 두 배열 A [1], …, A [n]과 B [1], …, B [m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오. 예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다. T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = A[2] + B[3] =..

문제 세준이는 양수와 +, -, 그러고 괄호를 가지고 식을 만들었다. 그러고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 풀이 [알고리즘] 괄호를 추가해서 최솟값이 나오기 위해서는 간단하게 생각하면 된다. 일반적으로 덧셈 ..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다..

문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오. 입력 첫째 줄..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다. 풀이 [알고리즘] BFS와 방문 체크를 이용하면 풀 수 있다. 연산 횟수의 최솟값을 구해달라 했기 때문에 BFS를 이용하고 이미 ..