티스토리

soreDemo 님의 블로그

검색하기

블로그 홈

soreDemo 님의 블로그

sore-demo.tistory.com/m

soreDemo 님의 블로그 입니다.

구독자: 0

방명록 방문하기

주요 글 목록

알고리즘 :: 백준 :: 4179 - 불! ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악행 R, 열 C (1 ≤ R, C ≤ 1000)지훈이 위치는 오직 1개탈출할 수있다면 탈출까지 걸린 최소시간없다면 "IMPOSSIBLE" 출력✏️ 문제풀이동시성 구현이 문제에서 가장 까다로운건 '동시성'을 어떻게 해결할지에 대한 고민입니다. 불과 지훈이는 동시에 이동하기 때문입니다.기존 BFS를 돌릴 때, 우리는 큐가 빌 때까지 돌리기 위해 `while(!q.empty())`를 관용구 처럼 사용했습니다.하지만, 이번에는 다릅니다. 현재 시간에 큐에 들어있는 요소들을 처리하는 동안 다음 시간에 이동할 예정인 칸들이 큐에 들어오기 때문입니다. 이것들은 '지금' 처리하면 안 되겠지요.이러한 문제에서 '지금', '현재' 큐에 들어있는 요소만 처리하기 위해서 for.. 공감수 0 댓글수 0 2025. 1. 16.
알고리즘 :: 백준 :: 16234 - 인구 이동 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악땅 크기 N×N (1 ≤ N ≤ 50)L ≤ 인구 차이 ≤ R (1 ≤ L ≤ R ≤ 100)✏️ 문제풀이문제에 인구 이동 로직이 나와있기 때문에 그대로 실수없이 구현하면 되는 문제입니다.인구 이동 과정은 ① 연합 만들기 - ② 인구 이동 - ③ 인구 이동 ? 시간 증가 : 종료 후 정답 출력으로 요약할 수 있습니다. 코드로 간략하게 나타내면 다음과 같습니다.while (true) { // 1. 연합 만들기 for (int y = 0; y 연합은 임의의 시작점을 기점으로 DFS를 1회 돌리면 만들 수 있습니다.갈 수 있는 모든 국가에 방문표시 및 외부 배열에 좌표를 저장합니다. 이렇게 연합이 만들어지면, 인구 이동을 실시합니다. 모든 점을 검사했는데.. 공감수 0 댓글수 0 2025. 1. 16.
알고리즘 :: 백준 :: 2589 - 보물섬 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악가로, 세로 ≤ 50✏️ 문제풀이육지칸 중에서 서로 다른 두 점을 골랐을 때, 가장 먼 거리를 구하는 문제입니다.이때, 일부러 돌아가서는 안 되고, 무조건 최단거리로 갔을 때의 거리 기준입니다. 두 정점 사이의 최단거리를 구해야 하므로 가장 먼저 BFS를 떠올립니다. 로직은 다음과 같습니다.모든 육지칸의 좌표를 `queue>`에 저장합니다.이 큐가 모두 빌 때까지 while문을 돌리는데,각 육지칸을 시작점으로 BFS를 돌립니다.BFS를 하면서 외부 배열에 방문여부 및 거리를 기록합니다.BFS를 마쳤다면 다시 전체 맵을 검사해 가장 거리가 길 때를 찾고 답을 갱신합니다.위 로직을 코드로 구현하면 다음과 같습니다.for (const auto& land : la.. 공감수 0 댓글수 0 2025. 1. 16.
알고리즘 :: 백준 :: 15686 - 치킨 배달 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악크기가 N×N인 도시, N(2 ≤ N ≤ 50)최대 치킨집 개수 M(1 ≤ M ≤ 13)집의 개수 ≤ 2NM ≤ 치킨집의 개수 ≤ 13도시의 치킨 거리의 최솟값✏️ 문제풀이우선, 문제를 bruteforce로 풀 수 있는지 확인하기 위해, 최악의 경우 몇 번 연산이 필요한지 생각해봅시다.N이 50이고, 총 치킨집이 13개 있으며, 여기서 6개 (또는 7개)를 뽑는 경우라고 생각합시다.치킨집을 뽑는 총 경우의 수는 $_13C_6 = 1,716$입니다.각 경우의 수마다 최대 100개의 집에 대해 치킨거리를 검사합니다.∴ 충분히 시간제한 1초 내로 문제를 풀 수 있다고 판단됐으니, 바로 로직을 생각하러 넘어갑시다.A개 중에서 B개를 뽑는 조합 (combinatio.. 공감수 0 댓글수 0 2025. 1. 15.
알고리즘 :: 백준 :: 17298 - 오큰수 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악수열 A의 크기 N (1 ≤ N ≤ 1,000,000)✏️ 문제풀이3 5 2 7예제 입력 1을 먼저 생각해봅시다.3은 5와 짝지어집니다.5는 7과 짝지어집니다.2는 7과 짝지어집니다.그래서 결과적으로 `5 7 7 -1` 이라는 답이 나옵니다.짝 지어짐, 짝을 찾음 이라는 개념에서 '스택'을 떠올리셔야 합니다. (관련문제: 9012 :: 괄호, 4949 :: 균형잡힌 세상)스택의 가장 위에 있는 값 (`top()`)보다 작은 값을 만나면 스택에 `push()` 됩니다.반면에 더 큰 값(`big` 이라고 할까요?)을 만나면 `big`보다 큰 값이 스택의 가장 위에 올 때까지 `pop()` 합니다. (없다면 스택이 비게 되겠지요)`pop()` 하면서 오큰수를 저.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 1325 - 효율적인 해킹 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악N개의 컴퓨터 ≤ 10,000, M개의 관계도 ≤ 100,000컴퓨터 번호는 1번부터 N번한 번에 가장 많이 해킹할 수 있는 컴퓨터 번호를 오름차순으로 (하나면 한개, 두 개 이상이면 오름차순으로)✏️ 문제풀이트리도 그래프의 일종임을 생각하면 어렵지 않게 접근법을 생각할 수 있습니다. 입력으로 들어오는 A, B는 'A가 B를 신뢰한다' = 'B를 해킹하면 A도 해킹할 수 있다' = B → A로 생각할 수 있습니다. 즉, 문제에서 말하는바와는 반대방향으로 간선이 만들어지는 겁니다. A가 B를 신뢰하지만, 간선은 B에서 A를 향하도록 만들어집니다 이렇게 간선을 이어서 트리를 형성했을 때, 한 번에 가장 많이 해킹할 수 있는 컴퓨터란, 해당 노드를 시점으로 DF.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 1068 - 트리 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악노드 개수 N ≤ 50입력: 0 ~ (N-1)번 노드의 부모 정보, 루트노드는 -1출력: 리프노드의 개수✏️ 문제풀이문제에 나와있지 않은 조건을 자신도 모르게 '당연히 그러겠지~'라고 생각하고 풀지 않기를 연습하기 좋은 문제입니다.(비슷한 문제로 2468 :: 안전영역이 있습니다.) 문제 어디에도 주어지는 노드가 '이진 트리'라는 정보가 없습니다. 예시로 주어지는 그림이 이진트리라 햇갈리기 정말 좋습니다. 정말로 트리를 구현할 필요는 없습니다.각 노드의 부모가 입력되므로 배열의 각 칸마다 자식노드의 번호들을 저장하면 됩니다.이때, 앞서 언급했듯이 이진트리가 아니기 때문에 각 칸마다 왼쪽/오른쪽 자식노드의 번호를 저장하기 위해 `std::vector>` 타입.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 2636 - 치즈 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악가로, 세로 ≤ 100출력: 치즈가 모두 녹는데 걸리는 시간, 모두 녹기 직전에 남아있던 치즈 칸 개수✏️ 문제풀이시뮬레이션(구현) + DFS/BFS 문제로, 문제가 요구하는대로 그대로 구현하면 됩니다.하지만, 바로 코딩에 들어가지 마시고 순서대로 어떤 절차를 밟을지 간단하게나마 손코딩을 한 후 진행합시다.`while(치즈가 남아있는 동안)` - 전체 칸을 순회하며 치즈가 있는지 확인하는 함수가 필요합니다.`(0, 0)` 공기를 시작점으로 DFS 또는 BFS를 돌려서 치즈를 만나면 '녹았다' 표시를 합니다.`(0, 0)`은 무조건 공기입니다. 문제에 '가장자리에는 치즈가 없다'고 나와있기 때문입니다.이 과정이 끝나면, 공기와 맞닿은 치즈는 '녹았다' 표시가.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 14502 - 연구소 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악세로 크기 N, 가로 크기 M (3 ≤ N, M ≤ 8)0은 빈 칸, 1은 벽, 2는 바이러스2 ≤ 바이러스 개수 ≤ 103 ≤ 빈 칸출력: 안전영역의 최대크기✏️ 문제풀이안전영역의 최대 크기를 구하기 위해서는 주어진 빈칸들 중 3칸을 선택할 수 있는 모든 경우의 수를 따져봐야 합니다.연구실 크기는 최대 8 × 8 = 64칸입니다.최악의 경우, 벽이 하나도 없고 바이러스가 2개 있다면, 3개의 벽을 세울 수 있는 경우는 62 × 61 × 60 = 약 22만충분히 모든 경우의 수를 계산할 수 있습니다. 로직은 다음과 같습니다.선택한 빈칸 3칸을 `1`로 만들어 벽을 세웁니다.DFS 또는 BFS를 이용해서 시뮬레이션을 돌립니다. 각 바이러스마다 갈 수 있는 모.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 4949 - 균형잡힌 세상 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악100글자보다 짧은 문장 입력문장 입력 : `getline(cin, str)`온점 "." 하나 입력될 때까지 입력 반복균형 문자열이면 "yes", 아니면 "no"✏️ 문제풀이9012 :: 괄호 문제의 진화버전입니다.역시 괄호 / 짝 찾기 문제이므로 스택을 사용한다는 것을 떠올려야합니다. 소괄호는 소괄호끼리, 대괄호는 대괄호끼리 짝지어집니다.스택이 비어있거나, 여는 괄호 (`(` 또는 `[`)를 만났다면 스택에 `push()`하며 나아갑니다.닫는 괄호(`)` 또는 `]`)를 만났다면, 스택 가장 위에 있는 것과 짝을 이루는지 확인합니다.짝을 이루지 않는다면 더 볼 것도 없습니다. 해당 문장은 균형 문자열이 아닙니다.📝 코드#include using name.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 9012 - 괄호 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악여러개의 테스트케이스 T입력: 2 ≤ 각 괄호문자열 길이 ≤ 50출력: 괄호문자열이면 "YES", 아니면 "NO"✏️ 문제풀이괄호, 짝을 찾는다 같은 표현은 '스택'을 생각합시다. 현재 스택이 비어있거나, 여는 소괄호(`(`)를 만나면 스택에 `push()` 하면서 나아갑니다.닫는 소괄호를 만나면스택 가장 위에 있는 괄호가 여는 소괄호(`(`)인지 확인합니다.맞다면, `pop()` 하고, 아니라면, 해당 문자열은 괄호 문자열이 아닙니다.문자열 끝까지 순회했는데, 스택이 비어있지 않고 무언가 남아있다면해당 문자열은 괄호 문자열이 아닙니다.📝 코드#include using namespace std;int main() { ios::sync_with_stdio(.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 1436 - 영화감독 숌 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악입력: N ≤ 10,000출력: N번째 종말의 수✏️ 문제풀이함정문제입니다.0666, 1666, 2666, 3666, 4666, 5666,6660, 6661, …., 6669, 7666, 8666, 9666총 19개… 그게 10666부터 11666까지…이렇게 빠져들기 시작하면 이 문제의 함정에 빠진 것입니다 ㅎㅎ함정에 걸리는 가장 큰 이유는 N이 10,000까지 가능해 오버플로우가 될 수도 있다고 생각하기 때문입니다. 단순하게 666부터 카운팅하면서 1,000으로 나머지연산(`%`)한 것이 666인 수를 찾으면 됩니다.while (temp) { if (temp % 1000 == 666) { answer++; break; } temp.. 공감수 0 댓글수 0 2025. 1. 8.
알고리즘 :: 백준 :: 2852 - NBA 농구 https://www.acmicpc.net/source/88151964 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악득점 개수 1 ≤ N ≤ 100각 득점 정보는 문자열로 "mm:ss" 형식출력: 1번팀이 이기고 있던 시간, 2번팀이 이기고 있던 시간✏️ 문제풀이1. 시간(초)을 하나의 칸으로 생각하는 방법'분'과 '초' 서로 다른 단위가 있을 때는 어느 한 쪽 단위로, 되도록이면 작은 단위로 통일하는 것이 좋습니다.농구경기 48분을 초로 환산하면 2,880초이므로 전체 농구경기를 연속된 2,880칸으로 표현할 수 있습니다. 문자열 "mm:ss"가 주어졌을 때, `int` 타입의 초로 환산하는 방법은 다음과 같습니다.60 * stoi(line.substr(0, 2)) + stoi(line.subst.. 공감수 5 댓글수 1 2025. 1. 8.
알고리즘 :: 백준 :: 3474 - 교수가 된 현우 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악입력: 테스트 케이스 T입력: 각 테스트 케이스마다 정수 1 ≤ N ≤ 1,000,000,000출력: $N!$를 나타냈을 때 오른쪽 끝에 있는 0의 개수✏️ 문제풀이당연히 `int`든 `unsigned long long`이든 수의 범위를 가볍게 넘어가기 때문에 직접 계산하는 문제가 아닙니다 ㅎㅎㅎ 0을 만들기 위해서 필요한 '재료'는 2와 5가 있습니다.$N!$를 나열하는 과정에서 2, 4, 6, 8 ... 정말 많은 2가 생성됩니다. 즉, 2라는 재료는 넘쳐난다는 뜻입니다.따라서, 0을 만들기 위한 '핵심재료'는 5입니다. $N!$ 속에 5가 몇 개 있느냐에 따라 0의 개수가 결정됩니다.코드로 나타내면 정말 간단합니다.for (int i = 5; i N .. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 10709 - 기상캐스터 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악1 ≤ 높이 H, 너비 W ≤ 100각 칸마다 `.` 또는 `c` 문자가 들어옴.✏️ 문제풀이간단한 시뮬레이션 구현 문제입니다.구름 위치(좌표)를 입력받은 뒤, 각 구름마다 실제로 이동시키면서 시간을 계산하는 방법.구름은 동쪽으로만 이동하고 외부 유입없다는 점에서 착안, 구름이 있는 칸은 '0', 그 오른쪽부터 한 칸마다 1, 2, 3, 4... 1씩 늘려가며 초기화하기.아무래도 두 번째 방법이 더 쉽고 간단하기 때문에 두 번째 방법을 사용하면 좋을 것 같습니다.읽은 문자가 `c`이면, 카운팅 변수를 0으로 초기화하고 현재 칸을 0으로 초기화.읽은 문자가 `.`이면, 카운팅 변수 1 증가하고, 현재 칸을 카운팅 변수로 초기화.카운팅 변수는 각 행마다 다시 .. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 2870 - 수학숙제 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악1 ≤ N ≤ 100소문자와 숫자로만 이루어진 문자열 길이 ≤ 100✏️ 문제풀이생각해야 할 반례가 많아서 조금 복잡한 문제입니다.반드시 조건을 먼저 정리하고, 어느정도 손코딩을 마친 뒤에 코딩에 들어가야 햇갈리지 않습니다. 문자열을 처음부터 끝까지 읽다가 숫자를 만난다면,'0'으로 시작하는 숫자인 경우'0'이 아닌 문자 (숫자 또는 소문자)가 나올 때까지 스킵합니다. (단순히 인덱스 변수 증가)이때 세 가지 경우가 발생합니다.다른 숫자를 만난 경우: 아래 '0'으로 시작하는 숫자가 아닌 경우로 이동 후 처리됩니다.소문자를 만난 경우: "00000... " 같은 경우였네요, 토큰을 "0"으로 초기화 해줍니다.문자열 범위를 벗어난 경우 (즉, 문자열 가장 뒤.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 4659 - 비밀번호 발음하기 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개 연속으로 오면 안 된다.각 글자마자 모음인지 자음인지 판단합니다. 모음이면 모음 카운터 변수 증.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 2910 - 빈도 정렬 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악요소 개수: 1 ≤ N ≤ 1,000각 요소의 최댓값(상한): 1 ≤ C ≤ 1,000,000,000✏️ 문제풀이빈도 정렬의 기준은 '많이 등장한 순'으로, 등장횟수가 같다면 '앞서 등장한 순'입니다.즉, 각 숫자와 대응하는 인덱스의 값마다 아래와 같은 정보를 갖고 있어야 합니다.이 숫자가 몇 번 등장했는지이 숫자가 언제 처음 등장했는지로직은 다음과 같습니다.숫자를 입력받습니다. 등장횟수, 첫 등장 인덱스 번호 정보를 함께 저장합니다.처음 등장했다면, 등장횟수는 1 입니다.처음 등장한 숫자가 아니라면, 삽입하지 말고 등장횟수만 1 증가시킵니다.문제에 나온 빈도 정렬의 기준에 따라 정렬합니다.원하는대로 정렬시켜주는 STL 함수는 없기 때문에 따로 정렬 함수객.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 2828 - 사과 담기 게임 ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악입력칸 수 N, 바구니의 크기 M, (1 ≤ M 사과의 개수 J (1 ≤ J ≤ 20)출력: 바구니 이동거리 최솟값✏️ 문제풀이최소로 이동하기 위해서는 최대한 바구니 양끝에서 사과를 받는게 이득이라는 건 쉽게 떠올릴 수 있습니다.만일 반대쪽에서 사과가 떨어진다면, 조금 덜 이동할 수 있을거고,사과가 바구니 안쪽으로 떨어질 가능성도 높아질 테니까요. 로직 자체는 상당히 간단합니다.사과가 떨어지는 위치가 왼쪽 끝에서 가까운지 아니면 오른쪽 끝에서 가까운지 판단합니다.더 가까운 방향으로 이동합니다. 단, 딱 사과가 위치한 지점까지만 움직이면 되겠습니다. 그렇다면, 왼쪽을 `l`이라 하면 오른쪽 끝 `r`을 어떻게 표현할 수 있을까요?바구니 크기 `M == 1`이.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 1992 - 쿼드트리 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악가로/세로 길이를 나타내는 N, 1 ≤ N ≤ 64N개의 문자열, 0과 1로 이뤄져있음.✏️ 문제풀이재귀 가능성 판단하기 전체 흑백영상을 압축하는 과정은 4개의 부분영상 중 하나를 압축하는 과정과 같습니다. 위 그림을 보면 길이만 절반으로 줄어들 뿐이고,범위 내에 있는 데이터가 모두 같다면 그냥 출력하고하나라도 다르다면, 2, 1, 3, 4사분면 순서대로 꼭짓점 위치에서 범위를 절반으로 줄이고 다시 검사하면 됩니다.N은 최대 64, 최대 데이터 수는 $2^{16}$으로 많지 않습니다. 이렇게 전체 문제와 부분 문제가 같다는 점 + 처리할 데이터가 많지 않다는 점을 파악해서 재귀로 풀 수 있어야 합니다. 풀이과정시작점 `(y, x)`에서 가로, 세로로 `l.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 2583 - 영역 구하기 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악의도적으로 좌표 햇갈리게 만든 문제입니다.만일 평소 자신에게 익숙한 좌표계나 문자(N, M, x, y)가 아니라면 주의해서 문제를 읽도록 합시다.세로가 M, 가로가 N (M, N ≤100)K개의 직사각형 좌표 왼쪽 아래 꼭짓점 (x, y), 오른쪽 위 꼭짓점 (x, y)모눈종이의 왼쪽 아래 꼭짓점의 좌표가 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다.이거 때문에 햇갈릴 필요 없습니다.만일 자신에게 편한 좌표계가 왼쪽 위 꼭짓점이 (0, 0), 오른쪽 아래 꼭짓점이 (M, N) 이라면 그냥 원래대로 두고 풀어도 영역의 넓이가 달라지진 않기 때문입니다. 그냥 그림이 거울대칭으로 뒤집혔다고 생각하면 됩니다.✏️ 문제풀이윗 절에서 언급했듯, 햇갈리는 .. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 2468 - 안전 영역 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악N × N 크기의 맵, 2 ≤ N ≤ 100각 칸마다 1 ≤ 높이≤ 100아무 지역도 물에 잠기지 않을 수도 있다.✏️ 문제풀이문제에 나와있지 않은 조건을 당연히 그럴거라 추측하고 풀면 안 된다는걸 연습하기 좋은 문제입니다.물의 높이를 당연히 1부터 시작할거라 생각했다면, 당한겁니다.문제 어디에도 '비가 무조건 내려야 한다'는 말이 없기 때문에, 일단 0부터 시작해야 합니다.물의 높이는 0부터 시작해서 입력받은 N × N 칸의 높이 중 가장 큰 높이까지 (또는 그냥 100까지)를 검사하면 됩니다. 검사는 다음과 같은 과정으로 이뤄집니다.'물에 잠기지 않은 임의의 칸'(즉, `arr[y][x] > 물의 높이`) 부터 시작.현재 물에 잠기지 않았고, 연결돼있.. 공감수 0 댓글수 0 2025. 1. 7.
std::vector<bool>를 PS에서는 어떻게 대해야할까 들어가며...알고리즘 문제를 풀다 보면 `std::vector` 또는 `std::array` 같은 코드를 사용하곤 합니다.우리에게는 `bool [N]`이 너무나도 익숙하고, 위와 같이 작성하더라도 별 문제가 발생하지 않기 때문입니다. 하지만, 실무적이고 객체지향적인 코드 작성과는 조금 멀리 떨어져있는 PS를 하면서도`std::vector`은 사용을 지양하세요~같은 문구를 종종 보곤합니다. 항상 그 이유가 궁금했지만, 그때마다관련 내용 조금 찾아보기어려운 내용에 질겁 → 결론 위주로 탐색'아하 그래서 `std::bitset` 쓰라는 거구나?'막상 `std::bitset` 써보니 불편함다시 `std::vector`로 회귀를 몇 번이고 반복하고 나니 이젠 잘 모르겠더라도 한 번은 정리를 해놔야 속이 시원할 것.. 공감수 1 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 1012 - 유기농 배추 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력:테스트케이스 T (제한 따로 없음)배추밭: 1 ≤ N, M ≤ 50, 가로M, 세로N 순으로 입력됨.배추 개수 1 ≤ K ≤ 250 + 각 배추의 위치 (x좌표, y좌표 순으로 입력됨)위치가 같은 배추는 없습니다.출력: 필요한 최소 지렁이 개수 (Connected component 개수)✏️ 문제풀이서로 연결된 칸들의 집합, 그 집합이 몇 개 있는지를 구하는 connected component 구하기 문제입니다.DFS, BFS 양쪽 모두로 풀 수 있습니다. 배추의 개수 및 위치를 입력받기 때문에배추 하나를 시작점으로 DFS 또는 BFS를 돌려 방문할 수 있는 모든 칸에 방문표시를 합니다. 이게 하나의 집합이 됩니다.배추밭을 더 순회합니다.아직 방문표.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 2178 - 미로탐색 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력:N × M 미로, '붙어서' 들어오는 입력`scanf("%c")` 이용또는 `std::string`으로 한 줄 입력받은 후 `for()`로 처리또는 `std::string`으로 한 줄 입력받은 후 그대로 사용하기2 ≤ N, M ≤ 100출력: (N, M)에 도달하기 까지 밟아야 하는 최소 칸 수시작하는 칸, 도착하는 칸도 밟은 칸 수에 포함됩니다.✏️ 문제풀이최소 칸 수 = 최적해가중치 없음 (모든 칸이 한 칸 이동에 동일하게 한 칸 소요) = BFS 이용방문표시 후 시작점 queue에 `push`4방향 중 갈 수 있는 칸은 queue에 `push`하고 방문표시 합니다.queue가 빌 때까지 반복합니다.4방향 검사하기미로의 경계범위를 넘어서지 않았고.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 4375 - 1 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 각 테스트케이스마다 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) .. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 1629 - 곱셈 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 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`을 이용해서, 나머지가 반복될 때 멈춥.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 3986 - 좋은 단어 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: '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.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 1940 - 주몽 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력재료개수: 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초내에 풀 수 없습니다.(사실 이 문제는 이렇게 풀어도 통과는 됩니다)더 효과적으로 탐색하려면, 투포인터를 사용하면 됩니다.재료 번호를 저장한 배열을 정렬한.. 공감수 0 댓글수 0 2025. 1. 7.
알고리즘 :: 백준 :: 1213 - 팰린드롬 만들기 ❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 알파벳 대문자로만 된 최대 50글자 문자열출력:팰린드롬을 만들 수 있다면, 팰린드롬을 출력하고팰린드롬을 만들 수 없다면, "I'm Sorry Hansoo"를 출력✏️ 문제풀이팰린드롬을 만들기 위해서는 반드시 문자열이 중간지점을 기점으로 대칭이어야 합니다.대칭이 되기 위해서는, 홀수번 등장하는 알파벳이 없거나 1개만 존재해야 합니다.즉, 홀수번 등장하는 문자가 2개 이상이라면, 해당 문자열은 팰린드롬을 만들 수 없습니다. 이런 맥락에서 보면, 팰린드롬은 다음과 같은 형태입니다.2회 이상 등장한 문자들을 각각 등장횟수 절반만큼 먼저 사전순으로 나열합니다.이렇게 나열한 문자열은 접두사(prefix)입니다. 나중에 이걸 뒤집어서 뒤에 붙이면, 모든 등장횟.. 공감수 0 댓글수 0 2025. 1. 7.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.