재귀12 [C++/PGS] Lv.4 : 호텔 방 배정 (재귀) https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr프로그래머스 레벨 4. 정답률 35%재귀 사용 문제!! 1. 효율성 실패 (78.8/100)테스트케이스는 다 맞았는데, 효용성은 0점 ㅋㅋ아마도 아래 부분이 문제였을 것이다. while(rooms.find(n) != rooms.end()){ n++;} 빈 방을 찾을때까지 while문을 돌렸는데, 이 부분을 최적화해야 통과할 것 같다.다음 빈 방을 효율적으로 저장할 수 있는 방법이 뭐가 있을까고민해봐도 모르겠어서 질문 게시판에서 힌트를 얻었다.. 2025. 4. 16. [Javascript/PGS] Lv.3 : 등대 - js 런타임에러 해결법 https://school.programmers.co.kr/learn/courses/30/lessons/133500 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 프로그래머스 레벨 3 등대 문제 - 트리 dp, dfs 유형* 정답 풀이는 최하단에 1. 재귀 풀이 - DFS이 풀이는 트리 dp 문제의 정석인 느낌인데, js로는 풀 수 없다.파이썬의 경우에는 sys.setrecursionlimit를 사용한다면, 재귀의 최대 깊이를 설정할 수 있어서이렇게 풀면 되지만...자스는 그런거 없다고 함 이 풀이로 제출 시 93.8점이 나왔다. (테스트 9만 틀림) let dp = null;let visited = .. 2025. 2. 26. [Javascript/PGS] Lv.2 : 피보나치 수 https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 프로그래머스 레벨 2.재귀로 풀면 시간 초과나서 안되는 듯.. 굳이 재귀로 풀려고 하면 dp로 점화식 써야 해결될 것 같다.단순하게 반복문으로 풀자! 나의 풀이function solution(n) { let arr = []; let answer = 0; arr.push(0); arr.push(1); for(let i=2; i 2025. 2. 19. [문제해결기법] 11. 동적 계획법 동적 계획법 (DP) 최적화 문제, 분할 정복 한 문제를 똑같은 문제이면서 크기만 작은 것으로 바꿀 수 있을지 생각해본다. 금화 모으기 문제 D[i][j] : (i, j)까지 오는 동안 모을 수 있는 금화의 최댓값 D[i][j] = max( D[i-1],[j] , D[i][j-1] ) + map[i][j]; 최대 공백 정사각형 (흰색으로만 이루어진 가장 큰 정사각형) mm 크기의 정사각형이 있다면, 4개의 (m-1)(m-1) 크기 정사각형이 있어야 한다는 점에서 착안한다. D[x][y]는 (x,y)가 가장 오른쪽 아래 꼭지점인 정사각형의 최대 크기라고 가정한다. (x,y)가 검은색이면, D[x][y] = 0 흰색이면, x==1 && y==1 : D[x][y] = 1 else : D[x][y] = min(.. 2023. 6. 16. [문제해결기법] 5. 욕심쟁이 기법 1. 욕심쟁이 알고리즘 : Greedy algorithm 매 단계마다 각 단계에서 최선의 선택을 한다. (현재 순간마다) 알고리즘이 매우 간단하나, 구한 답이 정답인지 검증이 필요하다. 기본 형태 2. 회의실 배정 문제 한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해서 시작 시간 Si와 끝 시간 Fi가 주어진다. 각 회의가 겹치지 않게 하면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하는 프로그램을 작성하시오. ❖ 입력 ➢ 첫 줄에는 회의의 수 n ➢ 둘째 줄부터 n+1줄까지 두 정수 Si와 Fi ❖ 출력 ➢ 잡은 회의를 차례대로 출력(둘 이상의 답이 있을 수 있음) 가능한 접근 방법 - 회의시간이 짧은 것 부터 넣는다 -> 반례 존재 - 다.. 2023. 4. 17. [C++/BOJ] 17609 : 회문 (투포인터) / 테스트케이스 / 삽질 기록 https://www.acmicpc.net/problem/17609 문제 회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다. 여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사.. 2023. 3. 25. 이전 1 2 다음 728x90 반응형
