Hello Ocean! 🌼

문제 https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 로봇이 4방향 (동서남북)으로 각각 이동할 확률과, 이동 횟수가 주어질 때 로봇이 한 번 방문한 곳을 다시 방문 하지 않을 확률을 구하는 문제이다. 풀이 가능한 모든 이동 경로를 탐색하면서 이전에 방문했던 칸을 다시 방문하지 않은 이동경로의 확률을 구해서 모두 더하면 된다. DFS로 풀었다고 생각했는데, 백트래킹이라고 한다..? 내가 이해하기로는 N번 이동하는 걸 탐색한다고 할 때 매번 ..

문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는..

문제 https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주어진다. 1 x : 알파벳 x를 잊는다. 2 x : 알파벳 x를 기억해 낸다. 처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다. 각 쿼리마다 완전히 알고 있는..

문제 https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 2차원 맵에서, 출발에서 도착점으로 가는데, X로 표시된 필요한 물건들을 모두 챙겨서 나가는 최소 이동거리를 구하는 문제이다. 풀이 그래프상에서 최소 이동 횟수를 구하는 문제이기 때문에 BFS를 이용했다. 그리고, 그래프상에 X가 있는 지점을 모두 방문하는게 조건이기 때문에 X방문체크를 어떻게 할지 고민하다가, X가 최대 5개라고 해서 길이 5짜리 비트마스크를 이용해서 방문체크를 해주..

문제 https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 2^25 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 이상 500만 이하이다. 풀이 숫자를 순서대로 입력받아..

문제 https://www.acmicpc.net/problem/11437 -> LCA 1 https://www.acmicpc.net/problem/11438 -> LCA 2 주어진 두 노드에 대해 LCA(가장 가까운 공통 조상)을 구하면 되는 문제이다. 1번과 2번의 차이는 노드의 최대 갯수 및 시간 제한의 차이이다. LCA2가 훨씬 빡빡하다. 풀이 1. 11437 LCA1번 풀이 연결된 두 노드 a,b가 N-1개의 줄에 걸쳐서 입력되는데, a,b중에 어떤 노드가 부모노드인지는 입력 받을 때에는 알 수가 없다. 그래서 처음에는 연결리스트 형태로 저장했다가, 입력을 다 받은 후에 BFS를 통해 루트인 1부터 타고 들어가서 트리구조를 파악할 수 있도록 했다. (각 노드의 부모와, 깊이 저장) 그리고 LCA를..