[코딩테스트] [16198] 에너지 모으기 & [2800] 괄호 제거 & [7490] 0 만들기
·
알고리즘/Recursion
[16198] 에너지 모으기 성공시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초512 MB65974967402476.270%문제N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.x번째 에너지 구슬을 제거한다.W × W의 에너지를 모을 수 있다.x+1x-1N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.N과 에너지 구슬의 무게가 주어..
[코딩테스트] [2529] 부등호 & [9095] 1,2,3 더하기 & [12101] 1,2,3 더하기 2
·
알고리즘/Recursion
[2529] 부등호시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB31504186331267758.215%문제두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.3 1 7 0이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족..
[코딩테스트] [1759] 암호 만들기 & [10971] 외판원 순회 2 & [14888] 연산자 끼워넣기
·
알고리즘/Recursion
[1759] 암호 만들기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB85939412702828044.931%문제바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그..
[Computer Science] [시스템 프로그래밍] 파일 다루기
·
Computer Science/System Programming
시스템 프로그래밍운영체제, 하드웨어와의 상호작용을 프로그래밍 하는 것커널이 제공하는 기능을 직접 제공받으며 low-level에서 동작하는 프로그램을 작성하는 것커널이 제공하는 기능: 시스템 콜 주로 활용운영체제, 네트워크 파트에서 학습한 내용을 소스코드 레벨에서 관측해보자.타 프로그래밍 언어를 이용하더라도 공통적으로 사용될 시스템 프로그래밍 개념파일 입출력프로세스간 통신소켓 프로그래밍파일 디스크립터프로세스는 운영체제로부터 파일을 할당받는다. 이걸 어떻게 구분할 수 있을까?파일을 식별하기 위해 운영체제로부터 할당 받은 정보입출력장치, 파이프, 소켓도 파일 디스크립터로 식별마치 위에 장치들을 파일로 다룬다.일반적으로 0이상의 정수 형태프로세스가 파일을 열거나 생성할 때 운영체제는 해당 파일에 대한 파일 디스..
[코딩테스트] [1182] 부분수열의 합 & [2758] 로또 & [1208] 부분 수열의 합2
·
알고리즘/Recursion
[1182] 부분수열의 합시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초256 MB99180449482929243.323%문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.문제 풀이이 알고리즘의 문제풀이는 수열이 있을때 크기가 양수인 부분수열중에서 그 수열의 원소가 더한 값이 S가 되는 경우의 수를 구하..
[코딩테스트] [14267] 회사 문화 1 & [1068] 트리 & [5639] 이진 검색 트리
·
알고리즘/Recursion
[14267] 회사 문화 1시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초512 MB112084301323936.492%문제영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,입력첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤..
[코딩테스트] [11725] 트리의 부모 찾기 & [1991] 트리 순회 & [15681] 트리와 쿼리
·
알고리즘/Recursion
트리계층적인 자료구조그래프의 일종사이클이 비순환적 구조이다.최상위 노드를 루트로가 한다.노드트리를 구성하는 각각의 요소루트트리의 최상위 노드부모 노드어떤 노드의 바로 위 노드자식 노드어떤 노드의 바로 아래 노드리프자식 노드가 없는 노드서브 트리트리내 특정노드를 루트로 하는 트리레벨Level 1으로 하였을 때, 각 노드의 깊이[11725] 트리의 부모 찾기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB99818454693188243.170%문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두..
[코딩테스트] 재귀함수 & [15654~15657] N과M
·
알고리즘/Recursion
재귀함수자기 자신을 호출하는 함수를 재귀함수라고 한다.사용 이유하나의 커다란 문제를 작은 문제로 나누어 해결하기 위해서문제를 귀납적으로 생각하기 위해서귀납적 예시, {i}번째 답을 구하기 위해 (i-1), (i-2), … 번째 결과를 활용한다.예시숫자 출력오름차순과 내림차순을 재귀로 출력하는 방법을 봐 보자.아래 사진을 보면 재귀를 통하여 출력되는 것을 볼 수 있다.class Main { static class PrintNumber { public void asc (int n) { if (n==0) return; asc(n-1); System.out.println(n); } public void desc..
[코딩테스트] [10799] 쇠막대기 & [2504] 괄호의 값
·
알고리즘/Stack
[10799] 쇠막대기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB59085384942858665.295%문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위..
[코딩테스트] [4949] 균형잡힌 세상 & [2812] 크게 만들기
·
알고리즘/Stack
균형잡힌 세상시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초128 MB160431549434232032.936%문제세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.모든 괄호들의 짝은 1:1 매칭만 가..
[Computer Science] [정보처리기사] 소프트웨어 설계 & 계산 문제 해설
·
Computer Science/기타
정보처리기사 필기를 준비하며 간단하게 정리를 해봤다.소프트웨어 설계소프트웨어 생명 주기소프트웨어 생명 주기는 소프트웨어 개발 단계와 각 단계별 주요 활동, 활동의 결과에 대한 산춘물로 표현한다. 소프트웨어 수명 주기라고도 한다.소프트웨어 공학의 개념소프트웨어 공학은 소프트웨어의 위기를 극복하기 위한 방안으로 연구된 학문여러가지 방법론과 도구, 관리 기법들을 통하여 품질 및 생산성 향상을 목적폭포수 모형(Waterfall Model)폭포처럼 떨어진 물은 거슬러 올러갈수없다.각 단계에서 확실히 매듭짓고 그 결과를 철저하게 검토하는 승인 과정을 거친다.전통적인 소프트웨어 생명주기모형, 고전적 생명 주기 모형이라고 한다.프로토타입 모형프로토타입은 사용자의 요구사항을 정확히 파악하기 위해 개발된 소프트웨어에 대한..
[Swift] [Error Handling] Result Type
·
Swift/정리
ResultType In SwiftSwift에서 Result Type은 성공 혹은 실패로 끝날 수 있는 작업을 관리하기 좋은 Tool이다.예를 들어 네트워크 요청을 하는 함수를 실행한다면 실행 결과가 성공시 요청한 데이터를 캡슐화하고 실패시 오류를 캡슐화할 수 있다.Result Type을 사용하면 예상 경과를 보다 명확하게 정의할 수 있어 가독성과 유지보수성을 향상 시킬 수 있다.그래서 Swift에서 오류 처리를 개선하기 위해 도입이 되었다고 한다.Swift에서 Result Type은 성공과 실패 즉, 두가지 경우가 Enum 역할을 한다.성공은 성공 시 기대되는 값이 되고, 실패는 발생하는 오류 값이 된다.ResultType SyntaxSwift의 결과 유형은 기본적으로 해당 값으로 성공을 나타내거나 관..
[Computer Science] [네트워크] 전송 계층
·
Computer Science/Network
전송계층전송계층의 역할응용 계층의 어플리케이션 프로세스 식별 → 포트를 통해서 식별한다.네트워크 계층의 신뢰성/연결성 확립포트네트워크 계층은 A호스트와 B호스트 어디있는지 IP 주소를 토대로 식별할 수 있다. 하지만 B 호스트한테 패킷이 도달한 후 어떤 응용 어플리케이션에게 패킷을 줘야할지 알 수 없다.포트번호를 어떤 어플리케이션에게 패킷을 전달해야하는지 알려준다.어플리케이션 프로세스를 식별해주는 고유한 문자열16비트로 표현 가능 65536개포트 범위 : 0번부터 65535번까지웰 노운 포트, 시스템 포트,대중적인 포트HTTP, HTTPS 등 대중적인 프로토콜을 할당해주는 포트등록된 포트잘 알려진 포트에 비해서는 덜 범용적이지만 흔히 사용되는 애플리케이션동적포트, 사설 포트, 임시포트사용자가 자유롭게 할..
[코딩테스트] [1966] 프린터 큐 &[10866] 덱
·
알고리즘/Queue
[1966] 프린터 큐시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB87682509864012458.876%문제여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤..
[코딩테스트] [Queue] [10845] 큐 & [15828] Router
·
알고리즘/Queue
Queue먼저 넣은 데이터가 먼저 나오는 형태(선입선출)의 자료구조를 의미한다. (First - In - First - Out)가장 뒤에 원소가 추가되고, 가장 앞에 원소가 처리된다.예를 들어, 티겟팅 대기열, 프린터 출력, 운영체제 스케줄링, 메세지 큐 등Queue 역시 인터페이스로 구현 되어 있다.Linked list 기반의 Queueenqueue: addLast를 사용해 리스트의 가장 앞 원소를 추가한다. (push)dequeue: removeFirst를 사용해 리스트의 가장 앞 원소를 삭제한다. (pop)public class MyListQueue { private int size = 0; private Node frontNode = null; private Node rearNode = null;..