PS 1000문제 도전기 - 24일차 [백준]
어제 깜빡하고 자버려서 지금 올린다...오늘 공부한 내용 & 푼 주요 문제1655 - 가운데를 말해요(골드 2)https://www.acmicpc.net/problem/1655우선순위 큐를 이용하여 중간 값을 빼내는 문제. 풀이가 굉장히 신박했다. 오늘 푼 잔여 문제없다. 현황레이팅: 1373 -> 1379(+6)푼 문제 수: 576 -> 577(+1)
2024.07.31
no image
PS 1000문제 도전기 - 23일차 [백준]
오늘 공부한 내용 & 푼 주요 문제12015 - 가장 긴 증가하는 부분 수열 2(골드 2)https://www.acmicpc.net/problem/1201512738 - 가장 긴 증가하는 부분 수열 3(골드 2)https://www.acmicpc.net/problem/1273814002 - 가장 긴 증가하는 부분 수열 4(골드 4)https://www.acmicpc.net/problem/1400214003 - 가장 긴 증가하는 부분 수열 5(플레 5)https://www.acmicpc.net/problem/14003LIS의 대표적인 문제. n이작을때는 DP를 이용해 풀면 시간복잡도가 O(n^2)이기 때문에 시간초과가 난다. 따라서 이분탐색을 사용해서 풀어야 한다. 이에 대한 내용은 따로 정리해서 올려보겠..
2024.07.29
PS 1000문제 도전기 - 22일차 [백준]
오늘 공부한 내용 & 푼 주요 문제1021 - 회전하는 큐(실버 3)https://www.acmicpc.net/problem/1021deque를 이용하여 푸는 쉬운 구현 문제. 오늘 푼 잔여 문제없다.현황레이팅: 1338->1338(0)푼 문제 수: 568 -> 569(+1)
2024.07.29
no image
PS 1000문제 도전기 - 21일차 [백준]
오늘 공부한 내용 & 푼 주요 문제없다. 오늘 푼 잔여 문제1문제 풀었다.현황레이팅: 1338->1338(0)푼 문제 수: 567 -> 568(+1)
2024.07.28
PS 1000문제 도전기 - 20일차 [백준]
오늘은 캠핑을 가야되서 조금밖에 못풀고 글을 남겨놓는다.오늘 공부한 내용 & 푼 주요 문제11509 - 풍선 맞추기(골드 5)https://www.acmicpc.net/problem/11509그리디 알고리즘을 쓰는 문제. 사실 구현 자체는 쉬웠으나 문제 이해를 하는데 애를 먹었다. 오늘 푼 잔여 문제없다. 현황레이팅: 1335 -> 1338(+3)푼 문제 수: 565 -> 567(+1)
2024.07.26
PS 1000문제 도전기 - 19일차 [백준]
오늘 공부한 내용 & 푼 주요 문제2239 - 스도쿠(골드 4)간단한 백트래킹 문제. 구현이 9할인거 같다. 스도쿠 원리만 잘 이해하고 있으면 되는 문제. 오늘 푼 잔여 문제없다. 현황레이팅: 1331 -> 1335(+4)푼 문제 수: 565 -> 566(+1)
2024.07.26
PS 1000문제 도전기 - 18일차 [백준]
오늘 공부한 내용 & 푼 주요 문제9935 - 문자열 폭발(골드 4)https://www.acmicpc.net/problem/9935스택을 사용하여 푸는 문제. 괄호 문자열 해결할때 스택이 사용된다고 해서 비슷하게 적용하여 풀어봤다. 9252 - LCS 2(골드 4)https://www.acmicpc.net/problem/9252LCS 1의 확장판. 리스트를 하나 더 만들어서 문자열을 저장해주며 dp를 돌리면 된다. 15681 - 트리와 쿼리(골드 5)https://www.acmicpc.net/problem/15681그 유명한 트쿼 문제의 첫 문제. dfs를 이용해서 자신의 자식이 몇명 있는지 세면서 올라와주면 된다. 11722 - 가장 긴 감소하는 부분 수열(실버 2)https://www.acmicpc..
2024.07.25
no image
17298:오큰수 [백준 문제풀이][Python]
문제:https://www.acmicpc.net/problem/17298난이도: 골드 4스택을 이용하여 최댓값을 구하는 문제. 처음 보는 개념이라 이해하는데 꽤 애를 먹었다.아이디어1처음에는 단순하게 최댓값을 찾아서 계속 업데이트 해주는 방식을 생각해봤는데, 단순 계산으로도 O(n^2)이 넘어서 안된다. 입력 값이 10만이기 때문에 O(nlogn) 또는 O(n)으로 풀어야 된다.아이디어2다음은 스택을 사용한 풀이이다. 혼자 생각한건 아니고, 대충 찾아보면서 삽질 좀 했다.스택은 선입후출(Last In Fisrt Out)의 방식을 가진 자료구조로, 선입선출 방식인 큐와 대비되는 방식이다. 이를 이용해서 최댓값을 구할 수 있는데, 스택을 하나의 탑으로 보자면, 값이 들어올때마다 탑의 맨 윗부분부터 비교하면서..
2024.07.24
PS 1000문제 도전기 - 17일차 [백준]
오늘 공부한 내용 & 푼 주요 문제3015 - 오아시스 재결합(플레 5)https://www.acmicpc.net/problem/3015스택을 사용하여 최댓값을 찾아가며 푸는 문제. 오큰수를 생각하며 풀어봤지만, 역시 플레의 벽은 높았다. 여러 번 풀이를 바꿔가며 풀었는데, 내일 아침에 일어나서 글을 올려보겠다.오늘 푼 잔여 문제없다. 현황레이팅: 1307 -> 1316(+9)푼 문제 수: 560 -> 561(+1)
2024.07.24