문제https://school.programmers.co.kr/learn/courses/30/lessons/17679?language=cpp 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr애니팡이 생각나는 문제. 풀이구현 문제어떻게 쉽게 구현할 것인가…에 대한 식견1) 처음 생각한 풀이board를 순회하며 2x2에 모두 같은 값이 있는지 판단같은 값이 존재하는 경우 board에 표시대문제→소문자로 변경바꿀 때마다 cnt로 체크하기cnt가 0이면 바꿀 값이 없다는 의미므로 종료![문제] 이후 순회할 때 겹치는 문자 예외 존재!삭제삭제시 소문자들 모두 X로 바꾸기아래에서부터 순회하며 삭제한 칸인 경우 위에서 밀기바..

문제https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이문제를 읽으면 Flood fill을 사용하는 문제임을 알 수 있다. 잠시 Flood fill을 알아보면,Flood fill이란? 2차원 배열(혹은 다차원 배열)에서 주어진 시작점과 연결된 영역 전체를 찾아서 특정 값(색상 등)으로 바꾸는 알고리즘 Flood fill을 이용한 BFS의 기본적인 예제 문제이다. (0, 0)에서 (n-1, m-1)까지의 최단 경로를 찾아야 한다. 프로그래머스 특성상 다음의 처리만 잘 해주면 된다.방문할 수 없는 경우 -..

문제https://www.acmicpc.net/problem/2178 풀이사실 이 문제는 BFS의 기본 문제입니다. BFS가 처음이신 분들은 이 문제를 예제삼아 알고리즘의 정당성을 공부하면 좋습니다. 행렬에서 특정 점까지의 최단 경로를 구하는 문제이다. BFS를 이용하면 특정 점까지의 최단 경로가 보장되므로 방문 가능한 좌표들을 중심으로 BFS를 수행하면 된다.que에 {0, 0}을 추가하여 시작점으로 설정상하좌우를 확인하며 방문 가능한 경우(아래 조건 만족하는 경우)에 대해서만 방문 진행방문 체크가 안되어 있어야 함값이 0이 아니어야 함범위 안에 존재해야 함que에서 꺼낸 현재 좌표가 {N-1, M-1}일 때까지 반복한다. 코드#include#include#define IN(Y, X) (Y = 0 &&..

1. 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 풀이 아이디어 완전 탐색으로 로프의 모든 조합을 비교하면 부분집합의 개수를 구하는 문제와 같아진다. 이런 경우 2ⁿ의 가지수가 생긴다. 최대 N이 10⁵이므로 완전 탐색을 이용할 경우 무조건 시간 초과가 발생한다. DP를 사용하여 memoization한다고 해도 O(N²)의 시간 복잡도를 가지므로 제한 시간내에 통과할 수 없다. 따라서 더 빠른 풀이를 생각해야 한다. 그러..