현수쓰

이진 탐색 (BinarySearch)이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 동작방식중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다. 배열의 중간 값을 가져옵니다. 중간 값과 검색 값을 비교합니다. 중간 값이 검색 값과 같다면 종료합니다. (mid = key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid < key) 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > key) 값을 찾거나 간격이 비어있을 때까지 반복합니다. 시간복잡도 Operation Best Average Worst Search O(1) Θ(log n) O(log n) ...

우선순위 큐 (Priority Queue)큐 (Queue))큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조입니다. 우선순위 큐 (Priority Queue)우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조입니다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현합니다. 우선순위 큐는 리스트와 연결리스트로 구현 가능합니다. 하지만 리스트의 경우 data가 많아 질 경우 데이터를 우선순위에 기반해 전체 비교를 거쳐 알맞은 자리를 찾고, 그 자리에 넣기 위해 전체 자료를 밀어내야합니다. 연결리스트의 경우 또한 data가 많아 질 경우 노드간의 연결을 거쳐 모든 노드에 접근하여 비교연산을 해야합니다. 이는 비용이 매우 크기 때문에 일반적으로 우선순위 큐는 Heap을 가지고 구현합니다. 힙 (Heap)힙(Heap)은 우선순위 큐를 위해 고안된 ...

카카오프렌즈 컬러링북문제출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.) 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자. 위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다. 입력 형식입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다. 1 <= m, n <= 100 picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다. picture의 원소 중 값이 0인 경우는 색칠하지 않는 영 ...

크레인 인형뽑기 게임문제게임 화면은 “1 x 1” 크기의 칸들로 이루어진 “N x N” 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 “5 x 5” 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 “1 x 1” 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다. 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 ...

전산회계 공부참고URL 회계?회계란 기업에 관한 유용한 경제적 정보를 일정한 원리에 따라 기록/계산/정리/분석하여 회계 정보 이용자가 합리적인 의사결정을 내릴 수 있도록 이들에게 식별/측정/전달하는 모든 과정을 말한다. 회계의 분류 부기 : 장부 부 기록할 기 = 장부에 기록한다. 단식부기 : 현금의 수입/지출만 기록 복식부기 : 현금 뿐만 아니라 현금 이외 항목도 원인과 결과 기록(오류검증) 영리부기 : 영리를 목적(상업부기, 공업부기, 농업부기, 은행부기) 비영리부기 : 영리를 목적으로 하지 않음 (학교부기, 가계부기, 관공서부기) 회계 : 모일 회 꾀 계 = 경영(투자) 계획을 수립한다. 재무 회계(Financial Accounting) : 기업 외부이용자(투자자, 채권자, 정부)에게 정보를 작성하여 제공할 목적으로 이루어지는 외부보고 목적의 회계 관리 회계(Management Accounting) : 기업 내부이용자(경영자)에게 정보를 작성하여 제공할 목적 ...

추석 트래픽문제이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 1차답안123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.util.*;import java.text.*;class Solution { public int solution(String[] lines) { HashMap<Integer,Integer> seconds = new HashMap<Integer,Integer>(); ...

오픈채팅방문제카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.[닉네임]님이 들어왔습니다. 채팅방에서 누군가 나가면 다음 메시지가 출력된다.[닉네임]님이 나갔습니다. 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 제한사항 record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다. 다음은 record에 담긴 문자열에 대한 설명이다. 모든 유저는 [유저 아이디]로 구분한다. [유저 아이 ...

키패드 누르기문제스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 1 2 3 4 5 6 7 8 9 * 0 # 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니 ...

숫자 문자열과 영단어문제네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다.다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다. 1478 → “one4seveneight”234567 → “23four5six7”10203 → “1zerotwozero3” 이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요. 참고로 각 숫자에 대응되는 영단어는 다음 표와 같습니다. 숫자 영단어 0 zero 1 one 2 two 3 three 4 four 5 five 6 six 7 seven 8 eight 9 nine 풀이123456789101112131415161718import java.util.*;c ...

신규 아이디 추천문제카카오에 입사한 신입 개발자 네오는 “카카오계정개발팀”에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. “네오”에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다.다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다.아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다.단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다. “네오”는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는 지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천해 주려고 합니다.신규 유저가 입력한 아이디가 new_id 라고 한다면, 예 ...