방배동 고구마

논리문제는 아이디어를 내기까지가 상당히 까다롭다. 결국 많은 경험이 필요하다. 다음 문제를 보자 문제 N*N의 영역이 주어진다.(N : 2~10000) 해당 영역에 먼지가 떨어져 있다. 청소를 단 한번 할 수 있다. 청소 구역의 둘레 길이 L(4~100이며 짝수이다)이 주어진다. 먼지의 개수는 M(1~100)으로 주어지며 먼지의 X,Y좌표값이 주어진다. 주어진 L의 조건에서 청소 시 가장 많이 제거할 수 있는 먼지의 갯수를 구하라 입력 6 10 6 2 2 4 6 5 2 6 4 2 4 3 3 출력 4 접근방법 주어진 케이스는 아래와 같다. 청소영역 둘레가 10이라 청소영역 가로세로 2*3 조합도 가능하고 1*4 조합도 가능하다. 아이디어를 생각해본다. 1) 간단하게 N을 기준으로 모든 영역을 수행한다. N..

[문제] N*N(N : 4~ 10) 크기의 도화지에 색종이를 붙인다. 색종이는 직사각형 모양이다. 이때 겹쳐 붙일 수 있다. 색종이는 숫자 1부터 9까지 나타나며 빈 도화지는 0으로 나타낸다. 가장 많이 겹쳐진 지점의 색종이 수를 구하라. [입력] 4 1591 1496 1444 0550 [출력] 4 [접근방법] 주어진 입력을 그림으로 표현하면 아래와 같다. 앞선 덧칠 문제와 굉장비 비슷한 접근 방법이다. 1. 색깔 별로 minX, minY, maxX, maxY의 값을 구한다. for문으로 탐색하여 좌표별 최고 최소 값을 구하면 될것이다. 2. 구한 좌표를 저장해둔다. 구조체 배열을 사용하면 편리하겠다. 3. 저장된 좌표값을 차례로 visit 배열에 count올린다. 4. visit배열에 가장 큰 값을 찾..

문제 꼬리잡기 게임을 한다. 일직선 상에서 진행하며 모두 동시에 출발하지만 출발 위치와 속도는 다르다. T분동안 게임이 진행되며 일직선 상이기 때문에 추월할 수 없고 속도가 빠른 뒷사람의 앞사람의 꼬리를 잡으면 하나의 그룹으로 인식된다. 주어진 조건에서 몇개의 그룹이 형성되는지 구하라 입력 참가자 수 N : 1~100,000 게임시간 T : 1~1,000,000,000 각 참가자출발 위치 P : 0 ~ 1,000,000,000 각 참가자 속도 S : 0 ~ 1,000,000,000 ※ 출발위치는 오름차순으로 입력됨 5 3 0 1 1 2 2 3 3 2 6 1 출력 3 접근방식 아주 간단하게 생각해보자. 1. 각 참가자의 계산된 T분 후 위치를 구한다.2. 뒷 사람이 앞사람보다 위치가 클 경우, 앞사람의 위..

Greedy 알고리즘은 모든 경우의 수에 대해 수행하지 않는다. 즉, 모든 문제에 Greedy를 적용할 수는 없다. 최선의 선택을 해가다 보면 최종적인 해답이 나온다는 개념이다. 예를 들어 10원, 50원, 100원 짜리가 있고 160원을 만든다고 할때, 최소의 갯수로 만든다고 하자. 최소의 갯수로 만들기 위한 최선의 선택은 큰 동전 부터 사용해가는 것이다. 즉, 100원 1개 / 50원 1개 / 10원 1개, 총 3개가 답이 되겠다. 그러나 120원짜리 동전이 있다고 가정해보자. 이때 역시 큰 동전부터 선택하게 되면 120원 1개 / 10원 4개로 총 5개를 선택하게 된다. 즉 오답이다. Greedy알고리즘은 모든 경우에 적용할 수 없다. 120원짜리 동전의 선택이 적용되지 않는 이유는 100원짜리 동..

문제 주어지는 노드사이에는 최대 1개의 도로가 있으며 양방향 도로이다. 도로에는 가중치가 있으며 노드간 이동시에는 최단 경로로 이동한다. N, 노드 수 : 5~100 M, 도로 수 : 5~5000 D, 노드 사이의 거리 이때 각 노드를 출발점으로 할때 도착 노드까지의 거리가 가장 먼 거리를 X라고 하자. 노드 중의 X가 가장 작은 X의 값을 구하라 입력 N과 M이 입력되며 노드A와 노드 B 사이의 거리 D가 아래와 같이 입력된다. 5 7 1 2 5 3 2 14 2 4 5 1 3 10 4 3 15 5 4 15 3 5 8 출력 15 입력을 그래프로 표현하면 위와 같다. 접근방식 서로 다른 가중치가 있는 맵이므로 BFS로 접근이 유효하다. BFS는 크게 2가지 종류가 있는데, 가중치가 서로 다른 경우와 가중치..

문제 주어진 지도에서 1구역, 2구역이 주어진다. 1구역에서 2구역으로 상하좌우 한칸씩 이동할 수 있다. 1구역에서 2구역으로 갈 수 있는 최단 거리를 구하라. 입력 N은 행, M은 열이며 map이 0과 1로 구분되어 입력된다. 0은 이동경로이며 1은 구역을 의미한다. 6 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 출력 4 접근방법1 1. map 전체를 탐색하여 1구역을 DFS로 확산하며 좌표를 저장한다..

