목록Algorithm (35)
Over the limit
1. 문제 풀이에 도움되는 함수 없이 (ord,chr 없이) def encrypt(value, padding): s = "abcdefghijklmnopqrstuvwxyz" b = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" answer = '' for char in value : for j in range(len(s)): if char==s[j]: index=j+padding answer+=s[index%26] elif char==b[j]: index=j+padding answer+=b[index%26] else: answer+='' return answer def decrypt(value, padding): s = "abcdefghijklmnopqrstuvwxyz" b = "ABCDEFGHIJK..
오늘 문제는 그리디 알고리즘이다. 문제를 풀기 전에 그리디 알고리즘(Greedy Algorithm)이 뭘까를 쉽게 알아보고 가자. 그리디 알고리즘은 말그대로 탐욕 알고리즘! 최적의 답을 선택하는 과정을 반복하여 적합한 결과를 도출한다는 것이 그리디 알고리즘이다. 즉 큰 틀, 미래를 생각하지 않고 각 단계를 보아 무엇이 최선의 선택일지 판단하고 도출하면 되는 것이다. 이 문제는 동전 개수의 최솟값을 구하는 프로그램을 작성하고 있다. 여기서 그리디 알고리즘을 적용하면, '최솟값'을 위해서 액수가 큰 가치를 먼저 탐색하면 되는 것이다. 익히 본 문제들을 푸는 과정과 비슷해보이지만, 액수가 큰 가치를 먼저 활용하기 위해서 for문을 역순으로 활용하는 정도라고 생각하면 된다. import java.util.Sca..
Iterator 란? Iterator란 자바의 인터페이스이다. 기능은 다양한 집합체(Map, List, Set)으로부터 정보를 얻어내는 것이다. Iterator 객체는 컬렉션 개체의 iterator() 메서드를 호출하여 얻어올 수 있다. 사용가능 객체 ArrayList arr = new ArrayList(); Vector vec = new Vector(); Iterator 객체 얻기 Iterator it0 = arr.iterator(); Iterator it1 = vec.iterator(); +) while문을 통해 객체 얻기 (하단의 Iterator 메소드 이용) while(it0.hasNext()){ String st=(String)it0.next(); } for문을 통해 객체 얻기 for(Membe..
문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..
문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N number return 5 1..
수 정렬하기 2 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 256 MB 130126 34530 23507 30.029% 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 복사 5 5 4 3 2 1 예제 출력 1 복사 1 2 3 4 5 문제풀이 이 문제를 읽고 2750과 다른 것은 무엇일까 크게 다를 것은 없지 않을까 생각했다면 경기도 오산이다. 많이 사용하는 버..
문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. 출력 입력으로 주어진 숫자 N개의 합을 출력한다. 예제 입력 1 복사 1 1 예제 출력 1 복사 1 11720번: 숫자의 합 (acmicpc.net) 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 두번째 줄은 n글자가 올 수 있는 상황이다. 이때 이를 String 으로 받게되면 어떻게 String을 만든 숫자들을 각각 나눌 수 있는가? 이때는 JAVA의 '뽑기' String.charAt..
문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 5 5 2 3 4 1 예제 출력 1 1 2 3 4 5 2750번: 수 정렬하기 (acmicpc.net) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc...
시간 복잡도란? 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 문제를 풀다보면 실행시간안에 알고리즘이 마치지 않았다고 정답으로 체크하지 않는 경우를 볼 수 있다. 따라서 시간 복잡도를 잘 체크하여 문제를 풀어야 한다. 빅오 표기법 원하는 답이 나오지 않는다면 최대 얼마만큼의 시간이 걸릴까를 측정하기 위해 사용하는 것이 빅오 표기법이다. (Big-O) 입력데이터(n)에 따라 어떤 결과가 나올지, 각각의 함수를 통해서 알 수 있다. 시간 복잡도의 대표적인 종류 1 : 입력자료의 수에 관계없이 일정한 실행시간 갖음 Log N : 입력자료의 수에 따라 시간이 조금씩 증가함 - 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형 ex)이진 탐색 N : 입력 자료의 수에 따라 ..
문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[..