본문 바로가기
반응형

알고리즘

1074번 1074번 - Z 처음에는 처음부터 모든 점을 방문하면서, 찾고자 하는 r,c 가 나왔을 때 답을 출력하도록 했더니, 시간초과가 발생했다. 그래서 다 방문하지 않고, r,c를 찾아가는 코드를 분할정복과 재귀를 이용해서 구현했다. 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단 순서로 방문하도록 for문을 이용해서 첫값을 구했다. 그리고 해당하는 점이 사분할 된 곳 중에 어느 곳에 있는지 확인하고, 그 사분면으로 이동하도록 구현했다. 만약 2사분면에 있다면, 1사분면의 모든 갯수를 더한 다음 순서가 되고, 만약 3사분면에 있다면, 1사분면+ 2사분면의 모든 갯수를 더한 다음 순서가 되기 때문에 모든 정점을 방문하지 않고 , 곧바로 목표로 하는 정점으로 방문해도 정답을 구할 수 있기 때문이다. 12345.. 더보기
2164번 2164번 - 카드2 deque 를 이용해서 구현했다. 카드 맨위를 없애는 것은 deque의 front 를 pop 하고, 다시 앞장의 카드를 뒤에 넣는 것은, deque 의 front 를 back에 push 하면 된다. 내가 왜 deque 로 했을까.. queue 로 하는게 오히려 더 편해보인다.. 1234567891011121314151617181920212223242526272829303132#include#include using namespace std; int main(){ int n; cin >> n; deque card(n); for (int i = 0; i 더보기
9517번 9517번 - 아이 러브 크로아티아 while 문 안에서 n번을 입력받는 동안 계산을 하는 방식으로 구현했다. 대답을 T로 했을 때만, 옆사람으로 넘기기 때문에 따로 if문을 이용해서 구현했다. 대답을 했을 때 210초가 처음으로 넘는사람이 범인이 된다. 그러므로 대답을 한 시간이 210초가 넘는지를 먼저 확인하고, 넘지 않는다면 다음사람에게 폭탄을 넘겨주는 순서로 풀어야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include using namespace std; int main(){ int k, n; cin >> k >> n; int ans; bool first = true; int t = -1; .. 더보기
1526번 1526번 - 금민수 n제한이 작아서 완전탐색으로 풀 수 있다. 맨 끝자리부터 4나 7로 나눠지는지 구하면서 문제를 풀었다. BFS로도 풀 수 있을 것 같은데, 그냥 while 문을 이용해서 모두 구했다. 1234567891011121314151617181920212223242526272829303132333435#include#includeusing namespace std; int n; int main(){ cin >> n; for (int i = n; i >= 4; i--) { int k = i; while (k!=0) { int ret = k % 10; if (ret !=4 && ret!=7) { break; } k /= 10; } if (k == 0) { cout 더보기
1551번 1551번 - 수열의 변화 조건에 수열의 숫자의 크기에 대한 조건이 없기도 하고, 그래서 그냥 string 을 써서 문제를 풀었다. 조금 더럽게 푼 감이 있긴 하지만, stoi 함수를 이용해서 입력받은 string을 int 형 변수로 바꿔줬다. (int 형으로 풀리는거 보니 엄청 큰 수는 없는 듯 함) 바꾼 int 값들을 v 벡터에 모두 넣어주고, 주어진 조건을 이용해서 v[i] = v[i+1] - v[i] 값을 다시 저장했다. 그리고 맨 끝 값은 필요없기 때문에 v.pop_back() 을 통해서 마지막값을 없애줬다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include#include.. 더보기
5525번 5525번 - IOIOI 이미 문자열의 길이가 백만이기 때문에, N^2의 for문으로 모두 비교하는건 시간초과가 발생할 거라고 생각했다. 그래서 시간을 줄이는 방법을 생각해봤는데 DP 점화식은 생각이 나지 않았고, 다른 방법을 찾게 됐다. 생각난 하나의 방법은 IOIOI 가 있을 때, P1=IOI 가 되고, 처음에 한번 맞추고 난 후에는 OI가 있으면 갯수가 하나씩 늘어난다는 점을 생각했다. 즉 IOIOI 는 2개, IOIOIOI는 3개가 되는 방식.. 그리고 OI 가 아닌 게 나오면 다시 처음부터 시작하는 것처럼 시작하면 된다는 점을 알게됐다. 그래서 정답을 한번 맞추고 연속으로 나오는지 확인하는 bool 타입의 chk변수를 지정해서 연속되는지 안되는지를 파악했다. 이런식으로, 코드는 깔끔하지 않지만 .. 더보기
1913번 1913번 - 달팽이 내가 까다롭게 푼지는 모르겠는데, 처음에 약간 까다롭다고 느꼈다. while 문에서 아래로 쭉, 오른쪽으로 쭉, 위로 쭉, 왼쪽 쭉, 아래로 쭉... 이런식으로 반복되기 때문에 dx,dy 배열을 만들어서 x,y 값을 이동시키면서 문제를 풀었다. 그리고 dx,dy 안에 들어갈 인덱스 d 값은 x나 y가 범위를 벗어나거나, 이미 수가 채워져 있으면 변화하도록 만들었다. 그리고 다 짜고 보니, k=0일때 한번 더 들어가는게 확인돼서, while문의 조건문에 추가해서 문제를 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include#includeusing namespac.. 더보기
10828번 10828번 - 스택 시뮬레이션 문제, 나는 vector 를 이용해서 스택을 구현했다. stack 은 마지막에 들어온게 처음에 나가는 LIFO 구조란 점만 기억해서 문제를 풀어주면 끝! ### push 1 이런식으로 숫자를 받는 경우, cin.clear() 를 해줘야 한다는 점 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include#include#includeusing namespace std; int main(){ int N; cin >> N; vector st; while (N--) { string s; cin >> s; ci.. 더보기
반응형

티스토리툴바