Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/1406 풀이 만약 시간제한이 없다면 간단하게 생각될 수 있는 문제이다. 각 명령어에 따라 조건문을 작성하고 string혹은 배열을 이용하여 명령어를 실행하면서 커서를 밀고 당기면서 문자열을 계속 새롭게 만들면 되기 때문이다. 나 같은 경우 string과 substr명령어를 사용해서 문자열을 계속 재배치했는데 역시 시간초과에 걸리고 말았다. 어떤 자료구조를 이용해서 이 문제를 효율적으로 풀어야할지 생각해내는 것이 이 문제의 핵심이다. 나는 stack자료구조를 썼는데 left스택과 right스택을 만들어 커서를 기준으로 왼쪽에 있으면 left 스택에, 오른쪽에 있으면 right스택에 문자들을 집어넣는다면 쉽게 풀 수 있다. 예를들어 ab..

문제링크 : https://www.acmicpc.net/problem/2606 풀이 같은 집합에 대해서 하나로 묶어주고 찾고자 하는것이 해당 집합에 포함되어 있는지 찾을 수 있는 유니온파인드 자료구조를 사용하였다. 자세한 방식에 대해서는 http://dolphins-it.tistory.com/223 를 참조하자. #include using namespace std; int computer[101]; int find(int x) { if (x == computer[x]) return x; else { int y = find(computer[x]); computer[x] = y; return y; } } void merge(int x, int y) { int a = find(x); int b = find(y..

문제링크 : https://www.acmicpc.net/problem/3015 풀이 정답률이 22%대로 낮은편이며 아주 골치아픈 문제이다. 일단 이 문제를 풀기위한 가장 깔끔한 방법은 새로운 사람이 줄을 설 때마다 처리해주는 식으로 문제를 푸는 것이다. 예를들어 2 1 4 순으로 줄을 서 있다고 해보자 맨 첫사람의 키인 2는 일단 스택에 넣어주고 키가 1인 다음사람을 처리해준다. 앞사람보다 키가 작아 앞사람이 다음사람을 보는데 문제가 없으므로 (1,2)의 짝만 나오기 때문에 최종답에 1을 더해준다. 키가 4인 다음 사람을 처리해 줄 때 키가 1인 사람은 더이상 사람을 볼 수 없으므로 (1,4)인 케이스, 그리고 pop을 해준뒤 키가 2인 사람도 더 이 사람보다 키가 작기 때문에 (4,2)인 케이스를 더해..

문제링크 : https://www.acmicpc.net/problem/3111 풀이 푸느라 상당히 시간이 많이걸린 문제이다 시간초과 , 출력초과가 빡치는 문제이다. 일단 나는 deque를 통해 코드를 작성했다. deque를 통해 앞에서부터 받을 때는 push_back을 통해 뒤에서부터 받을 때는 push_front를 통해 문자들을 받았다. 문자를 받을 때 마다 누적된 문제들이 검열하는 텍스트 A와 같은지 검사하며 front_index > a >> t; int front_index, last_index;//앞에서 부터 시작하는 index와 뒤에서 부터 시작하는 index; front_index = 0; last_index = t.size() - 1; //index의 위치 맨 처음과 맨 끝으로 조정 whil..

문제링크 : https://www.acmicpc.net/problem/1987 풀이 DFS를 통해 해결할 수 있는 문제이다. 이 때 이미 지난 알파벳을 지나지 않도록 해야하는데 이를 위해서 map을 이용해 이미 밟은 알파벳에 대해 표시할 수 있도록하였다. #include #include #include #include using namespace std; string arr[20]; bool check[20][20]; int move_x[] = { 1,-1,0,0 }; int move_y[] = { 0,0,-1,1 }; int r, c; int result = 0; map m; void dfs(int x, int y, int num) { check[x][y] = true; num++; m[arr[x][y..

