Archive: 2021
백준 - 수학
백준 - 수학수학 문제 이름 링크 정리여부 비고 1085 직사각형에서 탈출 https://www.acmicpc.net/problem/1085 1644 소수의 연속합 https://www.acmicpc.net/problem/1644 1712 손익분기점 https://www.acmicpc.net/problem/1712 1722 순열의 순서 https://www.acmicpc.net/problem/1722 1978 알파벳 https://www.acmicpc.net/problem/1978 1990 소수인팬린드롬 https://www.acmicpc.net/problem/1990 2292 벌집 https://www.acmicpc.net/problem/2292 2839 설탈배달 https://www.acmicpc.net/problem/2839 2960 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 10819 차이를 최대로 https://www.acmicpc.net/problem/10819 순열, next_permutation 10950 A+B - 3 https://www.acmicpc.net/problem/10950 10952 A+B - 5 https://www.acmicpc.net/problem/10952 11021 A+B - 7 https://www.acmicpc.net/problem/11021 11022 A+B - 8 https://www.acmicpc.net/problem/11022
백준 - 유니온 파인드
백준 유니온 파인드유니온 파인드 문제 이름 틀린 횟수 정리여부 비고 1717 집합의 표현 1976 여행가자 4195 친구 네트워크 10774 저지 10775 공항
백준 - 최소 스패닝 트리
백준 최소 스패닝 트리최소 스패닝 트리 문제 이름 틀린 횟수 정리여부 비고 1196 최소 스패닝 트리 최소 스패닝 트리 기본 유형 9372 상근이의 여행 17472 다리 만들기 2 삼성, 최소 스패닝 트리
백준 - 백트래킹
백준 백트래킹백트래킹 문제 이름 링크 정리여부 비고 1987 병든 나이트 https://www.acmicpc.net/problem/1987 2580 스도쿠 https://www.acmicpc.net/problem/2580 4574 스도미노쿠 https://www.acmicpc.net/problem/4574 6603 로또 https://www.acmicpc.net/problem/6603 9663 N-Queen https://www.acmicpc.net/problem/9663 16987 계란으로 계란치기 https://www.acmicpc.net/problem/16987
백준 - 이분탐색
백준 이분탐색이분 탐색 문제 이름 링크 정리여부 비고 1920 수찾기 https://www.acmicpc.net/problem/1920 1939 중량제한 https://www.acmicpc.net/problem/13397 2110 공유기 설치 https://www.acmicpc.net/problem/2210 2343 기타레슨 https://www.acmicpc.net/problem/2343 O 겁나 많이 틀림 2792 보석상자 https://www.acmicpc.net/problem/2792 O 중요! 다시 풀어보기 2805 나무자르기 https://www.acmicpc.net/problem/2805 2869 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 3020 개똥벌레 https://www.acmicpc.net/problem/3020 10815 숫자카드 https://www.acmicpc.net/problem/10815 10816 숫자카드2 https://www.acmicpc.net/problem/10816 13397 구간 나누기2 https://www.acmicpc.net/problem/13397
백준 - BFS
백준 BFSBFS기본 유형 문제 이름 틀린횟수 정리여부 비고 c++ java python 1260 DFS와 BFS 기초 O 1953 팀 배분 0 O 이분 그래프 2178 미로 탐색 최단 거리 O O O 전체 문제 문제 이름 틀린횟수 정리여부 비고 c++ java python 1012 유기농 배추 2 O 1194 달이 차오른다, 가자 1 O 1260 DFS와 BFS 기초 O O 1600 말이 되고픈 원숭이 5 O 1707 이분 그래프 4 O 1726 로봇 1 O 1939 중량제한 3 O 1953 팀 배분 0 O 이분 그래프 O 1963 소수 경로 0 O 1967 트리의 지름 2 O 2146 다리 만들기 5 O 2178 미로 탐색 최단 거리 O O O 2206 벽 부수고 이동하기 5 2251 물통 0 2234 성곽 0 2468 안전 영역 2 2573 빙산 3 2583 영역 구하기 1 2589 보물섬 0 2606 바이러스 0 2644 촌수 계산 0 2667 단지번호 붙이기 4 2933 미네랄 5 5014 스타트와 링크 1 5213 과외맨 6 5427 불 2 6087 레이저 통신 0 6593 상범 빌딩 1 7576 토마토 1 9019 DSLR 4 9205 맥주 마시면서 걸어가기 3 9372 상근이의 여행 1 12886 돌 그룹 1 15558 점프 게임 11 16236 아기 상어 4 O bfs를 통해 거리구하기 16397 탈출 5 16933 벽 부수고 이동하기3 6 16959 체스판 여행 1 0 17471 게리맨더링 4 O 조합, bfs, 삼성 17836 공주님을 구해라 5 18809 Gaaaaaaaaaarden 0 조합, bfs, 삼성
백준 - 문자열 처리
백준 문자열 처리문자열 처리 문제 이름 정리여부 비고 cpp java python 1032 명령 프롬프트 문자열 속 문자, 문자열 비교 O O O 1152 단어의 개수 문자열 분리, 문자열 토큰화 O O 1157 단어 공부 소문자 -> 대문자 O O 1296 데이트 문자열 정렬 O O O 1316 그룹 단어 체커 문자열 속 문자 찾기 O O O 1475 방 번호 문자열 속 문자 O O 2064 IP 주소 토크나이징 O 2743 단어 길이 재기 문자열 길이 O O O 2857 FBI 문자열 속 단어 찾기 O O O 2902 KMP는 왜 KMP일까? 문자열 토큰화 O O O 2908 상수 문자열 뒤집기 O O 2941 크로아티아 문자 문자열 속 문자 찾기, 문자열 대치 O O O 5586 JOI와 IOI 문자열 분리substr O O O 10808 알파벳 갯수 10809 알파벳 찾기 문자 check하는 방법, dic 사용 방법 O 11654 아스키 코드 아스키 코드 변환 O
백준 - 삼성 기출문제
백준 삼성 기출문제삼성 기출 문제 문제 이름 링크 정리여부 비고 1012 유기농 배추 https://www.acmicpc.net/problem/1012 1600 말이 되고픈 원숭이 https://www.acmicpc.net/problem/1600 1707 이분 그래프 https://www.acmicpc.net/problem/1707 1726 로봇 https://www.acmicpc.net/problem/1726 1939 중량제한 https://www.acmicpc.net/problem/1939 1953 팀 배분 https://www.acmicpc.net/problem/1953 O 이분 그래프 1963 소수 경로 https://www.acmicpc.net/problem/1963 1967 트리의 지름 https://www.acmicpc.net/problem/1967 2146 다리 만들기 https://www.acmicpc.net/problem/2146 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2251 물통 https://www.acmicpc.net/problem/2251 2468 안전 영역 https://www.acmicpc.net/problem/2468 2573 빙산 https://www.acmicpc.net/problem/2573 2583 영역 구하기 https://www.acmicpc.net/problem/2583 2589 보물섬 https://www.acmicpc.net/problem/2589 2606 바이러스 https://www.acmicpc.net/problem/2606 2644 촌수 계산 https://www.acmicpc.net/problem/2644 2667 단지번호 붙이기 https://www.acmicpc.net/problem/2667 2933 미네랄 https://www.acmicpc.net/problem/2933 5014 스타트와 링크 https://www.acmicpc.net/problem/5014 5213 과외맨 https://www.acmicpc.net/problem/5213 5427 불 https://www.acmicpc.net/problem/5427 6087 레이저 통신 https://www.acmicpc.net/problem/6087 6593 상범 빌딩 https://www.acmicpc.net/problem/5427 7576 토마토 https://www.acmicpc.net/problem/7576 9019 DSLR https://www.acmicpc.net/problem/9019 9205 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9372 상근이의 여행 https://www.acmicpc.net/problem/9372 12886 돌 그룹 https://www.acmicpc.net/problem/12886 16236 아기 상어 https://www.acmicpc.net/problem/16236 O bfs를 통해 거리구하기 16397 탈출 https://www.acmicpc.net/problem/16397 17471 게리맨더링 https://www.acmicpc.net/problem/17471 O 조합, bfs 17836 공주님을 구해라 https://www.acmicpc.net/problem/17836 브루트 포스 문제 이름 링크 정리여부 비고 1051 숫자 직사각형 https://www.acmicpc.net/problem/1051 1065 한수 https://www.acmicpc.net/problem/1065 1182 부분수열의 합 https://www.acmicpc.net/problem/1182 1436 영화감독 슘 https://www.acmicpc.net/problem/1436 1748 수 이어쓰기1 https://www.acmicpc.net/problem/1748 2231 분해 합 https://www.acmicpc.net/problem/2231 2309 일곱 난쟁이 https://www.acmicpc.net/problem/2309 2798 블랙잭 https://www.acmicpc.net/problem/2798 3085 사탕 게임 https://www.acmicpc.net/problem/3085 7568 덩치 https://www.acmicpc.net/problem/7568 10448 유레카 이론 https://www.acmicpc.net/problem/10448 12100 2048(Easy) https://www.acmicpc.net/problem/12100 12738 가장 긴 증가하는 부분 수열3 https://www.acmicpc.net/problem/12738 13460 구슬 탈출2 https://www.acmicpc.net/problem/13460 O while문을 이용한 bfs 14502 연구소 https://www.acmicpc.net/problem/14502 14888 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14889 스타크와 링크 https://www.acmicpc.net/problem/14889 15653 구슬 탈출4 https://www.acmicpc.net/problem/15653 O while문을 이용한 bfs 15683 감시 https://www.acmicpc.net/problem/15683 15684 사다리 조작 https://www.acmicpc.net/problem/15684 15686 치킨 배달 https://www.acmicpc.net/problem/14686 16198 에너지 모으기 https://www.acmicpc.net/problem/16198 17127 벚꽃이 정보섬에 피어난 이유 https://www.acmicpc.net/problem/17127 17142 연구소 3 https://www.acmicpc.net/problem/17142 O 조합, 경우의 수 탐색bfs 17779 게리멘더링2 https://www.acmicpc.net/problem/17779 O 영역 나누어 탐색하기
백준 - 자료구조
백준 자료구조vector 문제 이름 틀린 횟수 정리여부 비고 1158 요세푸스 문제 1 스택 문제 이름 링크 정리여부 비고 1406 에디터 https://www.acmicpc.net/problem/1406 1918 후위표기식 https://www.acmicpc.net/problem/1918 3015 오아시스 재결합 https://www.acmicpc.net/problem/3015 O 다시 풀어보기 9012 괄호 https://www.acmicpc.net/problem/9012 10799 쇠막대기 https://www.acmicpc.net/problem/10799 Set 문제 이름 틀린 횟수 정리여부 비고 1181 단어 정렬 1539 이진 검색 트리 2210 숫자판 점프 7785 회사에 있는 사람 map 문제 이름 틀린 횟수 정리여부 비고 1302 1539 9375
1194-달이차오른다_가자
백준 1194 - 달이 차오른다. 가자https://www.acmicpc.net/problem/1194 문제 해설기존 BFS문제를 푸는 형식에 비트마스킹까지 더해진 문제이다. 비트마스킹을 통해 키를 가지고 있는 각각의 상태들을 체크할 수 있다. 키는 총 6개가 주어지기 때문에 50x50x64 = 160,000 의 공간 복잡도를 갖게 돼 메모리 제한에 걸리지 않는다. 소스 코드#include <bits/stdc++.h>using namespace std;int N, M;char Map[55][55];bool check[1 << 6][55][55];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};queue<pair<int, int>> q;int startY, startX;struct point { int y; int x; int key; int count;};int bfs() { queue<point> q; q.push({startY, startX, 0, 0}); check[0][startY][startX] = true; while (!q.empty()) { int cntY = q.front().y; int cntX = q.front().x; int cntKey = q.front().key; int cntCount = q.front().count; q.pop(); if (Map[cntY][cntX] == '1') { return cntCount; } for (int i = 0; i < 4; i++) { int ny = cntY + dy[i]; int nx = cntX + dx[i]; if (0 >= ny || ny > N || 0 >= nx || nx > M) { continue; } if (check[cntKey][ny][nx] == true) { continue; } if (Map[ny][nx] == '.') { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } else { // 열쇠에 마주쳤을 경우 if ('a' <= Map[ny][nx] && Map[ny][nx] <= 'f') { int key = (1 << (Map[ny][nx] - 'a')); check[cntKey | key][ny][nx] = true; q.push({ny, nx, cntKey | key, cntCount + 1}); } // 문을 만났을 경우 if ('A' <= Map[ny][nx] && Map[ny][nx] <= 'F') { int door = (1 << (Map[ny][nx] - 'A')); if (door & cntKey) { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } } // 출구를 만났을 경우 if (Map[ny][nx] == '1') { q.push({ny, nx, cntKey, cntCount + 1}); } } } } return -1;}void init() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { cin >> Map[i][j]; if (Map[i][j] == '0') { startY = i; startX = j; Map[i][j] = '.'; } } }}int main(void) { cin >> N >> M; init(); cout << bfs() << '\n'; return 0;}