본문 바로가기

분류 전체보기151

[백준] 1920 수찾기 c++ 문제 링크 https://www.acmicpc.net/problem/1920 KEY 이중for문을 돌려서 일일이 확인하는 작업은 100,000 * 100,000 O(N^2)으로 시간초과가 발생한다. 따라서 O(logN)의 시간복잡도를 갖는 이분탐색과 map, ordered_map을 활용하여 풀이할 수 있다. unordered_map: HashTable로 구현된 자료구조. 탐색 시 O(1)의 시간복잡도 map: 이진탐색트리로 구현된 자료구조. 탐색 시 O(logN)의 시간복잡도. map의 경우 자동으로 정렬되므로(Red Black Tree의 특징) 삽입/삭제가 빈번할 경우 성능이 저하되는 특징이 있다. 따라서 이 문제와 같은 경우 최대 100,000번 불필요한 정렬을 할 수 있으므로, unordered_m.. 2023. 3. 31.
Can not issue data manipulation statements with executeQuery() 에러 해결 문제 발생 관리자페이지에서 상품 삭제버튼을 클릭하니 삭제 실패라는 에러 문구와 함께 해당 에러가 발생했다. 실제 DB에도 확인해 본 결과 상품이 제대로 삭제되지 않았다. 원인 분석 이 오류는 INSERT, UPDATE, DELETE문을 사용할 때 executeUpdate() 메서드를 사용하지 않았기 때문에 발생한다. SELECT 쿼리를 보낼 때에는 결과를 받아와야 하기 때문에 executeQuery() 메서드를 사용해야 한다.(조회한 행의 갯수를 반환) INSERT, UPDATE, DELETE 쿼리를 보낼 때에는 결과값이 없기 때문에 executeUpdate() 메서드를 사용해야 한다. 문제 해결 INSERT, UPDATE, DELETE 쿼리를 실행할 때는 executeUpdate() 메서드를 사용하도록.. 2023. 3. 30.
[프로그래머스] 등굣길 c++ 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 KEY 101 * 101 의 arr배열을 선언 한 후, 물 웅덩이가 있는 부분에 -1을 넣는다. 시작부분인 arr[1][1]에 1을 넣는다. 1 0 0 0 0 -1 0 0 0 0 0 0 arr[i][j] = arr[i-1][j] + arr[i][j-1]의 점화식으로 arr[i][j]에 값을 넣어가며 최단경로의 가짓 수를 구할 수 있다. 1 1 1 1 1 -1 1 2 1 1 2 4 백트래킹으로 최단경로의 가짓수를 구하는 방식으로 풀면 테스트케이슨는 모두 통과했지만 전부 시간 초과가 발생한다. 격자의 크기가 100*100이나 되서 재귀로 푸는데에는 시간초과가 뜰 수 밖에 없다. Dfs.. 2023. 3. 30.
[백준] 9251 LCS c++ 문제 링크 https://www.acmicpc.net/problem/9251 KEY LCS문제는 다음과 같이 행열로 두 문자열을 나열한 다음, 이중 for문을 활용해서 풀이한다. 아래 표를 만들어 내는 것이 핵심이고, 규칙성은 다음과 같다. 두 문자가 같은 경우 : 대각선 이전의 값에 1을 더한다. 두 문자가 다를 경우 : 자신의 왼쪽과 위쪽 중 최댓값을 취한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #include using namespace std; string str1; string str2; int dp[1001][1001]; int main() { cin >> str1 >> str.. 2023. 3. 29.
[백준] 2565 전깃줄 c++ 문제 링크 https://www.acmicpc.net/problem/2565 KEY 문제에서 없애야 하는 전깃줄의 최소 갯수를 구하라는 말은, 전깃줄의 전체 갯수 - 엉키지 않도록 하는 전깃줄의 최대 갯수를 구하라는 말과 동일하다. 입력값의 first를 기준으로 오름차순 정렬을 하면 first를 고정시킬 수 있으므로 second만 고려할 수 있다. 문제의 예제를 살펴보면, 정렬 후 second는 8, 2, 9, 1, 4, 6, 7, 10로 나타난다. 여기서 8, 9, 1을 없앤다면 2,4,6,7,10이 될 것이고, 이는 엉키지 않도록 하는 전깃줄의 최대 갯수가 된다. 따라서, 순열이 주어졌을 때, 가장 긴 증가하는 부분수열의 길이를 구한 후, 전체 갯수 N에서 빼주면 없애야 하는 전깃줄의 최소 갯수가 나.. 2023. 3. 28.
[백준] 11054 가장 긴 바이토닉 부분 수열 c++ 문제 링크 https://www.acmicpc.net/problem/11054 KEY 가장 긴 증가하는 부분 수열 문제와 풀이 과정이 거의 같다. 참고 --> https://everydayyy.tistory.com/136 [백준] 11053 가장 긴 증가하는 부분수열 c++ 문제 링크 https://www.acmicpc.net/problem/11053 KEY 현재 자신과 이전에 나왔던 수들을 비교해가면서, 현재 자신 > 이전의 수를 만족할 경우에 길이+1을 해주고, 가장 긴 길이를 자신의 길이로 취한다. 예 everydayyy.tistory.com 위 글을 간단히 요약하자면, 가장 긴 증가하는 부분수열는 다음과 같이 구할 수 있다. 현재 자신과 이전에 나왔던 수들을 비교해가면서, 현재 자신 > 이전의 수.. 2023. 3. 28.

티스토리툴바