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개의 방향간선이 뻗어나가, 간선의 개수가 많아진다. 이를 암시적 그래프 형태로 표현하여 간선을 신경쓰..

1. 문제 디스크에 작업요청이 들어온다. 이때 작업이 들어오는 시간과 수행되는 시간이 주어질 때 모든 작업의 요청부터 종료까지의 최소 평균을 구하여라. 2. 최소 힙, 그리디 증명 이 문제는 그리디한 방법으로 해결할 수 있다. 무조건 실행할 수 있는 작업중에서 가장 수행시간이 짧은것을 수행하는 것이다. 이것의 증명은 다음과 같이 할 수 있다. 만약 수행할 수 있는 작업 a , b, c, d 가 있다고 하자 이때 만약 작업시간이 가장 긴 a를 수행하게 되면 시작시간과 상관없이 b, c, d 가 기다리는 시간이 a의 긴 수행시간을 더해서 기다려야하기 때문에 전체 평균은 증가할 수 밖에 없는 것이다. 반대로 만약 작업시간이 가장 짧은 b를 수행하게 되면 나머지들의 대기시간도 짧아지고, 전체 평균은 이것을 선택..

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..

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 ..

1. 문제 n개의 노드가 있는 그래프 => 각 노드는 1부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고한다. 가장 멀리 떨어진 노드란 최단 경로로 이동햇을 때 간선의 개수가 가장 많은 노드를 의미한다. 노드의 개수 n은 2 이상 20,000이하이다. 간선은 양방향이며 총 1개이상 50,000개 이하의 간선이 있다. vertex 배열 각 행 [a, b] 는 a번 노드와 b번 노드 사이에 간선이 있다는 의미이다. 2. 너비우선 탐색 그래프의 최단거리를 구하는 방법은 여러가지가 있다. 그 중 한점을 기준으로 하는 탐색방법은 bfs O(|V| + |E|)를 이용하는것과 bfs에 우선순위큐를 활용한 다익스트라 O(ElgV) , 간선을 기준으로 업데이트하여 구하는 벨만 포드 O..

1. 문제 사용할 수 있는 숫자들과 타겟 넘버가 주어진다. 사용할 수 있는 숫자들 모두 사용하여 타겟넘버를 만들어라 단, 이때 연산은 +, - 만 가능하다. 2. 핵심 이 문제의 핵심은 사용할 수 있는 숫자들 모두를 사용하는 것이다. 처음에는 순서도 포함하여 세는줄 알았지만 순서는 필요없다는 것 그냥 숫자를 사용하기만 하면된다는 것이다. 모든 숫자를 사용해야하므로 재귀를 통해 모든 숫자를 탐색하면서 + 이나 - 를 해주며 마지막 숫자일때 타겟넘버와 동일한지 검사한다. 이는 dfs형태로 이루어지며 혹시모를 겹치는 부분을 대비하여 dp 를 적용시킬 수 있다. (실제로 테스트 1 과 테스트 2의 경우 시간이 빨라진다.) 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..