문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로
큰 문제를 작은 문제로 나눠서 푸는 알고리즘 이다 !Dynamic(동적?) 은 아무 의미가 없다 비슷한 알고리즘으로 Divide and conquer(분할정복)가 있는데 차이점은 D.P는 중복이 있고 D&C 는 중복이 없다 라는 점이다.OverlappingOptimal
정해진 상수 시간의 루프나 함수 호출은 o(1)만큼의 시간 복잡도를 가진다.함수나 프로그램이 입력 크기 n 을 탐색한다면, 시간 복잡도는 o(n) . 어떤 n 루프 안에서 n-루프가 실행된다면 중첩된 루프의 개수 c가 시간 복잡도가 된다. 예를 들어 2번 중첩된 경우
문제에 "연속" 에대한 제한/조건이 있다면 마지막에 사용한 수를 기록해야된다.예를 들어 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제에서 같은 수를 두번 이상 연속해서 사용하면 안된다 라는 조건이 있을때 점화식을 세울때 마지막에 사용한 수를 나타내
문제 보러가기 : 5582번: 공통 부분 문자열Key point (생략가능)공통 부분 문자열이 아니라 공통 부분 문자열의 길이가 필요하다DP 를 활용하자Logic :문자열 s1 의 한 문자당 문자열 s2의 문자들과 같은 것이 있는지 확인이 필요하다. → 이차원 배열 d
\[백준] 1025 :: 제곱수 찾기문제 이해를 위한 자료 :Key point완전 제곱근이 되어야한다 → 제곱근을 판별해주는 함수 필요모든 칸에 대해 등차 수열이 될 수 있는 모든 경우의 수를 따져보아야한다. → 4중 for문 필요배열에 넣을 때, 문자열로 넣어주어야
예제 입력 : 1188번: 음식 평론가Logic :소세지 3개를 5명에게 나누어 준다고 상상해보자 3/5가 3이 되기 위해서는 5토막을 내면 된다. 5토막을 내기위해서는 칼질 4(5-1)번만 하면 된다.그림을 보게되면 주황색 선이 최종적으로 시행한 칼질이다.여기서
예제 입력 : 24230번: 트리 색칠하기key point :문제에서 “하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다” , “색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다” 는 말에 주목할 필요가 있다. 이 말은 즉 한 정점의
2512번: 예산Key point (생략가능)모든 가능한 경우의 수를 다 생각해주자 (10/1,1,1,1,11,11,11,11,11,100/100 의 경우 41이 나와야함)이진 탐색 을 떠올릴 수 있었다면,,,당신은 성공Logic : 지역별로 요청한 금액의 총 합을
key point : 그리디를 이용해서 해결 할 수 있다는 것을 알아차리자.최대한 많은 회의를 배정할 수 있는 요인을 생각해보자Logic:위의 풀이에 따라 시작 시간 기준으로 회의를 정렬한 후 종료 시간 기준으로도 한번 더 회의를 정렬시킨다.meetings.sort(
Key point (생략가능):그리디 탐색은 미래는 생각하지 않고 현재에 가장 최우선의 선택을 한다는 점이다. 그리고 선택은 바꿀 수가 없다 !Logic :N 개의 장소가 있고 두마리의 벌과 한개의 꿀통이 있다. 벌들은 꿀통 쪽을 향해서만 이동이 가능하다.벌들이 처음
Key point (생략가능) :그리디 라는 것을 알아채릴 수 있다면 당신은 ,, 👍단순하게 생각하자Logic : 위 와 같이 12명 4조가 있다고 하자. 그러면 어떻게든 1조 2조 3조 4조가 생길 것이다.1조 (a1,b1) 2조 (a2,b2) 3조(a3,b3)