본문 바로가기

알고리즘/java5

[stack] 백준 1874 스택수열 문제____________문제스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다.스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다.이를 계산하는 프로그램을 작성하라.1부터 N까지 오름차순으로 스택에 push를.. 2024. 7. 31.
[슬라이딩 윈도우] 백준 12891 Dna 비밀번호 문제/* 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다.DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다.예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다.이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다.임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다.그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들.. 2024. 7. 29.
[투포인터] 백준 1940 주몽 문제주몽은 철기군을 양성하기 위한 프로젝트에 나섰다.그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다.야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다.갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면갑옷이 만들어 지게 된다.야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다.이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오. 조건첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다... 2024. 7. 27.
[투포인터] 백준 2018 수들의 합 5 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다.당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은15,7+8,4+5+6,1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은10,1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오. 시간제한 : 2초  자연수 N의 최대 크기가 천만이기 때문에, O(nlogn)의 복잡도를 가지는 알고리즘도 N이 천만일 때 약  2억3천 번의 연산이 필요하기 때문에 위험해 보인다. 따라서 O(n)의 시간복잡도를 가지는 방식으로 해결해.. 2024. 7. 24.
[백준] 구간 합 4 문제시간 제한 : 1 초문제 :수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력 :첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다.셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력 :총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.예시입력 :5 35 4 3 2 11 32 45 5예시 출력 :1291제한 범위 :1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N  제한 범위는  N과 M이 100000이하 이므로, 최악의 경우 모든 배열의 원소 n개의 합을 m번 구하게 된다면,100000 x 1.. 2024. 7. 23.

티스토리툴바