프로그래머스 코딩 문제/카카오 기출문제 (13) 썸네일형 리스트형 [프로그래머스] 보행자 천국 (2017 카카오코드 예선) (level 3) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1832 문제를 읽어보니 순간 두 가지 방법이 떠올랐다.-> dfs,bfs를 이용하는 방법, dp를 이용하는 방법. 이차원배열의 크기가 500*500=250000되는 것만 보아도 dfs,bfs를 이용하면 시간초과를 훌쩍 넘길 것을 예상할 수 있다. 게다가 20170805으로 나눈 나머지값을 리턴하라는 것만 보아도 시간초과를 예상할 수 있다. 당연히 방법은 dp를 사용하여야 한다. 1. 배열은 이차원이라 d[502][502] 를 선언해야 하지만 각 위치마다 위에서 내려온 경로, 왼쪽에서 온 경로 두가지를 나눠 저장해야 했기때문에 d[502][502][2]를 선언하였다. 0은 위에서 온 경우,, 1은 왼.. [프로그래머스] 카카오 프렌즈 컬러링북 (2017 카카오코드 예선) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829 단순 bfs문제이다. 1. 이차원 배열을 하나씩 순차 탐색한다. 2. 순차 탐색할 때 방문하지 않았고 색칠되어 있는 장소마다 bfs를 돌려준다. 3. bfs를 돌릴 때 queue에 들어간 개수를 카운팅해 영역의 크기를 max_area와 비교해 나간다. 3. bfs돌린 횟수가 결국 색칠한 영역의 개수이고 max_area(코드에서는maxx)가 제일 큰 영역의 크기이다. 1. 원소가 0인 부분은 색칠이 되어 있지 않은 부분이다. 색칠 되어 있지 않은 부분은 영역으로 치지 않는다. #include #include #include #include using namespace std; bool chec.. [프로그래머스] 문자열 압축 (2020 KAKAO BLIND RECRUITMENT) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60057 문자열 절단 단위를 1,2,3 ..... 증가시켜가며 각각 문자열 길이가 최소인 경우를 찾는다. 1. 원래 문자열을 자를 문자열 절단 단위를 1부터 반절까지 증가시키며 자른다. 2. 문자열 절단 단위(i)가 하나 정해지면 처음붙터 문자열 단위 씩 자르면서 전 문자열과 비교한다. 2-1 전 문자열과 현재 문자열이 같다면 total_size에서 문자열 절단 단위(i)만큼 뺀다. 2-2 전 문자열과 현재 문자열이 다르다면 증가시켜온 same_count 정수의 자릿수만큼 total_size에 더한다. 3. 문자열 절단 단위마다 문자열 길이가 최소인 값을 찾는다. #include #include #.. 이전 1 2 다음