BASIC의 개발 노트

문제 해석 단계별로 풀어보기의 큐, 덱 파트에서 가장 어려운 문제이다. 문제를 요약하면 입력으로 R이 들어오면 정수 배열을 뒤집어야하고, D가 들어오면 배열의 첫 번째를 버리는 작업을 해야한다. D가 들어올 때 마다 하는 동작은 먼저 들어온 값을 먼저 내보내는 큐에서의 pop()과 동작이 같다. 이렇게 함수를 실행하고 남은 결과를 출력하는 문제이다. 시행착오 이 문제는 처음 봤을 때 골드 5티어 라고 하기에는 너무 간단해보였다. 떠오른 생각대로 알고리즘을 구현하고 제출했더니 시간 초과를 받았다. 단순히 배열을 사용하거나 python의 deque 라이브러리를 사용한다고 하더라도 R을 문제에서 유도한 방식대로 처리하지 않는다면 시간 초과를 받을 수 밖에 없을 것이다. 그 이유는 Reverse를 수행하면 원소..

단계별 풀이 중 스택에 있는 가장 고난이도 문제이다. 스택 분류에 있는 문제라서 스택을 써야한다는 점을 알고 문제에 접근했지만 처음에는 스택 없이도 풀 수 있을 것 같다는 생각에 스택을 사용하지 않고 시도했다. 하지만 어김없이 시간초과를 받아버렸고.. 내가 짠 코드를 보니 O(N^2)으로 동작하는 코드였다. N이 1,000,000 까지 들어오기 때문에 시간초과를 받기 쉬운 코드였다. 시간초과인 이유는 간단하다. 만약 입력이 1 1 1 1 1 1 1 . . . 2 이런식으로 들어올 경우 오큰수를 찾기 위해 최악의 경우인 제일 끝에 있는 2를 계속해서 찾아야한다는 점에서 효율성이 상당히 떨어진다. 이걸 모든 1에 대해서 반복해야하니 1이 많을수록 오래걸릴 수 밖에 없다. 이렇게 이중반복문과 투포인터까지도 사..

단어 수학은 주어진 알파벳들에 대하여 각각의 알파벳을 0 ~ 9의 숫자로 하나씩 대응 시켰을 때 그 합이 최대가 되도록 하는 문제이다. 이해를 돕기 위해 한 가지 예시를 들어보면, 입력으로 ABCD와 EFG가 들어왔을 때 둘의 합을 최대로 만드는 경우를 생각해보자. 가장 먼저 떠오르는 방법은 위 그림처럼 알파벳에 값을 부여하는 방법이다. 즉 높은 자리수에 높은 숫자를 대응 시키면 최대에 가까운 값을 얻을 수 있을 것이다. 가장 높은 자리수를 가지고 있는 A에 가장 높은 숫자 9, 그 다음으로 높은 자리 수인 B, E에 각각 8과 7 .. 이런 식으로 숫자를 부여하도록 코드를 구현하고 제출했는데 오답 판정을 받았다. 무엇이 문제였을까.. 고민하고 찾아보던 도중 한 가지 예제에서 문제점을 확인 할 수 있었다..

주어진 카드 묶음들을 비교하는데, 이 비교 횟수가 최소가 되는 값이 무엇인지 구하는 문제이다. 문제 조건에 따르면 비교할 때는 A 묶음과 B 묶음이 있을 때 합쳐서 하나로 만드는데 A+B번 비교를 해야한다. 문제 예시를 활용하면 10, 20, 40이 있을 때 10과 20을 합치면 30번의 비교가 필요하며 이렇게 될 경우 30과 40만이 남게 되고 30과 40을 다시 합치면 70번의 비교가 필요해서 총 100번의 비교를 하게 된다. 만약 순서를 바꿔서 10과 40을 먼저 합치고 비교할 경우 100번 보다 많은 횟수가 나오게 된다. 가장 최소 횟수로 비교하기 위해서는 정렬해서 작은 수끼리 비교하고 이 값을 누적해 나가야 한다. 누적해 나가는 값을 최솟값으로 만드는 것이 최소한의 비교 횟수가 되는데 다시 이 ..

신입 사원은 입력으로 들어온 지원자들의 성적을 보고 선발 할 수 있는 최대 인원 수를 계산하는 문제이다. 중요한 조건은 성적으로 서류심사 순위와 면접시험 순위가 입력으로 주어지는데, 어떤 지원자의 성적 순위가 다른 지원자의 성적 순위에 비해 서류, 면접 순위가 모두 떨어질 경우 선발 대상에서 제외된다. 예를 들어서 A의 성적 순위가 각각 1, 3 B의 성적 순위가 각각 2, 1 C의 성적 순위가 각각 3, 2 라고 했을 때, C의 성적은 A랑 비교했을 때 두 번째 성적에서는 우위에 있지만, B랑 비교했을 때는 첫 번째, 두 번째 성적 모두 순위에서 밀린다. 이럴 경우 C는 선발 대상에서 제외되는 것이다. 우선 입력 조건에서 N이 100,000 까지 들어올 수 있기 때문에 O(N) 또는 O(NlogN)으로..

