프로그래밍에 대한 고찰 및 생각

전략 N의 최대크기는 100만이므로 배열이 주어졌을 때 한명한명 맨 앞 또는 맨 뒤로 전부 보내보는 것은 불가능해 보인다. 따라서 다른 전략이 필요할 것 같았다. 이런 문제처럼 감이 잘 안올 때에는 간단한 예제를 통해서 대략적인 전략을 찾아야 한다. 먼저 문제에서 주어진 예제를 먼저 보자. 예제의 입력에 대해서 답을 도출하는 과정은 위와 같다. 이 예제에서 주목한 부분은 "움직인 숫자" 와 "움직이지 않은 숫자" 였다. 아래와 같이 구분하면 좀 더 보기 쉬울 것이다. 2와 3은 그대로 두었고 5,4,1은 앞 또는 뒤로 옮겼다. 왜 2,3은 두고 5,4,1만 옮겼을 때 최소의 움직임이 되는지를 고민해보았다. 이 예제만으로는 감이 잘 안올 수도 있어 다른 예제를 하나 더 살펴보자. 위 예제의 경우 1,2,6..

투 포인터 알고리즘(Two Pointer Algorithm) 투 포인터 알고리즘은 선형자료구조에서 특정부분집합을 빠르게 찾아낼때 사용된다. 예를 들어 다음 문제를 보자. 백준 1806번 - 부분합 위 문제같은 경우 N = 100000 일때 모든 부분합의 개수는 N^2 으로 많은 시간이 소요된다. 그렇다고 메모이제이션을 하기에는 부분합인 S의 범위가 1억이하이므로 메모리상으로도 초과가 발생한다. 이때 사용할 수 있는 알고리즘이 투 포인터 알고리즘 이다. 다음과 같은 배열에서 합이 10이상이되는 가장 짧은 길이를 구해보자. 먼저 우리가 찾을 부분배열의 시작 인덱스를 start, 마지막 인덱스를 end라고 하자. 처음에는 두값모두 0이다. 이후 현재 부분배열의 합이 S(10) 이상이 아니라면 end++ 하여 ..

유명한 Greedy 알고리즘 - 회의실 배정 문제 회의실 배정 문제는 그리디 알고리즘에서 빠지지 않고 등장하는 문제이다. 이문제는 각 회의마다 시작시간과 종료시간이 정해져있고 하나의 회의실에 대해 가장 많은 회의를 진행하게 하고 싶을때 그 개수를 구하는 문제이다. 이 문제에서의 최종 목표는 최대한 많은 회의를 진행시키는 것 이다. 여기서 조건은 회의마다 시작시간과 끝나는시간이 정해져있다는 것과, 두 회의간 겹쳐서는 안된다는 점이다. Think1. 가장 짧은 회의들 먼저 진행시키면 되지않을까? 굉장히 Greedy한 접근법이다. 최대한 많은 회의를 진행시키려면 결국 회의시간이 짧은 회의들을 골라서 넣는것이 최적의 해를 만들어 줄것같다. 과연 그럴까? 위와같이 a~g까지 7개의 회의들이 있다고 가정해보자. 여..

탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘(이하 그리디)은 어떤 문제를 해결할때 모든 경우의 수를 전부 고려하지 않고 항상 최적이 되는 것만 골라서 진행해나가는 알고리즘을 의미한다. 모든 경우의 수를 전부 고려해서 최적의 해를 계산해내는 dynamic programming과는 다르다. 그렇다면 두가지 의문이 들수있다. 1. 항상 최적의 해만 골라서 탐색하면 지금까지 왜 dynamic programming으로 모든 경우의 수를 분석했나? 왜냐하면 그리디 알고리즘으로 모든 문제를 해결할 수 있는것이 아니기때문이다. 현재 상황에서는 가장 최적의 해라고 생각했지만 이후에 상황에 따라 그때의 선택이 최선의 결과를 만들지 않을수도 있기때문이다. 2. 그렇다면 그리디 알고리즘은 최선일수도 있고 아닐..

