while(1) 작심삼일();

http://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이) 방문하지않았던 곳이면 dfs 돌려서 전부 방문처리해주고 구간값 1개 더하는 식으로 처리를 했고, 두번째 dfs에선 기본 값들 다시 초기화 시키고, G -> R로 바꿔놓고 다시 한번 전과 같은 방식으로 dfs를 돌려서 해결했다. #include #include using namespace std; int N, ans = 0; int visited[101][101]; int dirX[4]..

http://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이) 각 좌표에 퀸을 놓을 수 있는지 확인만 해주면 된다. 열은 확인할 필요가 없고, 위랑 왼쪽대각선, 우측대각선만 확인을 해주면 된다. 해당 자리에 값을 넣을 수 있다면, 방문처리를 해놓고 dfs를 이어나가면 되고, 끝나면 다시 방문처리를 false로 원래대로 돌려놓으면 된다. #include using namespace std; int N, ans = 0; int map[16][16]; int position..

http://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이) (여담으로 학교 알고리즘수업때 시험문제로도 나왔었던 문제이다.) 앞선 문자열들의 결과가 존재해야 해당 순간에 맞는 가장 긴 값을 dp배열에 저장할 수 있기 때문에 dp는 (1, 1)배열부터 시작한다. 부분 문자열A와 부분 문자열B를 비교한다고 했을 때, 2가지 경우를 기준으로 dp에 값을 채울 수 있다. 1) 부분 A문자열의 마지막 인덱스값과 부분..

http://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이) 뱀의 몸에 닿으면 게임을 끝나는 조건을 설정할 때, 처음에 queue로 진행하려했으나, stl에서 자체적으로 제공하는 iterator가 없어서 linkedlist를 직접 구현하는 방식으로 진행했다. 구현문제였기때문에 문제에서 요구한 절차에 따라 방향에 따른 이동 -> 게임종료 조건 확인 -> 사과 먹은 유무에 따른 몸 길이 재 설정 -> 현 시간이 방향을 바꾸어야 하는 시점인지 확인으로 진행했고, ..

http://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 풀이) N의 범위를 보아, 반복문이 두번 돈다면 시간초과가 난다는 사실에서 스위핑 알고리즘이 떠올랐고, 우선 값들을 정렬을 했다. 시작점이 작고, 끝점이 큰(같은 시작점 기준 가장 긴 선분)을 앞쪽으로 오게 정렬을 한 다음, 스위핑 알고리즘을 이용하여, start, end를 잡아서 구간으로 검색을 하여 나올 수 있는 가장 긴 선분을 지속적으로 더해주고, 중간에 겹치지 않..

http://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이) 자원 측면에서 vector를 사용하였고, 특정 노드에 방문했을 때 갈 수 있는 노드들을 거리가 최소가 된다면 갱신하는 방식으로 구현하였다. #include #include #include using namespace std; int N, M, start, finish; int dist[1001]; vector graph[1001]; queue q; int d..