❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악의도적으로 좌표 햇갈리게 만든 문제입니다.만일 평소 자신에게 익숙한 좌표계나 문자(N, M, x, y)가 아니라면 주의해서 문제를 읽도록 합시다.세로가 M, 가로가 N (M, N ≤100)K개의 직사각형 좌표 왼쪽 아래 꼭짓점 (x, y), 오른쪽 위 꼭짓점 (x, y)모눈종이의 왼쪽 아래 꼭짓점의 좌표가 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다.이거 때문에 햇갈릴 필요 없습니다.만일 자신에게 편한 좌표계가 왼쪽 위 꼭짓점이 (0, 0), 오른쪽 아래 꼭짓점이 (M, N) 이라면 그냥 원래대로 두고 풀어도 영역의 넓이가 달라지진 않기 때문입니다. 그냥 그림이 거울대칭으로 뒤집혔다고 생각하면 됩니다.✏️ 문제풀이윗 절에서 언급했듯, 햇갈리는 ..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악N × N 크기의 맵, 2 ≤ N ≤ 100각 칸마다 1 ≤ 높이≤ 100아무 지역도 물에 잠기지 않을 수도 있다.✏️ 문제풀이문제에 나와있지 않은 조건을 당연히 그럴거라 추측하고 풀면 안 된다는걸 연습하기 좋은 문제입니다.물의 높이를 당연히 1부터 시작할거라 생각했다면, 당한겁니다.문제 어디에도 '비가 무조건 내려야 한다'는 말이 없기 때문에, 일단 0부터 시작해야 합니다.물의 높이는 0부터 시작해서 입력받은 N × N 칸의 높이 중 가장 큰 높이까지 (또는 그냥 100까지)를 검사하면 됩니다. 검사는 다음과 같은 과정으로 이뤄집니다.'물에 잠기지 않은 임의의 칸'(즉, `arr[y][x] > 물의 높이`) 부터 시작.현재 물에 잠기지 않았고, 연결돼있..

