본문 바로가기
반응형

알고리즘/BOJ

10942번 10942번 - 팰린드롬? DP를 이용해서 문제를 풀었다, 처음에는 그냥 하나 하나 완전탐색으로 하려고 했더니, 최대로 계산했을 때, 앞에서 N개 보고, 뒤에서 N개 보면서 확인 = 2N 번 거기에 질문 M 개가 있으므로 O(2MN) 이 되는데, MN=10억이라는 숫자가 나오기 때문에 1초안에 풀 수 없었다. 그래서 DP를 이용해서 문제를 풀었다. D[S][E] = 팰린드롬이면 1, 아니면 0 이라는 점화식을 세웠다. 나는 보통 DP는 재귀로 풀기 때문에, 재귀는 줄여나가는게 핵심이다. 그래서 D[S][E] 가 팰린드롬인지 확인할 때, D[S][E] 가 팰린드롬이 되기 위해서는 D[S+1][E-1] 에서 V[S] 와 V[E] 가 같으면 팰린드롬이 된다는 사실을 알았고, 이를 통해 글자길이를 줄여나가면서 .. 더보기
11048번 11048번 - 이동하기 처음에 완전탐색으로 풀었을 때, 시간 초과가 걸렸다. 사실 시간안에 풀 수 있다고 생각하고, 완전탐색으로 풀었는데 시간초과가 떠서 당황했다. 그리고 이 문제를 풀때, DP에 쓰이는 D값을 평상시 처럼 0으로 초기화했던 것이 문제였다. 사탕의 갯수가 0개 일 수 있기 때문에, D값에 0이 들어갈 수 있다는 점을 인지하고, -1로 초기화 했어야 했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include#include#include using namespace std;int dx[3] = { 0,-1,-1 };int dy[3] = .. 더보기
1764번 1764번 - 듣보잡 map 을 통해서 문제를 풀었다. while 문 양쪽에서 모두 입력이 될 경우 p[name] 의 값을 하나씩 증가시켜줬다. 그래서 마지막에는 iterator 를 이용해서 그 값이 2인 경우( 즉 , 양쪽에서 나온경우) 의 갯수를 세주고 출력해줬다. 갯수를 먼저 세주느라 for 문을 2개를 썼는데, 그냥 vector 를 선언해서 두번째 while문에서 다시 담아서 출력해도 될 것 같다. 나는 반복자를 숙달하려고 이렇게 풀어봤다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include#include using.. 더보기
7785번 7785번 - 회사에 있는 사람 이 문제는 이진탐색트리(Binary Search Tree) 를 공부하다가 예시 문제로 만났다. 이걸 노드들을 struct 해서 복잡하게 구현하기 보다는 STL 의 set을 쓰면 편하다고 알게 되었다. set 은 써보지 않았지만, map 을 공부할 때 비슷하다는 것을 좀 알아서 쓸 수 있었다. map 과는 다르게 set 은 따로 값을 저장하지 않고 key 값을 그대로 이용한다. 또한 오름차순으로 정렬이 된다는 특성! 배운점 이번 문제를 풀면서 iterator 에 대해서 쓰는 방법을 알 수 있게 된 것 같다.. 조금은 처음에 역순으로 출력해야 했기 때문에 iterator 선언 후 rbegin 부터 시작하려고 하자 오류가 발생했다. 그래서 고민하던중에 reverse_iterat.. 더보기
11286번(우선순위큐 다시풀기) 11286번 - 절대값 힙 나는 이 문제를 우선 순위큐가 아닌 배열을 통해서 풀어보았다. 최대힙, 최소힙과 비슷한 방식이었지만, 비어있는 큐가 0일 때를 생각해줘야 했고, 크다 작다가 아닌 같은 값일 때도 나눠줘야 했기 때문에 조건이 많이 발생하였다. 그리고 pop 할때 for문에서 i 값 증가량을 명시해놓지 않아서 처음에 많이 틀렸다. pop 에서 마지막 l !=0 && r!=0 부분에서 많이 헷갈렸었다.. 배열로 풀기는 너무 조건문이 많이 생기는 것 같다.. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273.. 더보기
1927번(우선순위 큐 다시풀기) 1927번 - 최소힙 최대힙과 비슷한 방식이었지만, 힙에 정수값이 들어온다는 점이 달랐다. 따라서 최대힙에서는 빈 노드가 0 이라, 어떤 노드가 추가 삭제 되도, 빈 노드에 대해서 생각할 필요가 없었다. 어차피 들어오는 값이 자연수고, 이는 0보다는 항상 크기 때문에. 하지만 최소힙에서는 비어있는 노드 값이0 이고, 이는 모든 자연수보다 작기 때문에, 비어있는 노드도 체크해줘야 했다. 이는 pop 할 때, 왼쪽 자식 노드가 빈 경우, 오른쪽 자식 노드가 빈 경우, 둘다 빈 경우, 둘다 있는 경우를 모두 고려해서 문제를 풀었다. (priorty_queue 를 이용하면 너무나 쉬운데.... ) 1234567891011121314151617181920212223242526272829303132333435363.. 더보기
11279번(우선순위 큐 다시풀기) 11279번 - 최대 힙 pop 함수와 push 함수를 구현해서 최대힙을 표현했다. 백준님 코드 중에 priority_queue 를 이용해서 엄청나게 쉽게 구현한게 있는데.. priority_queue 를 아직 사용할 줄 몰라서.. 공부를 해야겠다. 이 문제에서 배운점 - last 라는 트리에서 마지막을 나타내는 변수를 하나 지정해주니 , 처음에 엄청나게 복잡했던 코드가 엄청 간결해질 수 있었다. - for문의 조건문을 꼭 써야한다는 편견에서 벗어나서, 요리조리 내 맘대로 표현할 수 있어야 한다는 점을 느꼈다. ?? 궁금점 pop 함수의 for문에서 i*2 1; i /= 2) { if (heap[i] > heap[i / 2]) { swap(heap[i], heap[i / 2]); } else { brea.. 더보기
4195번 4195번 - 친구 네트워크 이 문제는 union-find 를 이용해서 문제를 풀었다. 추가적으로 STL 의 map 을 이용했다. 다른 분들 코드를 보니 각 노드에 번호를 다시 매겨서 그 번호를 이용해서 문제를 푸신다. 나는 map 에서 string 을 배열의 인덱스로 사용할 수 있으니 , 그냥 string 을 사용해서 문제를 풀었다. (그런데 이게 다른 문제에서는 메모리 오류나, 시간 오류가 발생하는 지는 모르겠다 아래 질문들 갓들은 대단하다 정말..... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374.. 더보기
반응형

티스토리툴바