2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 추천받아서 풀게된 무시무시한 플레 다익스트라 문제 일반 최단경로를 제외했을 때의 '거의 최단경로'를 구하는 문제다 그래서 음 prev를 구해서 체크해준 다음 다익스트라를 다시 돌리면 되지 않을까?생각했는데 접근 방법은 맞았다 위의 그림처럼 다익스트라를 수행하면서 prev를 저장하고(최단경로가 두 개 이상 존재할 수 있기 때문에 배열로 저장) 해당 경로를 삭제 or 접..

https://www.acmicpc.net/problem/22939 22939번: 쿠키크루 밀가루반죽으로 잘 구워진 킴쿠키는 광활하고 평평한 들판 위에 세워진 쿠키나라의 시민이다. 킴쿠키는 케이크나라의 침략으로 어려워진 쿠키나라를 지키기 위해 할 수 있는 일이 없을까 늘 고 www.acmicpc.net 단어가 안 읽혀서 재밌는 문ㄴ제 ㅎㅎ 최단거리하면 자동으로 BFS와 연관짓게 되는데, 그러한 부분을 역으로 주의해야 한다 이 문제에서는 장애물도 없고, 이동하는 데에 아무런 제약이 없기 때문에 거리를 단순히 맨해튼 거리로 구해주면 시간복잡도가 O(1)로 간단하다 따라서 모든 지원분야에 대해, 모든 정점 방문 가능 순서에 대해 전부 구해주면 되기 때문에 브루트 포스 ~~ import sys from iter..

https://www.acmicpc.net/problem/20304 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 익숙한 문제? ㅎㅎ 틀린문제 리스트에 있는게 싫어서 오랜만에 다시 풀어봤다 아주 훌륭한 문제였다 ( = 어렵다는 뜻 ) 안전거리와 안전도가 등장하는데 안전거리를 구하는 것 자체는 XOR 풀이가 직관적으로 떠오를 수 있지만 비밀번호 후보를 찾는 데에 Bitmask + BFS를 바로 떠올리기는 쉽지 않다 항상 특별한 분류의 알고리즘 문제를 풀 때에는 (바로 생각나는 브루트포스 풀이 + 최적화할 수 있는 솔..

https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 세 가지 방식으로 풀이했다 우선 입력받은 두 배열을 모두 정렬하는 것은 똑같고, 이후의 과정을 1️⃣완전탐색 2️⃣이진탐색 3️⃣투포인터 세 가지 방법으로 풀었다. 완전 탐색 풀이 #include #include #include using namespace std; int t, n, m; vector a, b; int main() { scanf(..

https://www.acmicpc.net/problem/17490 17490번: 일감호에 다리 놓기 2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다. www.acmicpc.net 간만에 제대로된(화나는) MST 문제 이렇게 호수 주변의 강의실(노드)들이 있고, 가운데에 와우동?이 있으며 각 강의실을 특정 개수의 돌멩이로 연결할 수 있을 때 K개 이하를 사용해서 모든 강의실이 연결될 수 있는지 묻는 문제 우선 이웃한 강의실 끼리는 공사중인 경로를 제외하고 기본적으로 모두 연결되어 있다 그렇기에 공사중인 경로가 1개 이하이면(0개이면 1~N까지의 강의실이 O 형태로 처음부터 연결되어있음,..

https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 다익스트라 기본 문제 요즘 다익스트라가 어렵게 나오는 것 같아서 다익스트라 심화 문제를 얼른 많이 풀어보고 싶다 어제 카카오 기출 훑어봤을 때에는 트리에서의 다이나믹프로그래밍 문제도 있더라 .... 저번 주에 너무 놀아서 다시 문제 많이많이 풀어야겠다 문제에서 주어진 시야에 보이는 노드들을 disable하고 dijkstra로 탐색하는 과정에서 도착 노드가 아닌 disab..

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 내가 삼성 코테에서 접한 삼성 유형의 정수라고 할 수 있는 문제 시뮬레이션+DFS+중력+배열회전이 전부 합쳐져서 처음 문제를 봤을 때 그냥 웃겼다 요즘 삼성 유형은 주사위 윷놀이같은 끔찍한 문제가 더 안 나오는 걸 보니 이전보다 난이도를 낮추고 구현 능력에 포커스를 맞춘 것 같아 보인다 상어 초등학교는 너무 쉬워서 당황했지만 상어 중학교는 요구사항이 엄청엄청엄청 많기 때문에 잘 정리하고 설계해..

https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 틱택토 보드판의 상태를 입력받아서 종료 조건으로 가능한 경우인지 판단하는 문제 그냥 백트래킹으로 맨 처음에 모든 틱택토 경우의 수(958가지)를 구해서 map에 저장해주고 입력받은 문자열이 map에 있는지로 판단해주었다 문제푸는걸 쉬었다가 시작해서 그런가?? 요즘 문제 처음볼 때 마다 막막하다 ㅠ.ㅜ #include #include #include #define board(i,j) str[(i)..