호지

펄스 수열은 두 종류가 있다 [-1, 1, -1...] , [1, -1, 1...] sequence가 주어지면 -1로 시작하는 펄스 수열과 곱해진 s1배열, 1로 시작하는 펄스 수열과 곱해진 s2배열 두가지로 나누어 생각했다. 가장 쉽게 생각할 수 있는 풀이방법은 DFS로 모든 경우의 수를 탐색하는 방법이었다. (하지만 이 방법은 시간 초과이다.) 다음으로 생각해본 방법은 DP이다. 모든 경우의 수를 탐색하면 이미 더했던 부분수열을 다시 더하고 하는 중복과정이 계속 발생한다. 또한 부분수열은 연속해서 이어지는 일렬의 과정이므로 for문 한번으로 해결할 수 있을 것 같았다. 과정은 s1과 s2를 나누어서 계산을 했다. cnt1과 cnt2는 dp배열로, i번째 위치의 의미는 해당 위치에서 나올 수 있는 부분..

BFS를 이용한 문제풀이입니다. 주어진 board에서 robot의 위치를 먼저 구합니다. 로봇은 상하좌우 방향으로 움직일 수 있고, 한 방향으로 움직이다가 장애물 D를 만나거나 board에 끝에 도달할때까지 움직입니다. 로봇이 움직일 수 있는 위치는 list큐에 넣습니다. 움직일 수 있는 위치 여부는 상하좌우(moves배열) 방향을 다 확인하고 한번 방문한 위치는 board를 C로 표기하여 중복 방문을 막습니다. list 큐가 empty면 G에 도달하지 못한 것이므로 -1을 반환하고, 중간에 G에 도달하면 해당위치의 count를 반환합니다. #include #include #include using namespace std; int solution(vector board) { int answer = -1..

카테고리가 해시인걸 봐선 해시로 푸는 문제인듯하지만 정렬이 훨씬 빠를 것같아서 정렬로 문제를 풀었다. phone_book을 정렬하면 인접한 데이터만 확인하면 접두사인지 확인할 수 있다. 따라서 정렬 후 phone_book을 탐색하여 phone_book.substr(0,x.size())와 x가 같다면(접두사) answer를 false로 바꾸고 탐색을 종료하면 된다. #include #include #include using namespace std; bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); string x = phone_book[0]; for(int i=1; i

S, L, R로 채워진 grid가 주어졌을때, 사이클이 있는가 탐색하는 문제이다. grid의 최대값은 500이므로 char형 배열 board[500][500]을 선언하고, 각 방향에 대해 방문했는지 확인을 위해 int형 배열 moves[500][500]을 선언하였다. 각 위치에서 가능한 방향은 상하좌우 총 4가지이므로 비트마스크를 통해 방문확인을 한다. 위(0001), 오른쪽(0010), 아래(0100), 왼쪽(1000) 각 방향은 mx,my 배열에 저장되어있다. (↑→↓←) find함수는 이미 진행한 방향을 만나기전까지 경로를 계속 진행하며 탐색하고,(while문) 이미 진행한 방향을 만났을 때의 위치가 시작점이면서,(x==start_x, y==start_y) 처음 방향과 동일하다면(d==start_d..

주어진 문제에서 튜플의 원소는 중복이 없다. 따라서 특정 튜플을 표현하는 집합이 주어졌을때, 모든 숫자에 대해 몇 번 사용되었는지 확인하면 가장 많이 사용된 숫자가 튜플의 시작이고 가장 적게 사용된 숫자가 튜플의 끝이다. 따라서 문자열을 탐색하면서 숫자는 map자료구조에 넣고(map의 first는 숫자, second는 개수) 이후 map을 전체 탐색하여 pair를 갖는 vector에 값을 넣는다. vector list를 pair.second(개수)의 내림차순으로 sort하면 pair.first를 확인하여 튜플을 구할 수 있다. #include #include #include #include using namespace std; bool cmp(pair p1, pair p2){ if(p1.second > ..

스택을 이용하여 문제를 풀었다. 먼저 주어진 string을 숫자와 연산자로 구분하여 vector에 push_back한다. 연산자는 {+,-,*}를 각각 0,1,2로 바꾸어 저장하였다. 가능한 경우의 수는 최대 3!=6개로 DFS로 재귀를 돌리는 것보다 미리 가능한 경우의 수를 p배열에 만들어 놓고 사용하는 게 효율적이다. count_op로 사용된 연산자 개수를 저장했고, count_op가 1일 때는 p배열의 0번 index만 탐색한다. count_op가 2일때는 p배열의 0번, 1번 index를 탐색한다. 0번은 {0,1,2} 1번은 {2,1,0}이므로 사용된 연산자가 0,1/0,2/1,2일 때 1,0/2,0/2,1을 모두 탐색할 수 있다. 연산자를 저장할 스택 op와 숫자를 저장할 스택 num이 있다...

문제를 조금 더 깔끔하게 푸는 법을 연습해야겠다. 모든 대기방에 대해서 거리두기를 확인하는 문제이다. 확인할 경우는 총 3가지이다. 1. 상하좌우로 2칸 떨어진 곳에 P가 있으면 사이에 파티션이 있는가 (없으면 거리두기X) P X P X P X P X P 2. 대각선에 P가 있으면 그 사이에 파티션이 2개 있는가 (없으면 거리두기X) P X P X P X P X P 3. 상하좌우 1칸 떨어진곳에 P가 있는가 P P P P P find함수에서 위 3가지 조건을 확인하여 거리두기가 확인되면 1, 거리두기가 아니면 0을 반환한다 * 상하좌우에 +2를 추가하여 room[5][5]가 아닌 room[9][9]를 전역변수로 선언하였다.(범위 확인 X) #include #include using namespace st..

stack을 이용하면 된다. stack에 원소를 push하면 짝일 경우는 해당 원소가 stack의 top인지 확인하면 되므로, 짝이면 stack에서 pop하고 아닐 경우 stack에 push하면 마지막에 stack이 비어있다면 짝지어 모두 제거가 된 것이고 아니라면 남아있는 원소가 있다는 것이다. #include #include #include using namespace std; int solution(string s) { int answer = 0; if(s.size() % 2 == 1) return answer; stack st; for(int i=0; i