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

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

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

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번 사건을 처리할수도 있다. 그렇다면 총 몇번 시도를 해봐야 모든 경우의 수를 다 탐색해 볼..

문제 이해 토마토 문제에서는 각 박스내에 3가지 상태가 존재한다. 익은 토마토(1), 안익은 토마토(0), 비어있는 칸(-1). 주의할 점은 익은 토마토는 자신의 상하좌우에 위치한 토마토만을 익힐 수 있고, 비어있는칸이 존재할 수 있기때문에, 문제의 예제2 처럼 모든 토마토를 전부 익힐 수 없는 상황이 주어질 수도 있다는 점을 고려해야한다. 알고리즘 설계 문제에서 주어진 예제3의 경우를 시각화했을 때의 모습이다. 간단하게 생각해보면, 1. 현재 익은토마토(1)의 상하좌우의 토마토들의 상태를 1로 바꾼다. 2. 현재 익은토마토들 주변에 익힐수 있는 토마토가 없을 경우 종료 / 아닐 경우 1 반복 로 표현할수 있다. 그런데 현재 익은 토마토의 개수는 매번 달라지므로 일반적인 재귀함수로 표현하기는 힘들것 같다..

알고리즘 설계 문제에서 주어지는 n명의 그림 소유상태를 비트마스킹으로 표현하고 DP를 이용해서 해결할수 있는문제이다. 만약 비트연산을 처음 들어봤다면 비트연산을 먼저 공부하고 오는 것을 추천한다. 전체 코드는 다음과 같다. #include int n; int pp[16][16]; int dp[15][32768] = {0}; int ddp(int state, int before, int price); int max(int x, int y); int main(){ int i,j; scanf("%d",&n); for(i=0;i

문제이해 N개의 높이가 다른 블록들로 높이가 같은 두개의 탑을 쌓는데 그 탑의 높이가 최대일때의 그 높이를 구하는 문제이다. 단, 모든 블록을 사용할 필요가 없다. 알고리즘 설계 만약 블록을 쌓을때 구역 a와 b에 쌓아서 두개의 탑을 만든다고 할때 각 블록마다 1. a에 쌓는다 2. b에 쌓는다 3. 둘다 쌓지않는다 ( 사용하지 않는다 ) 3가지 경우가 있다. 여기서 한가지 정해놓고 갈 부분. 위 그림은 블록 4개로 탑을 쌓는과정중 일부인데 두 상황이 좌우에 누가 더 높냐만 다르지 25와 30으로 두 상황에서 두 탑의 높이가 동일하다. 따라서 함수를 진행하면서 a구역을 두 탑중 높은 탑, b구역을 두 탑중 낮은 탑으로 진행을 하게될것이고 해당 변수는 l ( large )과 s ( small )이다. 따라..

문제이해 이 문제는 집합에서의 기본적인연산 ( 원소의 추가, 삭제, 확인, 반전, 전체 변경, 전체 삭제 등) 을 수행하는 알고리즘을 설계하는 문제이다. 다만 수행해야하는 연산의 수가 최대 3,000,000 이므로 배열연산보다는 비트마스크를 활용해서 문제를 해결해야할것이다. 알고리즘 설계 사실 비트마스크를 사용해본적이 있다면 쉽게 해결할수 있을것이다. 집합의 원소개수가 1부터 20까지 20개 이므로 한개의 int에서 20bit를 사용해서 n번째 원소가 채워져있으면 2^(n-1) 에 해당하는 부분을 1로 아니라면 0으로 채워서 현재 집합의 상태를 표현할수 있다. #include #include int ss = 0; int bit(char ar[], int k); int main(){ int n,i,j; c..