주유소는 각 도시별 리터당 가격과 거리를 고려했을 때 최소 비용을 계산하는 문제이다. 핵심은 가장 리터당 가격이 낮은 도시를 찾아서 남은 거리만큼 필요한 기름을 모두 구매하고 해당 도시까지 가는데 필요한 기름 구매 비용의 최솟값을 합산하면 된다. 이 문제를 풀면서 몇 가지 실수를 했었는데 먼저 채점 결과를 보면 다음과 같다. 처음 코드를 구현하고 나서 17점을 받았을 때 뭐가 문제인지 한참 헤맸던 것 같다. 알고보니 예제 입력을 테스트 케이스로 코드를 구현하다보니 최소 비용이 드는 도시는 한참 뒤에 있음에도 앞에서 그 비용을 모두 계산해버린 것이다. 즉 최소 비용이 드는 도시까지 가는 비용을 생각하지 못했다... 다시 코드를 수정하고 최소 비용이 드는 도시까지 가는 비용 + 해당 도시에서 남은 거리만큼의..

주어진 로프가 버틸 수 있는 최대 중량으로 들어올릴 수 있는 최대 중량을 구하는 문제이다. 모든 로프를 사용하지 않아도 되며 몇 개의 로프만 골라서 사용해도 된다. 문제에서 각 로프에 걸리는 중량은 모두 w/k 만큼이라고 했기 때문에 선택된 로프가 버틸 수 있는 중량은 이 값보다는 커야한다. 몇 개의 로프를 선택하냐와 어떤 로프를 선택하냐에 따라서 들어올릴 수 있는 최대 중량은 달라진다. 예를 들어서 로프가 버틸 수 있는 최대 중량으로 10, 3, 6이 주어졌다면 3개를 모두 선택한다면 수식은 w/3이 되고 이 값은 버틸 수 있는 최대 중량의 최소치인 3을 넘길 수는 없기 때문에 들어올릴 수 있는 최대 중량은 3 * 3 = 9가 된다. 하지만 만약 2개를 선택하는데 10, 6만 고른다고 했을 때, 수식은..

잃어버린 괄호는 +, - 만을 사용한 식에서 괄호를 사용하여 최솟값을 만드는 문제이다. 최솟값을 만드는 핵심은 - 기호가 나왔을 때 그 뒤에 오는 숫자를 가장 크게 만드는 것이다. 숫자를 가장 크게 만들고 그 앞 뒤를 괄호로 감싸게 되면 큰 수 앞에 -가 붙기 때문에 최솟값으로 볼 수 있다. 하지만 - 가 한 개가 아니라 여러 개가 나올 경우도 생각해봐야한다. 이 때는 다음 - 가 나오기 전까지를 괄호로 감싸면 된다. 그러면 다음 - 가 나오기 전까지 숫자를 계속 최대로 만들 수 있기 때문에 한정적인 최댓값을 계속해서 - 값으로 누적시켜 나갈 수가 있다. 예를 들면 0-100+20-100+20-100 이라는 식에서 처음 - 이후를 괄호로 감싸게 되면 0-(100+20-100+20-100) 가 되고 결과 ..

처음에는 각 회의 정보를 회의 시간(시작 시간 - 끝난 시간) 기준으로 정렬해서 문제를 풀었었다. 하지만 오답 처리 되었고 반례를 찾아본 결과 회의 시간이 적다고 해서 무조건 최대로 배정할 수 있는게 아니었다. 반례로 1, 7 / 7, 10 / 6, 8 정도를 들어볼 수 있다. 회의 시간이 제일 적은 것은 6, 8 지만 6, 8를 선택하는 대신 1, 7과 7, 10으로 2개의 회의 시간만큼을 배치할 수 있다. 따라서 회의 시간 대신 끝나는 시간 순으로 오름차순 정렬을 해서 문제를 풀었다. 하지만 그래도 자꾸 시간 초과되는 문제가 있었는데 N이 100,000 까지 들어올 수 있는 문제에서 O(n^2)로 코드를 구현했기 때문이었다. 기존 O(n^2) 코드는 별도에 리스트를 두고 선점한 회의 시간을 표기하는 ..

Internet network layer는 host, router 모두 network layer 기능을 구현하고 있어야 한다. 다양한 routing protocols, IP protocol, ICMP protocol 등이 존재한다. IP datagram format ----------------------------------------------------------------------------------------------------------------------------- version | header length(기본 20바이트 + options에 따라 늘어남) | type of service | length(total datagram length) ---------------------..