이 문제에서 핵심이 되는 부분은 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 이 부분이다. 이 말을 다르게 해석하면 결국 만약 자신이 일반인이라면 자신의 모든 친구들이 얼리어답터여야 함을 의미한다. 또한 만약 자신이 얼리어답터라면 자신의 친구가 일반인이던, 얼리어답터이던 중요하지 않다. 모두 가능하다. 정리하자면 얼리어답터 -> 얼리어답터 or 일반인 일반인 -> 얼리어답터 따라서 이것을 이용해 한정점에서 시작해 DFS로 순회하면서 위의 조건을 통해 최소의 얼리어답터 수를 구할 수 있을것이다. 만약 위와같은 트리로 전체적인 흐름을 파악해보자. 1번 정점부터 DFS를 수행한다고 할때 1번 정점에서 가능한 경우는 다음과 같이 두가지이다. 최종답은 두 경우중..

1. 오일러 서킷 ( 한붓그리기) 오일러 서킷이란 한 정점에서 시작해서 모든 간선을 지나 시작 정점으로 돌아오는 것을 의미한다. 2. 오일러 서킷의 조건 정점들과 간선들이 주어졌을때, 해당 자료에서 오일러 서킷이 존재하는지 판단하려면 어떻게 해야할까? 오일러 서킷이 되기위한 2가지 조건은 다음과 같다. 1. 모든 간선들이 하나의 컴포넌트에 속해야한다. 2. 각 정점마다 간선의 수가 짝수개여야한다. 그 이유에 대해 하나씩 알아보자. 2-1. 모든 간선들이 하나의 컴포넌트에 속해야한다. 위와같은 경우 각 컴포넌트별로는 오일러서킷이 존재하지만, 전체 정점들로 보았을때는 컴포넌트간 순회 할 수 없기때문에 반드시 모든 간선들이 하나의 컴포넌트에 속해야한다. 2-2. 각 정점마다 간선의 수가 짝수개여야한다. 각 정..

1. 문제이해 주어진 정점과 간선으로 그래프를 만들었을때 서로 이어져있는 그래프의 집합이 몇개인지를 구하는 문제이다. 2. 알고리즘 전략 문제 자체는 간단하지마 한가지 고려해야 할 사항은 그래프를 표현할때 다음과 같이 1. 2차원 배열로 나타낼수도 있고 2. 벡터를 사용하여 정점과 그 간선의 연결상태만 나타낼 수 있다. 위 문제의 경우 정점의 개수가 최대 1000개 이므로 배열의 크기는 1000*1000*4byte(int)로 약 400MB정도 되어 문제에서의 최대 메모리인 512MB보다는 작지만, 아마 프로그램 실행을 위한 기본 메모리값으로 인해, 최대 메모리인 512MB를 넘어 메모리초과가 발생한다. 따라서 벡터를 이용해서 각 정점들과 이어진 정점들만 넣어 구현하고, 1차원 배열을 만들어 방문한 정점은..

1. 문제 이해 경찰차 문제는 (1,1), (n,n) 에 위치한 경찰차 두대가 w개의 사건들을 가장 짧은 거리를 이동하여 처리하는 문제이다. 주의해야할 부분은 한 경찰차가 하나의 사건을 처리한후 다시 원래자리로 돌아가는 것이 아니라 그 자리에서 다음사건을 처리하게 되고, 사건들은 같은 장소에서 여러번 일어날 수 있다는 점이다. 2. 알고리즘 전략 먼저 문제의 예시를 통해 시나리오를 분석해보자. 경찰차는 (1,1) 그리고 (6,6)에 위치해있고 3개의 사건이 분포되어있다. 만약 첫번째 사건을 처리한다고 가정해보자. 위와같이 1번 경찰차가 6칸을 이동하여 1번 사건을 처리할수도 있고, 2번 경찰차가 4칸을 이동하여 1번 사건을 처리할수도 있다. 그렇다면 총 몇번 시도를 해봐야 모든 경우의 수를 다 탐색해 볼..