알고리즘

문제 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 구현, 시뮬레이션 성별에 따라서 스위치를 바꾸는 방법이 다르다. 남자의 경우 입력되는 숫자의 배수에 해당하는 스위치를 바꾼다. // num의 배수에 해당하는 스위치는 상태를 바꾼다. for (int i = num; i > N; for (int i = 1; i > button[i]; } int K; cin >> K; while (K--) { int gender, num; cin >> gender >> num; if (gender == 1) { //..

문제 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 구현, 시뮬레이션 각 칸을 하나의 구조체로 만들었다. 구조체에는 영양분과 나무를 가지는 vector로 구성된다. 처음에는 sort 작업을 없애기 위해, 우선순위 큐로 만들었지만 오히려 시간초과가 발생하였다. struct space { int nutrient = 5; vector trees; }; 계절 별로 함수로 만들어서 해결한다. 봄, 여름에는 (i, j)위치의 칸의 나무를 오름차순으로 정렬하고, 성장 가능한 나무는 따로 vector에..

문제 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 판의 가장자리 부터 bfs를 실시하여 치즈가 있는 칸을 0으로 설정하여 치즈가 모두 녹을 때까지 진행하면 된다. 칸의 가장자리는 에는 치즈가 놓여있지 않기 때문에, (0, 0)에서 bfs를 시작해도 무방하다. 루프를 돌면서 만나는 치즈를 바로 0으로 만들면 해당 칸이 현재 루프에 영향을 미치므로 다음 루프에서의 판을 나타내는 next_board배열을 만들어서 next_board에 해당 칸을 0으로 설정한다. // 다음 칸이 ..

문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 구현, 시뮬레이션, 백트래킹 입력된 cctv에서 가능한 모든 상태를 백트래킹으로 탐색하여 해결하였다. cctv 데이터를 다음의 구조체로 vector에 넣어주었다. struct cctv { int x; int y; bool dir[4] = { false, }; }; cctv를 회전할 때는 dir배열을 회전한 만큼 이동하여 구현하였다. for (int dir = 0; dir < 4; ++dir) { bool temp_dir[4] = { false..

문제 10810번: 공 넣기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 www.acmicpc.net 풀이 구현, 시뮬레이션 단순한 구현 문제로, 배열의 i부터 j까지 k의 값을 넣는 작업을 M번 반복한다. 특정 구간에 동일한 값을 넣을 때, std::fill 함수를 사용했다. std::fill(시작 주소, 끝 주소, 값); std::fill(v.begin() + i, v.begin() + j, k); vector에서도 사용가능하다. 코드 #include #include using namespace std; int nums[102] = { 0, }; int..

문제 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 풀이 문자열, 트라이 이전 트라이 문제와 달리 접두사를 챙길 필요가 없다. 그러므로 Trie 구조체의 멤버 변수를 map로 두어 특정 string이 어떤 자식 노드를 가리키는지만 저장해 둔다. Trie에 string을 입력할 때는, map에 입력되는 string이 있는지 확인하고 없다면 새로운 Trie를 생성하여 map에 현재 string과 같이 저장한다. 출력 때는, 노드의 깊이도 같이 인자로 넣어주어 "--"가 현재 깊이만큼 출력된 다음..

문제 16934번: 게임 닉네임 첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, www.acmicpc.net 풀이 문자열, 트라이 입력된 문자열의 접두사를 닉네임으로 사용할 수 있다면 해당 접두사를 출력하고, 사용할 수 없다면 이름에 이전에 입력된 이름의 수(1은 제외)를 붙여서 출력한다. 입력된 문자열(name)의 접두사(prefix)를 모두 탐색한다. 가능한 접두사 목록은 다음과 같다. [1, 1], [1, 2], [1, 3], ... , [1, N] 현재 trie에 입력된 문자열들 중에서 prefix를 접두사로 하는 문자열이 없다면 prefix를..

문제 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 풀이 문자열, 트라이 [백준][C++] 5052: 전화번호 목록 문제 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 kantatatam.tistory.com 위의 문제 처럼 트라이를 사용하는 문제다. 특정 ..

문제 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 문자열, 트라이 [Algorithm] 트라이(Trie) 개념과 기본 문제 Practice makes perfect! twpower.github.io 다른 풀이를 보면 여러 방법이 있는 것 같지만, 기본 트라이 문제라고 해서 트라이로 풀었다. 트라이 개념은 위의 링크로... 코드 #include #include #include using namespace std; const int MAX_NUM = 10; struct Trie {..

문제 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 풀이 문자열, 정렬, 해시를 사용한 집합과 맵 입력받은 문자열을 저장하고 정렬하는 방법이 필요한 문제 문자열이 입력된 횟수를 알아야 하므로 map을 사용해야 한다. 입력되는 수가 많지 않기 때문에 unordered_map을 사용한다. 문제에 맞게 정렬이 필요하므로 compare 함수를 생성해야 한다. compare 함수에는 문자열이 입력된 수, 문자열의 길이, 문자열의 사전 순서를 알아야 한..