백준 12865번 평범한 배낭
우선 dp배열에 들어가야할 값은, 물건의 인덱스별 무게별 가치합이 들어가야한다.그냥 무게별 가치합으로 일차원 배열로 설정한다면, 같은 무게인데 다른 물건으로 이루어졌을때, 관계정립을 할 수가 없다.따라서 물건의 인덱스별 무게별 가치합, 이차원 배열을 통해 dp를 설정한
백준 1931번 회의실 배정
📢이 문제의 핵심은 종료시점을 기준으로 정렬한 후, 가장 위에 있는 회의부터 고르면 된다는 것이다.단, 이때 종료시점이 같다면, 시작시점이 빠른것을 먼저 선택해야한다.알고나면 아무것도 아닌 규칙이지만, 알기전에는 잘 안보였던 규칙이었다.규칙만 안다면 구현은 크게 어렵
백준 17140번 이차원 배열과 연산
전체적인 설계는 100x100 이차원 배열을 생성 후, R,C연산에 따라, 각 행 또는 열을 해쉬맵, 리스트를 통해 정렬을 반복하는 것이다.hashmap에 숫자와 빈도수를 세서 넣는다. 이때, 0은 세지 않는다.숫자와 빈도수를 list에 전달한다.📢 리스트를 숫자 기
1699번 제곱수의 합
dp배열에 들어갈 값은 제곱수의 갯수가 들어가면 된다. 11의 경우, $11=3^2+1^2+1^2$(3개 항) $11=2^2+2^2+1^2+1^2+1^2$(5개 항)이 가능하기 때문에 최솟값을 찾아야 한다.이때, 무조건 큰 제곱수를 기준으로 생각할 수 있는데,12를 살
백준 11055번 가장 큰 증가하는 부분순열
dp배열에 넣어야 할 값: 현재 값보다 작은 값 중에 증가하는 순열의 합이 가장 큰값1 100 5 3 50 일때, dp5가 가능한 증가하는 순열은 1 5 50, 1 3 50 두가지가 있다. 둘 중 큰값을 선택한다.이때 1 5, 1 3 은 각각 dp3, dp4이다.즉 d
백준 101번 다리놓기
1번 코드(수학공식 사용) 풀이방법 nCr의 조합을 사용하면 된다까지는 확인할 수 있다. 다만 nCr을 어떻게 구현할 것인가가 문제이다. 이를 그대로 구현하면, long 자료형에 29!을 담을 수가 없다. 따라서 약분한 식을 구현해준다. 즉, 7C4 라면, 7x6x
SWEA 1824. 혁진이의 프로그램 검증
📢전체적인 구조는 dfs탐색을 통해 @를 만나면 flag=true;를 통해 끝낼수 있음을 체크하고, 없다면 NO를 출력한다.이때, 무한반복 탈출조건은 같은 좌표에, 같은 메모리크기, 같은 방향이 온다면 탈출하도록 하여 끝낼 수 없음을 체크한다.check 함수에 좌표와
백준 16928번 뱀과 사다리 게임
사다리와 뱀리스트를 만들어 입력받은 값을 넣어준다.bfs탐색시 다음 위치로 가능한 수는 현재 위치 + 주사위 1~6까지 수이다.이때 다음 위치에 해당하는 수가 사다리나 뱀 리스트에 있는 수라면, 추가적으로 이동한다.👉뱀을 거치는게 최소일 수도 있으므로, 뱀을 아예 제
13549번 숨바꼭질 3
현재 위치x에서 갈 수 있는 방법은 총 세가지가 있다.x-1,x+1,2\*x 방문하지 않은 곳이라면 큐에 넣어준다.큐에 넣을때, 위치와 시간을 함께넣는데, 2\*x로 이동할때는 시간을 추가하지 않는다.현재 위치가 K라면 그때의 시간을 출력한다.📢간단한 bfs이지만 주
백준 1034번 램프
풀이방법 이 문제는 완전탐색 방식으로 스위치를 K번 껐다켰다 하는 경우의 수 중 최댓값을 찾으면 시간초과가 난다. 따라서 적절한 규칙을 찾아서 그리디 방식으로 구현해야한다.
백준 1027번 고층 건물
풀이 방법 전체 코드의 구조는 현재 위치의 건물에서 왼쪽에 위치한 건물, 오른쪽의 위치한 건물 중 조건에 해당하는 건물을 세고, 완전탐색 방식으로 탐색하여 조건에 맞는 건물 중 최댓값을 구한다. > 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나
백준 1022번 소용돌이 예쁘게 출력하기
\-5 000 ≤ r1, c1, r2, c2 ≤ 5,0000 ≤ r2 - r1 ≤ 490 ≤ c2 - c1 ≤ 4만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.📢해당풀이의 전체적인 접근은, 입력값의 최대범위에 맞게 배열을
백준 17298번 오큰수
스택에 현재 인덱스를 담으며 진행하고,while문으로 스택을 탐색하며, 스택에 담긴 인덱스에 해당하는 arr값이 현재 arr값보다 작으면 그곳에 현재 arr값을 대입하며 진행한다.현재 arr값보다 크다면, while문을 탈출한다.처리되지 못하고 stack에 남아있는 인
백준 14501 퇴사
우선 dp배열에 어떤 점화식으로 통해 P값을 넣어야 할지 알아보기 위해 가능한 경우의 수를 하나씩 나열해본다.1 4 523 4 54 5500👉 나중에 상담한 값이 이전의 dp값에 영향을 미치는 것을 확인할 수 있다. 즉, dpi = dpi+1 + k; 이런식의 점화식
백준 1912 연속합
📢이 풀이의 핵심은 dp배열에 처음 순열부터의 합, 현재값 둘중에 큰값을 메모이제이션 하는것이다.이후 dp배열의 최댓값을 구하면 된다.나는 dp배열에 이후 순열의 합을 저장하고 접근했는데, 이런식의 접근에는 반례가 생겨서 풀 수가 없다.dp배열에 어떤값을 메모이제이션
백준 11053번 가장 긴 증가하는 부분순열
📢 arrn에 들어있는 수보다 이전에 더 작은 값의 길이가 dp배열에 담기게 된다.이때 arrn보다 작은 arri값들중 dp배열의 값중에 최대값+1로 현재 dp배열에 저장한다.주의할 점은 최소길이가 1이므로, 전부 1로 초기화 해줘야 한다는 점이다.또한 recur(N
SWEA 2806 N-Queen
map을 완전탐색으로 0,0부터 check 함수로 가로,세로, 대각선 4방향을 확인하고(범위설정 주의) 놓을 수 있다면 퀸을 자리에 놓는다. (mapi = 1;)자리에 놓았다면 다음 행으로 넘어가서 다시 탐색을 시작한다.퀸 8개를 놓았다면 answer을 증가시키고 끝낸
토익 문법 공부
that + V + ()\-> 동사뒤에 목적어 자리 이므로 명사가 와야한다. B,C 중 하나\-> 동명사나 to 부정사, 명사가 선택지에 같이 있을경우 90%는 명사가 답이다.명사가 아니면서 동명사나 to 부정사가 답이 되는 패턴은 거의 없음1\. 동명사에서 명사로 굳
백준 2579번 계단오르기
2가지 경우의 수중 더 큰값을 dp배열에 메모이제이션하면서 진행한다.이때 n-1은 메모이제이션 하지 않고, arrn-1을 그대로 더해준다.이유는 n-1을 메모이제이션 하면, dp5,dp4,dp3...등 이전 계단을 밟았는지를 알수가 없다.📢따라서 (recur(n-3)
백준 1463번 1로 만들기
📢이 문제에서는 할 수 있는 연산이 세가지로 나와있다.3으로 나누어 떨어질 경우 3으로 나누기2로 나누어 떨어질 경우 2로 나누기1빼기이 연산들중에는 겹치는 연산이 있기 때문에 경우의 따라 해당 연산들 중에 나오는 최소값을 구해야한다.3으로 나누어 떨어질 경우에, 3