백준 2630번 c++ 문제풀이 문제: 백준 2630 풀이: 2차원 vector에 색종이 정보 입력 색종이 칸이 모두 같은 색인지 확인 모두 같다면, 해당 색의 갯수 증가. 다른 색이 있다면, 4등분 후 각 부분을 1번 과정 부터 반복한다. (재귀) 위 과정이 모두 끝났다면, 색종이의 ...

백준 1927번 c++ 문제풀이 문제: 백준 1927 풀이: 최소힙은 최솟값을 찾기 위한 데이터 구조이다. 우선 순위 큐를 오름차순으로 정렬 하면 최솟값을 찾을 수 있으므로 최소힙 구현이 가능하다. 코드: #include <iostream> #include <algorithm> #include <que...

백준 1541번 c++ 문제풀이 문제: 백준 1541 풀이: 문자열을 입력받은 후, ‘-‘를 기준으로 문자를 잘라야 한다. ’-‘뒤의 숫자가 클수록, 작아지기 때문이다, 따라서 더하기를 괄호로 묶으면, 최솟값을 찾을 수 있다. 문자를 자르기 위해 sstream을 이용했다.(코드 참고) ...

백준 1260번 c++ 문제풀이 문제: 백준 1260 풀이: dfs는 재귀함수로, bfs는 queue를 이용해서 풀었다. 2차원 벡터에 정점과 간선의 정보를 저장한다. dfs는 각 정점에 연결된 정점을 방문했으면 스킵, 아니면 그 정점으로 이동해서 반복한다. bfs는 각 정점에 연결된 모든 정점을 큐에 저장 후 시작 정점을 p...

백준 1012번 c++ 문제풀이 문제: 백준 1012 풀이: map[51][51]을 선언하고 배추가 심어져 있는 위치를 1, 아닌곳을 0으로 값을 입력해준다. map[x][y] = 1인 위치에서 dfs를 실행해주고, 방문했을 시, 1을 0으로 바꿔준다. dfs가 끝나면 result 값을 증가시켜줘서 총 몇번의 dfs함수를 실행하는...

백준 17626번 c++ 문제풀이 문제: 백준 17626 풀이: dp[i]를 i에 대해 최소개수라고 설정한다. dp[i] = dp[a] + dp[i+b]를 만족한다. 예를 들어. dp[5] = dp[1] + dp[4] dp[5] = dp[2] + dp[3] . . 이런 식으로 표현할 수 있다. 위의 예시처럼 여러가지로 표현할 ...

백준 11726번 c++ 문제풀이 문제: 백준 11726 풀이: 타일링의 규칙을 찾는다. dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 5 dp[5] = 8 위의 규칙을 따르면 점화식은 dp[n] = dp[n-1] + dp[n-2] 주의할 점은 문제에서 10007로 나눈 값을 구하라고 되어있다. 마지막에만 나눠주...

백준 11659번 c++ 문제풀이 문제: 백준 11659 풀이: 처음 문제를 봤을 땐 굉장히 단순한 문제라 쉽게 접근해서 그냥 누적 합을 일일이 구하면 풀 줄 알았지만 숫자가 커짐에 따라 시간이 오래거려서 시간 초과가 나고 말았다. 그래서 다른 방식으로 문제에 접근했다. dp로 접근해서, 1부터 n까지의 누적 합을 구해 저장해준다. ...

백준 9375번 c++ 문제풀이 문제: 백준 9375 풀이: <string, int> map을 선언한다. 입력받은 카테고리 별로 입력 받은 카테고리의 map의 int 값을 증가시킨다.(처음 값은 0) 조합의 문제이므로, 각각의 카테고리 수 + 1 만큼 씩 곱해주고(그 카데고리가 선택되지 않은 경우까지 포함) 마지막에...

백준 9095번 c++ 문제풀이 문제: 백준 9095 풀이: dp문제이다. dp로 풀수 있게 점화식 세운다. 1= 1 = 1 2= 1 1, 2 = 2 3= 1 1 1, 2 1, 3 = 1+2+1 = 4 4= 1 1 1 1, 2 2, 2 1 1, 3 1 = 1 + 1 + 3 + 2=7 5= 1 1 1 ...