개발하는 사막여우

https://www.acmicpc.net/problem/14659 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.net 소스코드 풀이 ★ python3으로 제출했을 때 50%에서 시간초과가 발생하였습니다. 그렇기에 pypy로 제출한 코드입니다 ! ★ 배열 안의 원소 하나를 나머지 원소들과 대소비교해줍니다. - for i in range(n): for j in range(i+1,n): 만약 해당 수가 배열 안의 수보다 크다면 용을 처치할 수 있는 봉우리에 있기 때문에 cnt를 ..

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 소스코드 풀이 ★ 문제를 해결하는 과정에서 몇가지 경우를 생각해줘야 합니다. 먼저 입력받은 세트와 낱개의 가격을 각각 리스트에 추가하고 해당 리스트의 최솟값을 변수로 설정해줍니다. 1. 세트의 가격이 낱개 가격으로 6개 사는 것보다 비싼 경우. 이 경우일 떈 끊어진 줄 수가 몇개인지에 상관없이 무조건 낱개로 사는 게 싸기 때문에 결과값에다 n*낱개 가격을 해줍니다. 2. 위의 경우가 아니면서 ..

https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 소스코드 풀이 ★ 알고리즘 분류 중 '구현'에서 이 문제를 봤고, 선입선출 구조를 가지고 있는 큐를 사용하여 문제를 풀었습니다 ★ 1부터 n까지의 수가 들어있는 큐와 버리는 수들을 저장하는 배열 k를 만들어줍니다. n-1만큼 반복을 하면서 큐에서 2개의 수를 leftpop 합니다. 그 수 중 처음오는 수는 버리는 수이기 때문에 k에 저장하고 두번째 수는 큐의 맨 뒤로 append 해줍니다. ★ 반..

https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 소스코드 풀이 ★ 문제를 봤을 때 승률(z)이 변하는 최소 게임 수를 구하라고 했는데, 승률이 오르는 경우 뿐만 아니라 내리는 경우도 있지 않나 싶어서 조금 헤맸던 거 같습니다. ★ 승률 k를 구하는 과정에서 소수점 이하를 내림 처리 해주는 math 모듈의 trunc 함수를 사용하였습니다. 처음엔 k = m.trunc((y/x)*100)으로 승률을 구했는데 정답 처리가 계속 오답으로 떠서 ..

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 소스코드 풀이 ★ 딕셔너리를 사용하여 입력받은 배열 안의 수가 몇번 나오는지 확인해줍니다. ex) a = [1,1,2,3,4,2,1] => {1: 3, 2: 2, 3: 1, 4: 1} ★ 정답을 저장하는 배열 ans는 -1로 초기화 하는데, 만약 해당 수의 오등큰수가 없다면 -1이 출력되어야 하기 때문입니다. ★ 입력받은 배열을 읽으면서 stack의 최상단의 값이 딕셔너리 안에 가지고 있는 수가 해당 값의 수..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 소스코드 풀이 ★ 정렬된 리스트 a의 시작부분과 끝부분을 투포인터로 잡고, 그 값들을 더한 값이 0에 가까운 수들을 찾아줍니다. lt가 rt보다 작을 때만 반복문을 도는 이유는 문제에서 n개의 용액들 전부 특성이 다르기에 중복되는 수가 없기 때문입니다. ★ 투포인터를 더한 절대값(mid값)이 ans보다 작으면 그 값이 0에 가장 가까운 값이 됩니다. 만약 mid ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 소스코드 풀이 ★ 입력으로 주어진 m개의 수를 가지고 있는지 없는지 판단하기 위해 이분 탐색을 합니다. 먼저 a를 오름차순으로 정렬한 뒤 시작점(lt), 끝점(rt)를 0과 n-1로 설정합니다. ★ b의 원소들에 대해 반복문을 돌면서 x와 mid값을 인덱스로 가지고 있는 a의 값이 같다면 숫자를 가지고 있는 것이기에 1을 출력하고, while문이 break없이 정상적..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 소스코드 - 자료형 - 이분탐색 풀이 ★ 이번 문제는 자료형을 사용하거나 이분탐색을 사용하는 방식으로 해결할 수 있는 문제입니다. 먼저 자료형 set을 사용하면 입력받은 a리스트에서 중복된 수가 제거되고 값들을 정렬한 형태로 반환합니다. b 리스트를 돌면서 in을 활용하여, 해당 수가 a에 들어있다면 1을, 없다면 0을 출력합니다. ★ 이분탐색을 위..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 소스코드 풀이 ★ k개를 제거하여 가장 큰 수를 만들어야 하기 때문에 수들을 stack에 넣어가며 대소비교를 해줘야 합니다. stack 안에 들어있는 값보다 비교하려는 값이 더 작다면 그 수는 stack에 들어올 수 없습니다. ★ for문을 돌면서 stack이 비어있지 않고, 제거해야 하는 갯수인 k가 0보다 크다면 stack의 최상단 값과 반복문을 도는 값의 크기 비교를 해줍니다. 만약 stack안에 있는 값이 작다면 pop으로 제거해주고, k또한 -1 해줍니다. 크다면 ..

https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 소스코드 풀이 ★ 입력받은 문자열의 문자들을 stack에 추가하면서 stack의 뒤에서 두번째 글자부터 끝까지의 글자가 ['A','A'] or ['B','B']일 경우 그 문자열은 좋은 단어이기 때문에 삭제해주는 과정을 진행합니다. ex) ABBA stack = ['A'] stack = ['A','B'] stack = ['A','B','B'] => 'B','B' pop 되고, cnt += 1 stack =[..