0=2

문제https://www.acmicpc.net/problem/2667 문제 이해N × N 크기의 정사각형 지도에서 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.집이 있는 곳(1)끼리 상하좌우로 연결시켜 단지를 만든다.총 단지수와 단지내 집의 수를 오름차순으로 출력한다. 문제 풀이 🔍 접근 집이 존재하는 곳을 기준으로 그 집의 상하좌우에 또 다른 집이 존재하는지를 판단하는 그래프 탐색 문제로 볼 수 있다.지도를 순회하면서 '1'이 나왔을 때 모든 인접 정점을 방문하여 연결된 집의 개수를 구한다.  🔨 구현 BFS와 DFS를 이용하여 풀 수 있다.방문 표기는 visited 배열을 만드는 대신 지도에서 방문한 곳을 '0'으로 바꾸어 표기할 수 있다.집이 있는 곳에서 dr, dc 배열을 이용해서 상..

문제https://www.acmicpc.net/problem/3085 문제 이해N×N 크기의 보드에 사탕을 4가지 색으로 채워져있다.인접한 두 칸을 골라 사탕을 서로 교환한다.행 또는 열에서 같은 색으로 이루어져 있는 가장 긴 연속 부분을 구한다. 문제 풀이 🔍 접근 모든 경우의 수를 탐색하는 시간복잡도를 계산해보면,사탕을 교환하는 데 N * N, 연속하는 최대 개수를 구하는 데 N * N 이므로 총 O(N^4)이다.N ≤ 50이므로 제한시간 내에 계산할 수 있다. 💡 브루트포스행/열에서 인접한 두 칸을 골라 서로 사탕을 교환한다.연속하는 행/열의 최대 개수를 찾는다.1회 교환할 때마다 최대 개수를 찾는다. 코드#include #include using namespace std;/*1. 행/열에서 인..

문제https://www.acmicpc.net/problem/1789 문제 이해서로 다른 N개의 자연수의 합이 S이다. S가 주어질 때 N의 최댓값을 구한다. 문제 풀이💡 아이디어N이 최대가 되려면, 자연수를 1부터 차례대로 더하는 방식을 생각할 수 있다. 1 + 2 + 3 + 4 + ... = S 이런식으로 더할 경우 N이 최대가 된다.1 + 2+ 3 + ... + n = n * (n + 1) / 2 인 점을 이용해서 예시를 살펴볼 수 있다.예: 2001 + 2 + 3 + ... + 18 + 19 = 190 에서 10을 더하면, 서로 다른 수라는 조건을 만족하지 못한다.1 + 2 + 3 + ... + 17 + 18 = 171 이므로, 29를 더하면 200이 된다.N의 최댓값은 19이다. 🔨 구현반복..

문제https://www.acmicpc.net/problem/15650 문제 이해1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.고른 수열은 오름차순이어야 한다. 문제 풀이💡 DFS를 이용한 백트래킹 이전에 올린 N과 M (1) 문제에서, 출력할 수열이 오름차순인 것만 추가되었다. [BOJ][C++] 백준 15649번: N과 M (1)문제https://www.acmicpc.net/problem/15649 문제 이해1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구한다. 문제 풀이💡DFS를 이용한 백트래킹    1부터 N까지 재귀함수를 이용해 탐색하y-e-99.tistory.comN과 M (1)과 풀이 방식이 비슷한데, for 반복문에서 i값을 이용하면 중복없이 오름..

문제https://www.acmicpc.net/problem/15649 문제 이해1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구한다. 문제 풀이💡DFS를 이용한 백트래킹    1부터 N까지 재귀함수를 이용해 탐색하며 중복 없이 M개의 수를 선택하고 출력한다.종료 조건: M개의 수를 모두 선택했을 때탐색- 1부터 N까지 탐색을 반복한다.- 수를 중복해서 선택하지 않도록 방문 표기한다.- 탐색한 수를 출력할 배열에 삽입한다.- 탐색이 끝난 수를 배열에서 제거하고 방문하지 않은 수로 표기한다.탐색 종료- 선택한 M개의 수가 담긴 배열을 출력 후 탐색을 종료한다. 코드#include#includeusing namespace std;int N, M;vector v;vector visited;..

문제https://www.acmicpc.net/problem/2002풀이🔍 접근차가 들어간 순서를 숫자로 나타내기A차가 다른 차를 추월했다는 것을 아는 방법(1) A의 들어갈 때 인덱스보다 나올 때 인덱스가 작으면 추월?       → 들어갈 때 인덱스가 A보다 큰 차들이 추월하면서, A의 나올 때 인덱스도 뒤로 밀릴 수 있으므로            A의 인덱스 비교만으로는 판단할 수 없다.(2) A보다 늦게 나온 차 중에서, A보다 들어갈 때 인덱스가 작은 차가 하나라도 있으면      A보다 먼저 들어왔는데 A보다 뒤에 나온 것이므로 A는 터널 안에서 추월을 했다고 판단한다.🔨 구현map을 이용해 차량 번호(key)와 들어간 순서(value)를 저장한다.vector에 나온 차의 차량 번호를 저장한..

문제https://www.acmicpc.net/problem/20546풀이성민(BNP)남은 현금으로 주식을 살 수 없을 때까지 주식 매수준현(TIMING)3일 연속 가격 상승: 전량 매도3일 연속 가격 하락: 전량 매수매수할 때는 (성민과 똑같이) 남은 현금으로 주식을 살 수 없을 때까지 매수코드#include #include using namespace std;const int DAY = 14;int bnp(int cash, vector &price) { int stock = 0; for (int i = 0; i = 0) { cash -= price[i]; stock++; } } return stock * price[DAY - 1..

문제https://www.acmicpc.net/problem/1212풀이💡 8진수 한 자리는 2진수 세 자리로 변환할 수 있다.(ex) 0 → 000, 1 → 001, ... , 7 → 111 1. 0 ~ 7 을 2진수로 변환한 문자열 배열을 생성한다.2. 입력받은 8진수 수를 앞에서부터 한 자리씩 2진수로 변환한 문자열로 출력한다.    *이때, 맨 앞의 수가 0으로 시작하지 않도록 int로 변환한다. 🚨 자릿수 유의    - 주어지는 수의 길이는 333334 이하이고 이진수로 변환하면 333334*3이다.    - 맨 앞의 수만 int형으로 바꾸지 않고 전체를 int형으로 바꾸면 범위를 초과한다. 코드#include #include using namespace std;int main() { ..

문제https://www.acmicpc.net/problem/9184풀이문제에 나와있는 함수를 작성하면 아래와 같다.int w(int a, int b, int c) { if (a 20 || b > 20 || c > 20) return w(20, 20, 20); else if (a  재귀의 횟수를 줄이기 위해 w의 결과 값을 dp 배열에 저장할 수 있다.a, b, c의 값에 따른 결과값을 저장하기 위한 3차원 dp 배열을 선언한다.w(a, b, c) 함수를 실행했을 때 배열에 이미 저장된 값이면, 재귀 과정을 생략하고 그 값을 불러온다.배열에 값을 저장할 때 인덱스에 음수 또는 20 이상의 수가 들어가지 않도록 유의한다.코드#include #include using namespac..