호지

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

세 용액의 ph지수의 합이 0에 가까운 경우를 구하는 문제이다. 용액이 2개라하면 정렬된 리스트에서 이분탐색을 통해 0에 가까운 값을 구할 수 있다. 따라서 이분 탐색을 이용하기 위해 가장 ph지수가 낮은 값부터 순차적으로 용액을 뽑고(for문) 그 뽑힌 용액보다 ph지수가 높은 값들 중에서 2개를 뽑아 총 3개의 용액의 합 중 0에 가까운 값을 구하여, 이 때의 세 용액의 특성값을 출력한다. #include #include #include using namespace std; int main(){ int n; long long result[3]; long long value = 9000000000; long long list[5000]; cin >> n; for(int i=0; i> list[i]; }..

이분탐색을 활용한 문제풀이이다. 용액의 특성값은 오름차수로 주어지므로 용액의 특성값을 list배열에 입력받아 list배열의 왼쪽과 오른쪽에 포인터를 두고 이분탐색을 한다. 두 용액의 합의 절대값이 0에 가까울 때, 두 용액의 특성값을 출력해야 한다. sum변수에는 가장 절대값이 0에 가까울 때 값을 저장하고 1.왼쪽 포인터를 오른쪽으로 옮길때와(abs(list[right] + list[left+1]) 2.오른쪽 포인터를 왼쪽으로 옮길때(abs(list[right-1] + list[left]) 를 비교하여 1일때는 left를 1증가, 2일때는 right를 1감소시켜 이분탐색을 한다. #include using namespace std; int list[100001]; int main(){ int n; ci..

처음에 DFS로 풀었으나 시간초과로 틀렸다. DP문제는 해도해도 헷갈린다ㅜ dp[n][i][j]는 n번째 움직임에서 왼쪽발이 i에 있고, 오른쪽이 j에 있을때 power의 최솟값을 뜻한다. 1번째 움직임에서 가능한 경우는 왼발이 moves[1]에 있거나 오른발이 moves[1]에 있을 때이다. 따라서 dp의 초기값은 dp[1][moves[1]][0] = 2, dp[1][0][moves[1]] = 2이다. (0에서 이동한 경우엔 power가 2) 2~n까지 탐색을 통해 dp값을 채우면 dp[n]의 최솟값이 구하고자하는 power의 최솟값이다. 양발은 같은 위치에 있으면 안 되므로 if(moves[x] !=i) , if(moves[x] !=j)로 확인한다. x1-> x2의 이동의 power계산은 scores..

1766번 문제집 풀이가 비슷하다 https://hoji25.tistory.com/27 [백준 알고리즘] 1766번 문제집 문제풀이 c++ 1~n개의 문제 중 앞 번호의 문제를 먼저 푸는게 더 좋다. m개의 선행되어야할 문제 조건이 주어지는데 이 조건을 만족하면서 앞 번호의 문제를 우선적으로 풀 때 결과를 출력하면 된다. 위상정렬 hoji25.tistory.com order 벡터에는 자기보다 키가 큰 학생의 번호를 저장한다. ex) 3번학생보다 4번, 5번 학생이 키가 크다면 order[3]벡터에는 4,5가 저장되어있다. cnt배열에는 자기보다 키가 작은 학생의 수가 저장되어있다. 자기보다 키가 작은 학생이 0명이면 바로 줄을 설 수 있으므로 queue에 push한다. queue가 empty일때까지 wh..

DFS를 활용한 스도쿠 문제풀이이다. list벡터에 보드가 0일때 위치, 즉 1~9값이 채워져야하는 곳의 위치를 저장한다 DFS의 인자 level은 list벡터의 index위치이고, value는 1~9값 중 하나를 뜻한다 i가 0~9일 때, board[nx][i](가로) board[i][ny](세로) , board[nx/3*3+i/3][ny/3*3+i%3](3*3 정사각형) 이 value값인지 확인하고 가로,세로,3*3정사각형에 같은 value가 있다면 해당 dfs를 종료한다. 아니라면 해당 level 위치의 board값을 value로 하고, level+1이면서 value 0~9일 때 DFS를 호출한다. level이 list.size()-1이면 스도쿠를 다 채웠을 때이므로, 결과값을 출력한 후 exit(..

다각형의 면적을 구하는 신발끈 공식을 사용하여 문제를 풀었다. ret은 각 좌표의 절대값은 10000이 될 수 있으므로 long long형으로 선언하였다. 또한 ret을 구할 때 x[i]*y[j] - x[j]*y[i] 도 int의 최대값을 넘을 수 있기에 long long형으로 형변환을 하였다. ret이 음수인 경우 양수로 바꾸고 ret/2한 값을 double로 형변환하여 출력하면 다각형의 면적을 구할 수 있다. #include using namespace std; int x[10000], y[10000]; int main(){ int n; cin >> n; for(int i=0; i> x[i] >> y[i]; } long long ret = 0; int i = n-1; for(int j=0; j

역시 알고리즘은 끝이없다 두 선분이 만나는지 여부는 CCW알고리즘을 통해 구할 수 있다 CCW알고리즘은 3점의 방향성을 나타내고 시계방향일때는 -1, 직선일때는 0, 반시계방향일때는 1을 반환한다. 이 방향성을 응용하여 선분이 만나는지 확인할 수 있는데, 선분1 a(x1, y1), b(x2, y2) 선분2 c(x3, y3), d(x4, y4) 이 주어졌을 때 선분ab와 점 c, 선분 ab와 점 d의 ccw값이 둘 다 -1이거나 둘 다 1이면 선분 ab와 선분 cd는 만나지 않는다. 위를 이용해 ccw를 값을 이용해 선분ab, 선분 cd에 대해 교점이 있는지 확인하는 check 함수를 구현했다. 각 점에 대한 ccw값인 abc, abd, cda, cdb를 구하고, if(abc*abd ==0 && cda*c..

map에 n배열과 m배열의 가능한 부 배열의 합을 key로 하여 합의 개수를 저장한다. 그 후 map을 전체탐색하여 nmap에서 key가 x일때, mmap에서 key가 t-x인 경우를 곱한 값을 모두 더하면 두 배열의 부 배열의 합이 t인 모든 경우의 수 개수를 알 수 있다. 예시 5 4 1 3 1 2 3 1 3 2 위 경우에서 각각 map을 채우면 nmap[1] = 2, nmap[2] =1, nmap[3] = 2, nmap[4] =2, nmap[5] = 1, nmap[6] = 1, nmap[7] =1 mmap[1] = 1, mmap[2] = 2, mmap[3] = 1, mmap[4] =1, mmap[5] =1, mmap[6] 와 같이 채워지고, map탐색을 통해서 nmap[1] * mmap[4] + n..