[1182] 부분수열의 합시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초256 MB99180449482929243.323%문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.문제 풀이이 알고리즘의 문제풀이는 수열이 있을때 크기가 양수인 부분수열중에서 그 수열의 원소가 더한 값이 S가 되는 경우의 수를 구하..

트리계층적인 자료구조그래프의 일종사이클이 비순환적 구조이다.최상위 노드를 루트로가 한다.노드트리를 구성하는 각각의 요소루트트리의 최상위 노드부모 노드어떤 노드의 바로 위 노드자식 노드어떤 노드의 바로 아래 노드리프자식 노드가 없는 노드서브 트리트리내 특정노드를 루트로 하는 트리레벨Level 1으로 하였을 때, 각 노드의 깊이[11725] 트리의 부모 찾기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB99818454693188243.170%문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두..

재귀함수자기 자신을 호출하는 함수를 재귀함수라고 한다.사용 이유하나의 커다란 문제를 작은 문제로 나누어 해결하기 위해서문제를 귀납적으로 생각하기 위해서귀납적 예시, {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..

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;..

[17609] 회문시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초 (추가 시간 없음)512 MB315558988663429.094%문제회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는..

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초128 MB221546761462529.061%문제현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우..

[11659] 구간 합 구하기 4누적합 배열이 어떻게 사용되는지 문제를 풀어보며 이해해보자.시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB138676567894147038.443%문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.제한1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N문제풀이이 문제는 수 N개가 주어 졌을 ..

행운의 바퀴시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초128 MB93722424171723.798%문제상덕이는 최근에 행운의 바퀴를 구매했다. 상덕이는 바퀴의 각 칸에 알파벳 대문자를 아래 그림과 같이 적었다.바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 또, 바퀴는 시계방향으로만 돌아간다. 바퀴 옆에는 화살표가 있는데, 이 화살표는 항상 한 곳을 가리키고 있으며, 돌아가는 동안 가리키는 글자는 바뀌게 된다. 위의 그림에서는 H를 가리키고 있다.상덕이는 바퀴를 연속해서 K번 돌릴 것이다. 매번 바퀴를 돌릴 때 마다, 상덕이는 화살표가 가리키는 글자가 변하는 횟수와 어떤 글자에서 회전을 멈추었는지를 종이에 적는다.희원이는 상덕이가 적어놓은 종이를 발견했다. 그 종이를 바탕으로 상덕이가 ..

회문인 수시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB47662414200154.331%문제어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 수를 표현할 때 쓸 수 있는 수의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다.입력입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T..

성지키기문제영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.입력첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다.출력첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다.문제풀이1. 각 행과 열에 경비원이 있는지 확인하기일단 2차원 배열로 N*M으로 구성된 칸을 만들어보자 그리고 경비원을 넣어주어 ..

단어 공부문제알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.입력첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.출력첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.문제 풀이문자열을 대문자로만 입력 받기Scanner 클래스와 next() 메서드를 사용하여 문자열을 입력 받는다.import java.util.Scanner Scanner sc = new Scanner(System.in); String input = sc.next().toUppe..

코딩테스트 준비JAVA로 코딩테스트를 준비하기로 하였다.JAVA만 코딩테스트를 보는 회사가 많다. 내 시장성 가치를 올리기 위해 수요가 많은 시장을 선택한다.추후 안드로이드 개발도 관심이 있는데 코틀린이 자바와 완전한 상호운용이 가능하고 구문 전환이 용이하므로 자바 개발자에게 매력적이라고 한다.공부는 인터넷 강의에 나와있는 백준 문제대로 풀이를 하고 하루에 한 번씩 같이 코딩테스트를 공부하는 스터디원분과 손코딩으로 작성하며 문제풀이를 설명하는 방식이다.[2744] 대소문자 바꾸기문제영어 소문자와 대문자로 이루어진 단어를 입력받은 뒤, 대문자는 소문자로, 소문자는 대문자로 바꾸어 출력하는 프로그램을 작성하시오.입력첫째 줄에 영어 소문자와 대문자로만 이루어진 단어가 주어진다. 단어의 길이는 최대 100이다...

분류자료 구조, 구현, 큐제출 일자2024년 5월 22일 00:49:48문제 설명요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)출력예제와 같이 요세푸스 순열을 출력한다...

분류자료 구조, 스택, 문자열 제출 일자2024년 5월 13일 16:13:21 문제 설명괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “..

분류구현, 문자열 문제 설명문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다. 출력각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다. 문제풀이방법1. T수 만큼 명령 수 입력2. 문장 입력 받은 후 문장안 공백 마다 분리하기3. 분리한 문장들을 뒤집어주기4. 뒤집은 문장을 출력하기