문제 빵을 먹고 가장 체중이 증가한 경우를 구하라 1. 빵은 N개이며 최대 150000개 이다. 2. 빵에 써있는 숫자가 있다. 3. 첫번째로 먹으면 빵의 숫자만큼 체중이 는다. 4. 두번째로 먹으면 빵의 숫자만큼 체중이 준다. 인풋 8 7 2 1 8 4 3 5 6 아웃풋 17 접근방식 DFS, BFS 접근 방식은 N의 갯수가 너무 크기때문에 불가하다. 시간복잡도 O(N제곱) DP로 접근해야한다. DP : 부분문제의 최적화된 결과를 이용하여 전체문제를 해결하는 방식의 알고리즘 다이나믹 테이블과 점화식이 필요하다. 다이나믹 테이블 : 전체 문제 및 부분 문제의 결과를 기록할 수 있는 테이블 점화식 : 부분문제를 일반화시켜서 수식으로 표현한것 아이디어 1) 홀수번째는 증가하는 빵이기 때문에 최대값으로 만들려..

문제 N, R, P 각각의 인풋이 주어진다. N은 필름의 개수이고 R과 P는 필름의 특성값이다. R은 곱의 성능, P는 합의 성능이라고 할때 R과 P의 차이값이 최소인 경우가 가장 필름화면의 성능이 우수한 경우이다. 주어진 N개의 필름에서 최적의 성능을 위해 제거할 필름의 최대갯수를 구하라 입력 4 2 10 2 8 3 4 4 12 출력 1 문제해결 모든 경우의 수를 조합하는 것이다. 모든 경우의 수는 조합이며 조합은 즉, DFS로 접근 가능하다. DFS를 조합으로 나타낼때 다중트리나 이중트리로 접근한다. 다중트리는 노드를 중심으로, 이중트리는 노드의 방문 혹은 선택여부를 중심으로 판단한다. ※ 재귀함수 추적시 확인점 0. 함수 Call되어 Stack caller에 쌓인 경로 1. Code에 의해 Retu..

문제 N*N 크기의 map이 있음 Input으로 map 크기에 맞는 cost가 들어옴 (0,0) 부터 (N-1,N-1) 까지 가는 최소비용을 구하라 입력 N은 2이상 100이하의 자연수이다. 3 041 253 620 Output 8 문제해결 더보기 DFS는 모든 경우의 수이다. 시간복잡도가 오래걸릴 수 있다.BFS를 이용하여 최소의 경우를 구할 수 있다. 단 중복방문을 무조건 허용하지 않고 이전 비용보다 좋을때 허용할 수 있도록 한다. DFS로 최초 풀이해보았으나 N이 커지면 Timeout이 났다. 모든 경우의 수이기때문에 시간복잡도가 매우 높을 것이다. #include int N; char map[100+10][100+10]; int visit[100+10][100+10]; int dx[4] = {1,..

문제 N*N 크기의 도화지에 1~9의 색을 칠한다. 이때 직사각형 모양으로 색칠한다. 매번 다른색을 칠하며 영역을 완전히 침범하지 않는 선에서 덧칠을 할 수 있다. 이때 덧칠되지 않은 색은 몇개인지 구하라. input (도화지 크기, 색정보) 4 1230 1737 1777 0220 output 2 접근방법 1. 색영역은 무조건 직사각형이다. 색 영역의 min, max 꼭지점 좌표를 구한다. 2. 색영역을 탐색하며 해당 색 영역에 침범된 다른 색을 Checker 배열에 count한다. 3. Checker배열에서 다른 영역을 침범하지 않은 색의 갯수를 구한다. #include int N; char paint[12][12]; void input(){ scanf("%d",&N); for(int i=0; i

문제 1. N개의 건물 높이가 주어진다. (최대 80000) 2. 건물옥상에서 좌에서 우측 방향으로만 바라볼 수 있다. 3. 높이가 같거나 높으면 옥상을 볼 수 없다. 4. 이때 옥상을 볼 수있는 최대의 합을 구하라 접근 N의 갯수가 최대 8만이기 때문에 i번째 건물'이' 볼 수 있는 옥상을 이중 루프로 비교 탐색을 수행할시 시간복잡도는 O(N제곱)이다. 때문에 시간이 초과될 수 있다. i번째 건물'을' 볼 수 있는 건물을 탐색해야한다. 시간 복잡도 O(N). 1. i번째 건물을 볼 수 있는 건물을 스택에 저장한다. 2. i+1번째 건물을 볼 수 있으면 pop하지 않는다. 3. i+1번째 건물을 볼 수 없다면 pop한다. 스택에 있는 전체 건물 후보에 대해 2,3을 판단한다. 4. 스택에 남아있는 건물 ..

난 컴공이라고 하기엔 애매한 학부를 졸업했다. 해서 알고리즘등과 같은 전산학 이론에 다소 취약하다. 그래도 꾸준하게 공부하고 정리해가다 보면 빠삭해지지 않을까. 어찌되었건 오늘은 N queen을 공부해보았다. 사실 이전에 풀은 기억이 있고 그때 풀었던 코드를 다시 봤는데 내가 풀었는데 이해가 안간다. 그래서 다시 차근차근 살펴보았다. N queen. 알고리즘의 Backtracking을 다룰때 매우 빈번하게 등장하는 아무 유명한 문제이다. 문제는 간단하다. 문제 "N*N의 Table에서 체스unit Queen N개가 서로 공격하지 않게 놓일 수 있는 경우의 수" 예를 들어 N=4일때, 4개의 Queen이 놓일 수 있는 경우는 아래와 같다. 주요 아이디어 1. 퀸의 특성상, 한 행에 하나의 퀸만 있을 수 있..