문제링크 : https://www.acmicpc.net/problem/9663 풀이 재귀를 통해 가능한 모든 부분을 탐색하였다. int queen(int rows) 위와같이 줄 번호를 매개변수로 받는 함수를 통해 문제를 풀었다. 해당 행이 주어졌을 때 모든 열을 탐색하면서 만약 대각선, 세로에 다른 퀸이 서있지 않다면 bool형 배열에 그것을 체크한 뒤 result += queen(rows+1)을 하도록 했다. 이 함수는 rows = n이 됐을 때 (주어진 행을 모두 검사하고 초과된 경우) 1을 return하며 그렇지 않은 경우에는 result를 return하도록 하였다. 대각선을 검사하는 방식은 다음과 같이 하였다. 오른쪽 위에서 왼쪽 밑으로 향하는 대각선의 경우 행과 열의 index를 더해보면 다음과..

문제링크 : https://www.acmicpc.net/problem/9095 풀이 재귀를 이용해서 풀었을 때 간단하게 풀 수 있는 문제이다. 재귀함수의 매개변수로는 (현재까지 더해진 숫자, 나타내야하는 정수) 2개를 준다.-> func(int sum, int goal) 여기서 sum == goal이 될 때까지 func(sum+1, goal) ; func(sum+2, goal) ; func(sum+3,goal) 을 이용해서 뻗어나가고 만약 조건이 충족이 된다면 자연스럽게 그 경우의 수들은 처음 시작한 함수로 모일것이다. #include using namespace std; int func(int sum, int goal) { if (sum > goal) return 0; if (sum == goal) r..

문제링크 : https://www.acmicpc.net/problem/1525 풀이 이 문제의 핵심은 2차원 배열을 마치 1차원 배열처럼 생각하고 문제를 풀어야한다는 점이다. 이렇게 한 이유는 이차원 배열을 통해 bfs로 문제를 풀었을 때 이미 했던 경우의 수를 check하기가 까다롭기 때문이다. 만약 이차원 배열이 아니라 문제에 있는 이런 퍼즐을 193425786 (0은 9로 바꿔서 넣음) 으로 생각하고 문제를 풀 때 map을 이용하면 방문했는지 여부와 횟수가 어떻게 되는지를 동시에 알 수 있다. 아래의 코드와 주석을 보면 어떻게 풀었는지 이해할 수 있을것이다. #include #include #include #include using namespace std; int move_x[] = { 1,-1,..

문제링크 : https://www.acmicpc.net/problem/9019 풀이 전형적으로 BFS를 사용하는 문제이다. 처음에 이 문제를 풀 때 'L'연산과 'R'연산을 하는 과정에서 비효율적으로 코드를 짜서 문제해결에 성공하지 못했는데 'L'연산의 경우 int tmp = (x % 1000) * 10 + x / 1000; 'R'연산의 경우 int tmp = (x / 10) + (x % 10) * 1000; 이렇게 식 하나로 정리했더니 문제를 해결할 수 있었다. #include #include #include #include #include using namespace std; bool visit[10000]; char cmd[] = { 'D','S','L','R' }; int main() { int ..

문제링크 : https://www.acmicpc.net/problem/1963 풀이 어떻게 풀어야하나 고민을 많이 했는데 결론적으로는 큐를 이용해 일일히 다 검사하면서 문제를 풀었다. 먼저 해결해야 하는것은 4자리 수중에 소수들을 가려내는 작업이다. 이 작업은 에라토스테네스의 체를 이용하여 소수들을 선별해놓으면 편하다. 에라토스테네스의 체에 대해 자세히 모른다면 http://dolphins-it.tistory.com/105?category=771381 을 참조하자 아무튼 이러한 방식으로 소수를 판별했다면 자릿수 별로 숫자를 바꿔주면서 해당 자릿수의 숫자를 바꿨을 때 소수이면서 방문하지 않은 숫자라면 큐에 삽입해서 원하는 수가 나올 때까지 계속 반복해주도록 한다. #include #include #incl..