❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악1 ≤ 높이 H, 너비 W ≤ 100각 칸마다 `.` 또는 `c` 문자가 들어옴.✏️ 문제풀이간단한 시뮬레이션 구현 문제입니다.구름 위치(좌표)를 입력받은 뒤, 각 구름마다 실제로 이동시키면서 시간을 계산하는 방법.구름은 동쪽으로만 이동하고 외부 유입없다는 점에서 착안, 구름이 있는 칸은 '0', 그 오른쪽부터 한 칸마다 1, 2, 3, 4... 1씩 늘려가며 초기화하기.아무래도 두 번째 방법이 더 쉽고 간단하기 때문에 두 번째 방법을 사용하면 좋을 것 같습니다.읽은 문자가 `c`이면, 카운팅 변수를 0으로 초기화하고 현재 칸을 0으로 초기화.읽은 문자가 `.`이면, 카운팅 변수 1 증가하고, 현재 칸을 카운팅 변수로 초기화.카운팅 변수는 각 행마다 다시 ..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악1 ≤ N ≤ 100소문자와 숫자로만 이루어진 문자열 길이 ≤ 100✏️ 문제풀이생각해야 할 반례가 많아서 조금 복잡한 문제입니다.반드시 조건을 먼저 정리하고, 어느정도 손코딩을 마친 뒤에 코딩에 들어가야 햇갈리지 않습니다. 문자열을 처음부터 끝까지 읽다가 숫자를 만난다면,'0'으로 시작하는 숫자인 경우'0'이 아닌 문자 (숫자 또는 소문자)가 나올 때까지 스킵합니다. (단순히 인덱스 변수 증가)이때 세 가지 경우가 발생합니다.다른 숫자를 만난 경우: 아래 '0'으로 시작하는 숫자가 아닌 경우로 이동 후 처리됩니다.소문자를 만난 경우: "00000... " 같은 경우였네요, 토큰을 "0"으로 초기화 해줍니다.문자열 범위를 벗어난 경우 (즉, 문자열 가장 뒤..

https://www.acmicpc.net/source/88126015      ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악"end"가 나올 때까지 계속 입력받기각 패스워드 문자열 20글자 이하, 대문자로만 이뤄진 문자열✏️ 문제풀이문제에 주어진 세 가지 조건을 빠짐없이 구현하기만 하면 되는 문제입니다. 다른 방법은 없습니다. 첫 번째 조건: 모음(a,e,i,o,u) 하나를 반드시 포함하는지 검사하기inline bool isVowel(char c) { return (c=='a') || (c=='e') || (c=='i') || (c=='o') || (c=='u');} 두 번째 조건:모음 또는 자음이 3개 연속으로 오면 안 된다.각 글자마자 모음인지 자음인지 판단합니다. 모음이면 모음 카운터 변수 증..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악요소 개수: 1 ≤ N ≤ 1,000각 요소의 최댓값(상한): 1 ≤ C ≤ 1,000,000,000✏️ 문제풀이빈도 정렬의 기준은 '많이 등장한 순'으로, 등장횟수가 같다면 '앞서 등장한 순'입니다.즉, 각 숫자와 대응하는 인덱스의 값마다 아래와 같은 정보를 갖고 있어야 합니다.이 숫자가 몇 번 등장했는지이 숫자가 언제 처음 등장했는지로직은 다음과 같습니다.숫자를 입력받습니다. 등장횟수, 첫 등장 인덱스 번호 정보를 함께 저장합니다.처음 등장했다면, 등장횟수는 1 입니다.처음 등장한 숫자가 아니라면, 삽입하지 말고 등장횟수만 1 증가시킵니다.문제에 나온 빈도 정렬의 기준에 따라 정렬합니다.원하는대로 정렬시켜주는 STL 함수는 없기 때문에 따로 정렬 함수객..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악입력칸 수 N, 바구니의 크기 M, (1 ≤ M 사과의 개수 J (1 ≤ J ≤ 20)출력: 바구니 이동거리 최솟값✏️ 문제풀이최소로 이동하기 위해서는 최대한 바구니 양끝에서 사과를 받는게 이득이라는 건 쉽게 떠올릴 수 있습니다.만일 반대쪽에서 사과가 떨어진다면, 조금 덜 이동할 수 있을거고,사과가 바구니 안쪽으로 떨어질 가능성도 높아질 테니까요. 로직 자체는 상당히 간단합니다.사과가 떨어지는 위치가 왼쪽 끝에서 가까운지 아니면 오른쪽 끝에서 가까운지 판단합니다.더 가까운 방향으로 이동합니다. 단, 딱 사과가 위치한 지점까지만 움직이면 되겠습니다. 그렇다면, 왼쪽을 `l`이라 하면 오른쪽 끝 `r`을 어떻게 표현할 수 있을까요?바구니 크기 `M == 1`이..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악가로/세로 길이를 나타내는 N, 1 ≤ N ≤ 64N개의 문자열, 0과 1로 이뤄져있음.✏️ 문제풀이재귀 가능성 판단하기 전체 흑백영상을 압축하는 과정은 4개의 부분영상 중 하나를 압축하는 과정과 같습니다. 위 그림을 보면 길이만 절반으로 줄어들 뿐이고,범위 내에 있는 데이터가 모두 같다면 그냥 출력하고하나라도 다르다면, 2, 1, 3, 4사분면 순서대로 꼭짓점 위치에서 범위를 절반으로 줄이고 다시 검사하면 됩니다.N은 최대 64, 최대 데이터 수는 $2^{16}$으로 많지 않습니다. 이렇게 전체 문제와 부분 문제가 같다는 점 + 처리할 데이터가 많지 않다는 점을 파악해서 재귀로 풀 수 있어야 합니다. 풀이과정시작점 `(y, x)`에서 가로, 세로로 `l..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악의도적으로 좌표 햇갈리게 만든 문제입니다.만일 평소 자신에게 익숙한 좌표계나 문자(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를 돌려 방문할 수 있는 모든 칸에 방문표시를 합니다. 이게 하나의 집합이 됩니다.배추밭을 더 순회합니다.아직 방문표..