본문 바로가기

Coding

 (195)
2606번 바이러스 그냥 DFS를 구현할 수 있는지 없는지 판단하는 문제 1번부터 시작하여 연결된 정점들만 찾으면 된다.
Manacher's Algorithm 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 이 팰린드롬을 찾기 위한 알고리즘 중 하나가 Manacher's Algorithm이다.(시간 복잡도 O(n)) 문자열 S=bananac로 팰린드롬을 찾아보는 연습을 해보자. A[i]는 i번째 문자를 중심으로 하는 가장 긴 반지름을 뜻한다 -> S[4]는 문자 a를 뜻하고 A[4]는 문자 a를 기준으로 S[2]와 S[6]에 있는 a까지의 거리(반지름)을 뜻한다. S[i] b a n a n a c A[i] 0 0 1 2 1 0 0 이 알고리즘의 동작 원리를 살펴보자. 1. i는 1부터 N까지 진행된다. 2. j r이면 A[i]의 초기값은 0이다. -2. i
typedef typedef은 아직 써본 적이 없기 때문에 예시를 만들어두려고 한다 typedef struct { int y,x; }Dir; Dir moveDir[4]={{1,0},{-1,0},{0,1},{0,-1}}; moveDir[i].y; moveDir[i].x; -> i가 0일 경우 y는 1, x는 0
cin.tie() / sync_with_stdio() cin.tie() -> cin, cerr 스트림과 cout 스트림이 묶여있기 때문에 입출력 동작을 하기 전에 출력 스트림 버퍼를 플러쉬하는데 이 묶여있는 것을 해제하기 위해 cin.tie(NULL)을 넣는다. 이렇게 하면 cin과 cout의 관계는 없게 된다. cout 버퍼를 따로 플러쉬해주어야 하지만 속도는 빨라진다. sync_with_stdio() -> c++ 라이브러리 iostream과 c 라이브러리 stdio의 동기화를 키거나 끌 수 있게 해주는 함수. 한 가지만 쓸 경우 다른 라이브러리까지 불러오면 속도가 느려지므로 iostream 라이브러리만 쓸 경우 ios_base::sync_with_stdio(false)를 사용하여 stdio 라이브러리 동기화를 풀어 속도를 향상시킨다.
10844번 쉬운 계단 수 일단 N=1일 경우 1층부터 9층까지 9개가 존재한다. N=2일 경우 0층으로 갈 수 있는 경우는 그 전 1층에서 가는 경우밖에 없다. 9층으로 갈 수 있는 경우는 그 전 8층에서 가는 경우밖에 없다. 1층에서 8층으로 갈 수 있는 경우는 그 전 층의 +1, -1층 즉, 2가지 경우가 있다. 따라서 N 길이를 가려고 했을 때 F[n][0] = F[n-1][1] F[n][9] = F[n-1][8] F[n][1] = F[n-1][0] + F[n-1][2] ..... ... .. F[n][8] = F[n-1][7] + F[n-1][9] 층수를 J라고 하면 F[n][j] = F[n-1][j-1] + F[n-1][j+1] 이 식이 성립하게 된다. ps. N=2일 경우 1층으로 가는 경우는 전 0층과 2층인데 0층..
3187번 양치기 꿍 입력을 받을때 양과 늑대의 위치를 큐에 넣어주고 bfs를 돌려 동시에 찾는다 늑대를 먼저 큐에서 빼든 양을 먼저 빼든 상관이 없다 큐에서 맨 처음 빼낸 좌표가 늑대인지 양인지 파악한 후 갯수를 1 더해주고 그 좌표를 기준으로 벽으로 막힌 곳까지 늑대와 양을 다 찾아낸다 찾아내서 누가 먼저 잡아먹히는지 비교해서 값에 넣어주고 큐에서 다음 늑대 혹은 양을 꺼내 확인한다 이때 방문처리를 통해 같은 공간에 있던 늑대 혹은 양인지 확인한 후 방문처리가 되어있으면 큐에서 그 다음 좌표를 꺼내 또 dfs를 시작한다 이 과정을 반복하여 늑대와 양의 수를 세게 된다. #include #include #define visited true #define Non_visited false #define MAX 251 using..
1003번 피보나치 함수 계산해보면 0은 fibonacci(num-1) 개수 만큼 1은 fibonacci(num)만큼 출력을 한다 #include #include #define MAX 41 using namespace std; int Test[MAX]; int fibonacci(int n) { if(n==-1){ return 1; } if(n==0) { return 0; } if(n==1) { return 1; } if(Test[n]!=0) return Test[n]; return Test[n] = fibonacci(n-1) + fibonacci(n-2); } int main(){ int number; cin>>number; queue q; for(int i=0;i> M; q.push(M); } while(!q.empty()){..
14502번 연구소 하필 왜 인체에 치명적인 바이러스를 만들었을까? 안만들었으면 유출될 일도 없었을텐데 내가 보통 문제를 풀면 이것저것 확인을 하면서 한다 1. 입력값을 넣고 제대로 넣었는지 출력을 해본다 2. 함수를 만들고 그 함수가 제대로 작동하는지 사용해본다 3. 2번 과정을 반복하면서 문제를 해결한다 -> 처음에는 바이러스 함수를 만들어서 벽으로 막혀있는 곳을 제외하고 채워지는지 확인 -> 벽 3개를 직접 세워 안전 영역의 크기를 구하는 함수를 만들어 확인 -> 벽 3개를 일일이 세우도록 하는 함수(예를 들어 11100-> 11010 -> 11001 -> 10110 -> 10101 -> 10011)를 만들어 확인 -> 함수 3개 동시에 확인 #include #include #include #include #defin..

티스토리툴바