새로운 것을 배우는게 즐거운 개발자입니다.
알고리즘/백준
https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 백준 온라인저지 1311번 문제 할 일 정하기1번 문제입니다. 아이디어 N번의 사람이 N번의 일을 할때 최소값을 구해야 하는 문제인데, N은 20이하이기 때문에 depth가 20인 dfs 완전탐색을 이용하여 풀이했습니다. #include #define MAX 21 #define INF 987654321 using namespace std; int n; int task[MAX][MAX..
2022. 5. 23.
https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 백준 온라인저지 17244번 아맞다우산 문제입니다. 아이디어 물건을 모두 찾아서 들어오는 문에서 나가는 문으로 나가야 하기때문에 물건을 숫자로 파싱하여 비트마스킹을 사용할 수 있게 했고, 최단 거리를 구하는 문제이기에 bfs를 이용하여 완전탐색으로 풀이 했습니다. 바로 전날 동일 유형문제를 풀어서 원트에 통과받았네요. :) #include #include #include #define MA..
https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 백준 온라인저지 4991번 로봇 청소기문제입니다. 아이디어 더러운 칸이 최대 10개이기 때문에 더러운칸을 비트마스킹을 사용할 수 있게 숫자로 저장하고, 모든 더러운칸을 방문했을때 최소거리를 구하기 위해 bfs를 이용하여 완전탐색 하였습니다. 풀이 도중 더러운칸을 비트로 나타낸 state가 변경되었을때 newState를 사용하지 않아 고생을 좀 했네요 #include #include #include #def..
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 백준온라인저지 2146번 다리만들기 문제입니다. 아이디어 bitset을 이용해서 각 comand에 대해 수행하도록 작성했습니다. #include #include #include using namespace std; bitset bit; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; string s; int n; while(t--) { cin >..
2022. 5. 22.
https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai n) { if (bit[n]) continue; bit[n] = 1; cout
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 백준 온라인 저지 1194번 달이 차오른다, 가자. 문제입니다. 풀이과정 비트마스킹과 BFS를 이용하여 풀이하였는데, 사실 노드의 상태를 비트로 표현하여 탐색하는 문제는 이제 어느정도 익숙해서 풀만해서 풀이자체는 어렵지 않았습니다. 그런데 상태 관리하는 부분과 메모리를 신경쓰지 못해서 고생을 많이 했네요. 상태관리하는 부분은 for문이 돌면서 열쇠가 없이 방문해야하는..
2022. 4. 21.
2022. 3. 13.
