문제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 &&..

문제문제 링크 풀이두 가지 풀이 방식을 소개해 보겠습니다.첫 번째 풀이는 흔히 생각할 수 있는 완전탐색으로 O(N²)의 풀이이고,두 번째 풀이는 단조 스택을 이용한 효율적인 풀이입니다.풀이 1현재(i)원소를 기준으로 남은 원소들(j)를 탐색하며 모두 비교한다.완전 탐색을 사용한 풀이이므로 아이디어는 생략하겠습니다.알고리즘 설명순서는 다음과 같습니다.모든 주식들이 떨어지지 않는다고 가정하에 ans 배열을 최대 날짜들로 초기화한다.price의 각 원소들을 비교하며 떨어진 날이 있을 경우에만 ans값을 업데이트한다. 구현 코드[python]def solution(price): ans = [len(price) - i - 1 for i in range(len(price))] for i in range(..

1. 문제https://www.acmicpc.net/problem/30237코드포스 Round899 B번 문제입니다.2. 풀이차집합 계산하기U = S1 ∪ S2 ∪ S3 ∪ ... ∪ Sn 이라고 해봅시다. 먼저 우리가 구하는 S는 완전탐색으로 생각해볼 수 있습니다. S₁부터 Sn까지 모든 부분집합을 Subset이라고 하면, 모든 Subset에 대해서 U - Subset을 비교하는 방법입니다. 즉,  전체합집합과의 차집합을 비교하는 것으로 생각할 수 있습니다. 하지만 Subset을 모두 탐색하면 O(2ⁿ)이므로 시간초과가 발생합니다.따라서 전체집합에서 원소를 하나씩 빼보는 방식을 생각했습니다. x ∈ U인 임의의 x에 대해 U - x를계산하면  x를 가지고 있는 모든 Si도 빠져야 합니다. 예를 들어 t..

1. 문제https://www.acmicpc.net/problem/1562 1562번: 계단 수첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net 2. 풀이DP적 접근비슷한 문제로 [백준 18044] 쉬운 쉬운 계단수가 있습니다. 이 문제를 먼저 이해해야 합니다. 이 문제는 기본적으로 [18044 쉬운 계단수]와 동일하게 최적 부분구조와 반복되는 부분문제를 가집니다. 하지만 쉬운 계단 수와는 다르게 "0부터 9까지 숫자가 모두 포함되어야 한다"는 조건이 추가되었습니다. 기존의 두 가지 정보를 이용한 DP 테이블로는 원하는 답을 얻을 수 없습니다. 따라서 부분문제를 해결할 때 "현재 구성된 계단수의 숫자의 조합"이라는 정보도 추가되어야..

1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 DP적 접근 문제를 읽고 세번째까지는 구조도를 그려봤습니다. 구조를 보면 결국 완전탐색을 통해 모든 경우의 수를 찾는 문제입니다. 그런데 다음 자리로 늘어나는 과정에서 완전탐색의 시간복잡도는 O(2ⁿ)이 됩니다. 따라서 DP나 그리디를 써야 하는데 아까 그린 구조도를 살펴보면 두 가지 특징을 가집니다. 반복되는 부분문제(Overlapping Subproblems) 다음 자리로 늘어나는 과정에서 같은 부분문제들이 반복됩니다. 최적 부분구조(Optimal Substructur) 위의 부분문제들..

1. 문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 2. 풀이 접근 방법 문제의 조건 중 "어떤 파티에서는 진실을 듣고 또다른 파티에서는 과장된 이야기를 들었을 때에도 거짓말 쟁이로 간주된다" 라는 표현이 핵심 포인트입니다. 저는 이 문제를 해결하는 과정에서 유니온 파인드를 떠올렸습니다. 처음에는 단순히 모든 파티들을 탐색하며 진실/거짓 여부를 확인하고 개수를 세어 주려고 했습니다. 하지만 테스트 케이스를 검증하다가 보니 예외가 존재합니다. 현재 ..