알고리즘/프로그래머스(30)
-
[프로그래머스] [C++] 조이스틱
1. 문제 조이스틱을 다음과 같이 조작하여 AA...A 에서 이름을 기록하는 최소의 조작 수를 구하여라 위 = 알파벳 다음글자 (Z->A) 아래 = 알파벳 이전 글자 (A->Z) 왼쪽 = 커서 왼쪽으로 (맨 왼쪽 => 맨 오른쪽) 오른쪽 = 커서 오른쪽으로 (맨 오른쪽 => 맨 왼쪽) 2. greedy 이문제는 그리디로 푸는 문제가 아닌것같지만 그리디 항목에 있어서 그리디로 풀었다. 그리디는 최소임을 보장하지 않는다. "CANAAAAANAN" 의 경우 최소는 48이지만 그리디한 방법 현재상태에서 최선을 선택하면 49가 나온다고한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..
2021.03.16 -
[프로그래머스] [C++] 소수 찾기 (brute-force)
1. 문제 0~9로 이루어진 문자열이 주어진다. 적절히 자르고 붙여서 중복되지 않은 숫자를 만드는 경우의 수 중 소수인 숫자들의 개수를 구하여라. 2. 에라토스테네스의 체와 브루트 포스(dfs) 일단 나올 수 있는 최대 숫자까지 모든 숫자에대해 소수인지 아닌지 판별하여 전역 변수에 기록하였다. 이것은 에라토스테네스의 체의 알고리즘으로 소수를 판별하였다. 그 후 입력으로 주어진 문자열을 가공하여 0~9의 개수를 담은 배열을 만들었다. 이렇게 배열을 만들고 dfs를 하게되면 한번의 실행에 0~9를 탐색하지만 중복된 숫자를 따로 처리하지 않을 수 있다. dfs로 다른 숫자들을 붙여나가며 소수인지를 판별해나가며 개수를 카운트한다. 3. 코드 아쉬운점: 함수명을 dp로 한점 1 2 3 4 5 6 7 8 9 10 ..
2021.03.16 -
[프로그래머스] [C++] N으로 표현 (dp)
1. 문제 이 문제는 N 과 number가 주어진다. 이때 N은 1~9 의 수이며 11, 222, 3333, 33 , 444, 8 등과 같이 N을 여러개 이어붙인거에 덧셈 곱셈 뺄셈 나눗셈하여 number를 만드는 최소 N의 개수를 구하는 문제이다. 2. 문제 변형 주어진 N을 x라 할때 다음과 같은 배열을 만들어 조합탐색해나가면 문제를 해결할 수 있다. [ x, xx, xxx, xxxx, xxxxx, xxxxxx, xxxxxxx, xxxxxxxx ] 이 배열 원소들이 그래프의 정점이라고 가정하고 간선은 연산이라고 생각하여 dfs를 돌리면 답을 얻을 수 있다. 이때 그래프의 형태는 한정점에서 한정점까지 4개의 방향간선이 뻗어나가, 간선의 개수가 많아진다. 이를 암시적 그래프 형태로 표현하여 간선을 신경쓰..
2021.03.15 -
[프로그래머스] [C++] 디스크 컨트롤러 (heap)
1. 문제 디스크에 작업요청이 들어온다. 이때 작업이 들어오는 시간과 수행되는 시간이 주어질 때 모든 작업의 요청부터 종료까지의 최소 평균을 구하여라. 2. 최소 힙, 그리디 증명 이 문제는 그리디한 방법으로 해결할 수 있다. 무조건 실행할 수 있는 작업중에서 가장 수행시간이 짧은것을 수행하는 것이다. 이것의 증명은 다음과 같이 할 수 있다. 만약 수행할 수 있는 작업 a , b, c, d 가 있다고 하자 이때 만약 작업시간이 가장 긴 a를 수행하게 되면 시작시간과 상관없이 b, c, d 가 기다리는 시간이 a의 긴 수행시간을 더해서 기다려야하기 때문에 전체 평균은 증가할 수 밖에 없는 것이다. 반대로 만약 작업시간이 가장 짧은 b를 수행하게 되면 나머지들의 대기시간도 짧아지고, 전체 평균은 이것을 선택..
2021.03.11 -
[프로그래머스] [C++] 주식가격 (stack)
1. 문제 초단위로 기록된 주식 가격이 주어질때 가격이 떨어지지 않은 기간은 몇 초인지를 계산하여라 기록은 다음 기록이 있을시 1초가 지났다는걸 의미한다. 2. 스택 사용 모든 원소를 탐색하면서 스택에 넣는다 단, 스택에 넣기전에 top 보다 만약 해당 가격이 낮을 시 pop해주고 스택에 저장한 인덱스 벙보를 활용하여 몇초가 지났는지 파악한다. 이때 기록배열에 -1을 넣으면 자연스럽게 마지막 원소까지 해결된다. (단 -1일때 len의 길이는 -1 해줘야한다. 임의로 들어간 원소이기 때문이다.) 3. 코드 이것은 처음 제출한 코드인데, 인덱스 0을 따로 스택에 먼저 넣지 않아도 잘작동한다. 즉, 필요없는 코드를 작성했다는 것 이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..
2021.03.11 -
[프로그래머스] [C++] 전화번호 목록 (trie)
1. 문제 전화번호 목록이 주어진다. 주어진 목록에서 다른 전화번호가 접두사인 전화번호가 있는지 없는지 찾아내는 프로그램을 작성하여라 2. TRIE 이 문제는 트라이로 문제를 해결할 수 있다. 트라이는 문자열의 각각 문자로 이루어진 트리이다. 문자열을 집어넣고 트리를 만들어나갈때 만약 새로운 트라이 노드를 만들지 않거나 (접두사로 포함되는 문자열을 삽입한 경우) 진행하던중 종료점이 있을경우 (접두사로 가지는 문자열을 삽입한 경우) 두 경우 만 찾으면 된다. 3. 코드 이것은 좋지 못한 코드이다. 소멸자에 delete 하는 과정이 없고 쓸모없는 number라는 코드가 있기 때문이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..
2021.03.10