본문 바로가기
반응형

전체 글

1509번 1509번 - 팰린드롬 분할 이 문제는 생각이 좀 부족해서 다른 설명을 보고 풀었다. 일단 점화식은 D[i]=i번 문자열까지 팰린드롬 분할했을 때, 최소갯수 솔직히 이 점화식까지는 생각했지만, 이를 어떻게 활용할지는 생각이 나지 않았다. 근데 여기서 점화식에는 포함되지 않는 변수 j 를 문자열 중간에 삽입하면 모든 퍼즐이 완성된다. 즉, 변수 j번 문자열부터 i번 문자열까지는 팰린드롬 수라고 가정한다면, D[i] = min(D[i],D[j-1]+1) 이라는 식을 세울 수 있게된다. 뒤에서부터 짤라가는 과정이라고 생각하면 된다. 1. 뒤에서 부터 만들 수 있는 가장 긴 팰린드롬을 만든다. 2. 그 팰린드롬을 잘라낸 앞 부분에서 다시 위의 과정을 시작한다. j의 범위는 0부터 i 까지 나타낼 수 있다. 예를.. 더보기
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.. 더보기
반응형

티스토리툴바