호지

펄스 수열은 두 종류가 있다 [-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..

map을 이용해 문제를 풀었다. 문자열 str1, str2에 대해서 문자를 두글자씩 끊어서 다중집합의 원소로 만드는데, 알파벳 소문자일때는 toupper로 대문자로, 대문자는 그대로, 그외에는 무시하는 것으로 처리했다. str1은 m1, str2는 m2에 다중집합의 원소를 저장하고 이때마다 합집합 uni값을 증가하였다. m1을 탐색하여 m1의 first(string)에 해당하는 m2값이 존재한다면 m1의 second(int)과 m2값 중 min값을 교집합 inter값에 더하면 교집합의 수를 알 수 있다. uni는 전체 원소의 개수이므로 여기서 교집합을 빼면 합집합의 수를 구할 수 있다. uni와 inter가 둘 다 0이면 자카드 유사도는 1이고, 그 외엔 inter/uni이므로, 여기에 65536을 곱하..

주어진 조건만 잘 파악하면 어려움 없이 풀 수 있다. 올바른 괄호 문자열인지 correct_str함수로 확인할 수 있다. ( 일때 +1, ) 일때 -1을 하면 음수가 나오면 올바르지 않은 괄호 문자열임을 확인할 수 있다. w를 u와 v로 나누어 조건대로 수행한 결과를 반환하는 find수행함으로 결과를 구할 수 있다. 조건 4-1~4-5를 수행하는 함수는 change_str함수이다. #include #include #include using namespace std; bool correct_str(string p){ int x=0; for(int i=0; i

DFS와 map을 이용한 문제이다. 전체에서 course의 개수만큼 뽑는 모든 경우의 수를 탐색한다.(조합,dfs) map으로 각 조합이 가능한 경우의 수를 저장하고, max_order로 가장 많이 주문된 코스를 구한다. 최소주문횟수는 2회이므로 max_order>1일경우에만 map 탐색을 통해 max_order인 코스를 구하여 answer에 push한다. 정렬된 결과를 출력해야하므로 answer을 마지막에 sort한다. #include #include #include #include using namespace std; map m; int max_order = -1; void DFS(string order, string list, int depth){ if(list.size() == depth){ in..