17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 시간초과로 상당히 고생한 문제. 처음 내가 풀었던 방식은 아래와 같다. 3이 있으면 우측으로 쭉 읽으면서 3보다 큰수가 나오면 break를 걸도록했다. 이렇게 하면 2중 for loop를 사용하게 되는데 worst case의 경우 n!이 나온다. 따라서 이렇게 풀면 당연히 시간초과. 결국 풀다가 백준님 강의를 듣고 아래의 소스코드로 정답을 맞췄다. 해당 문제를 시간내 통과하기 위해서 Stack을 사용했다. 3 5 2 7이라는 숫자가 있다면 먼저 0(숫자3의 인덱스)을 Stack..

2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수를 구하는 여러방법이 있는데 가장 유명한것은 유클리드 호제법. 단번에 이해되는 예시도 있으니 아래의 백과사전을 참고하자. 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 � ko.wikipedia.org 최대공약수를 먼저 구하면 최소공배수는 쉽게 구할 수 있다. 이유는 최대공약수와 최소공배수는 아래와 같은 관계..

2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이�� www.acmicpc.net 문제 이해하는데 한참 걸렸다. 책좀 더 읽어야겠다. 아래 코드처럼 모든경우의 수를 다 확인하는 방법으로 풀었다. 입력은 대문자만 된다고 했으니 대문자 32개를 입력받을수 있도록 했다. ( length가 32인 list에 0으로 초기화 ) 대문자는 아스키코드 65부터 시작하니까 입력받은 문자를 65로 나눈 나머지가 0이면 A, 나머지가 1이면 B 이런식으로 처리했다. 그후 구성이 같은지, 문자를 하나 뺐을때 같은지, 문자를 하나 더했을때 같은지, 기존 문자 ..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net { 1, 2, 1, 4, 3, 2 }라는 순열이 있을때 구할수 있는 증가 부분 수열이 몇가지 존재한다. 예를들면 [1 2] , [1 4], [1 2 3] , [1 2 4] 같은것들이다. 좌측부터 수를 뽑되(순열) 반드시 증가해야하며(증가) 주어진 순열내에 있는 숫자(주어진 순열의 부분)로 이뤄져있다. 위의 예시같은 경우는 3이 가장긴 부분 수열이다. ( [1 2 3] 또는 [ 1 2 4..

코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 �� programmers.co.kr 생각보다 신경써줘야 할게 많아서 힘들었다. 반례(테스트케이스) 관련 링크는 제일 하단에 있다. 나는 먼저 key를 장르, value를 장르 재생횟수의 총합으로 가지는 HashMap을 만들었다. ( genres_sum ) 그리고 max_genres라는 함수를 통해 현재 genres_sum에서 가장 재생횟수가 많은 장르를 return 하도록 했다. 이제부터 while을 돌며 앨범을 만들면된다. max_genres함수를 통해 가장 재생횟수가 많은 장르를 가져왔..

https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린�� programmers.co.kr 내가 원하는 출력물이 몇번만에 출력되는지 계산하는 문제다. 그냥 꺼내면 좋겠지만 각 출력물은 우선순위가 부여되어있다. 먼저 prior에 우선순위 정보를 넣고, loc에 위치 정보를 넣었다. prior의 0번째 출력물을 하나 꺼내고 prior에 남아 있는 값들 중에 내가 꺼낸 출력물 보다 우선순위가 높은게 없다면 출력하면 된다. 만약 있다면 제일 후 순위로 다시 ..