들어가며...알고리즘 문제를 풀다 보면 `std::vector` 또는 `std::array` 같은 코드를 사용하곤 합니다.우리에게는 `bool [N]`이 너무나도 익숙하고, 위와 같이 작성하더라도 별 문제가 발생하지 않기 때문입니다. 하지만, 실무적이고 객체지향적인 코드 작성과는 조금 멀리 떨어져있는 PS를 하면서도`std::vector`은 사용을 지양하세요~같은 문구를 종종 보곤합니다. 항상 그 이유가 궁금했지만, 그때마다관련 내용 조금 찾아보기어려운 내용에 질겁 → 결론 위주로 탐색'아하 그래서 `std::bitset` 쓰라는 거구나?'막상 `std::bitset` 써보니 불편함다시 `std::vector`로 회귀를 몇 번이고 반복하고 나니 이젠 잘 모르겠더라도 한 번은 정리를 해놔야 속이 시원할 것..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력:테스트케이스 T (제한 따로 없음)배추밭: 1 ≤ N, M ≤ 50, 가로M, 세로N 순으로 입력됨.배추 개수 1 ≤ K ≤ 250 + 각 배추의 위치 (x좌표, y좌표 순으로 입력됨)위치가 같은 배추는 없습니다.출력: 필요한 최소 지렁이 개수 (Connected component 개수)✏️ 문제풀이서로 연결된 칸들의 집합, 그 집합이 몇 개 있는지를 구하는 connected component 구하기 문제입니다.DFS, BFS 양쪽 모두로 풀 수 있습니다. 배추의 개수 및 위치를 입력받기 때문에배추 하나를 시작점으로 DFS 또는 BFS를 돌려 방문할 수 있는 모든 칸에 방문표시를 합니다. 이게 하나의 집합이 됩니다.배추밭을 더 순회합니다.아직 방문표..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력:N × M 미로, '붙어서' 들어오는 입력`scanf("%c")` 이용또는 `std::string`으로 한 줄 입력받은 후 `for()`로 처리또는 `std::string`으로 한 줄 입력받은 후 그대로 사용하기2 ≤ N, M ≤ 100출력: (N, M)에 도달하기 까지 밟아야 하는 최소 칸 수시작하는 칸, 도착하는 칸도 밟은 칸 수에 포함됩니다.✏️ 문제풀이최소 칸 수 = 최적해가중치 없음 (모든 칸이 한 칸 이동에 동일하게 한 칸 소요) = BFS 이용방문표시 후 시작점 queue에 `push`4방향 중 갈 수 있는 칸은 queue에 `push`하고 방문표시 합니다.queue가 빌 때까지 반복합니다.4방향 검사하기미로의 경계범위를 넘어서지 않았고..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 각 테스트케이스마다 2와 5로 나누어 떨어지지 않는 정수 N(1 ≤ N ≤ 10000)출력: 각 자릿수가 모두 1로만 이루어진 n의 배수의 자릿수✏️ 문제풀이[Tip] 정해지지 않은 입력 개수 입력받기 = `while (cin >> n)` 1. 증명하기이 문제는 정답을 정수 자료형에(`int`(12자리), `unsigned long long`(20자리)) 담을 수 없습니다.따라서 구해야하는 답인 '자릿수'에 집중해봅시다. $x$가 n의 배수라는 뜻은, $x \pmod n = 0$ 이라는 뜻입니다.그리고, 모듈로 연산(`%`)은 분배법칙이 성립합니다. $x \pmod n = 0$ 이고, $x$를 이전 규칙으로 표현하면 $((x\div10) - 1) ..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 2,147,483,647 이하의 자연수 A, B, C출력: A를 B번 곱한 수를 C로 나눈 나머지  ($A^B \pmod C$)✏️ 문제풀이첫 시도 :: 잘못된 접근나누는 수에 따라 나머지가 반복되는 성질이 있는 일부 수가 있는데, 모든 수가 그럴 것이라 생각하고 풀었습니다.그러나, 반드시 모든 수가 나머지가 반복되진 않습니다.ull A, B, C, result = 1;cin >> A >> B >> C;set s;while (B--) { result = (result * A) % C; if (s.find(result) != s.end()) break; s.insert(result);}cout `std::set`을 이용해서, 나머지가 반복될 때 멈춥..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 'A', 'B'로만 이뤄진 문자열, 길이 ≤ 100'000, 문자열 개수 N ≤ 100출력: 좋은 단어 개수✏️ 문제풀이'교차하지 않는다', '짝을 찾는다' 같은 용어는 먼저 '스택'을 떠올립시다.단어 내 문자를 하나씩 스택에 넣습니다.현재 top이 가리키는 문자와 똑같은 문자라면, 위 그림과 같이 서로 사라집니다.문자열 끝까지 탐색했는데,스택이 비어있다면, 좋은 단어입니다.스택이 비어있지 않다면, 좋은 단어가 아닙니다.📝 코드#include using namespace std;int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int N; cin >> N..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력재료개수: 1 ≤ N ≤ 15,000갑옷 1개 만드는 데 필요한 수: 1 ≤ M ≤ 10,000,000A[i] ≤ 100,000, 중복없음출력: 갑옷을 만들 수 있는 개수 ✏️ 문제풀이중복된 번호는 없기 때문에 A + B = M이 성립하는 재료 A, B를 발견하면 바로 선택하면 됩니다. (임의의 재료를 어느 재료와 조합하냐에 따라 만들 수 있는 갑옷 개수가 달라지거나 그렇지 않기 때문입니다.)하지만, 모든 경우의 수를 탐색하려면 $O(N^2)$이 소요되는데, N이 최대 15,000이므로 시간제한 2초내에 풀 수 없습니다.(사실 이 문제는 이렇게 풀어도 통과는 됩니다)더 효과적으로 탐색하려면, 투포인터를 사용하면 됩니다.재료 번호를 저장한 배열을 정렬한..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 알파벳 대문자로만 된 최대 50글자 문자열출력:팰린드롬을 만들 수 있다면, 팰린드롬을 출력하고팰린드롬을 만들 수 없다면, "I'm Sorry Hansoo"를 출력✏️ 문제풀이팰린드롬을 만들기 위해서는 반드시 문자열이 중간지점을 기점으로 대칭이어야 합니다.대칭이 되기 위해서는, 홀수번 등장하는 알파벳이 없거나 1개만 존재해야 합니다.즉, 홀수번 등장하는 문자가 2개 이상이라면, 해당 문자열은 팰린드롬을 만들 수 없습니다. 이런 맥락에서 보면, 팰린드롬은 다음과 같은 형태입니다.2회 이상 등장한 문자들을 각각 등장횟수 절반만큼 먼저 사전순으로 나열합니다.이렇게 나열한 문자열은 접두사(prefix)입니다. 나중에 이걸 뒤집어서 뒤에 붙이면, 모든 등장횟..