2JINISHAPPY 2JINISHAPPY

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/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net merge sort스러운 투포인터 문제 n,m=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) ans=[] a=0 b=0 while a!=len(A) or b!=len(B): if a==len(A): ans.append(B[b]) b+=1 elif ..

https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 조금 어려웠던 벨만포드 문제 ~~~~ 아주 전형적인 벨만포드 문제라면 음수 사이클의 존재 여부만 체크할텐데 이 문제에서는 음수 사이클이 존재하는지 & 해당 사이클에서 목적 노드로의 path가 있는지 또한 검사해야 했다 그래서 3번이 처음에는 음수 사이클이 존재한다면 Gee를 출력하는 줄 알았지만 ~~ 여러개의 음수 사이클이 존재하더라도, 하나의 음수 사이클에서라도 도착지로 가는 path가 있을 ..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 응용 BFS문제인 공주님을 구해라 ~!~! 공주에게 도달할 수 있는 최단거리 상태가 검을 얻었을 때/검을 얻지 못했을 때로 나뉘기 때문에 visit 배열을 3차원으로 만들어주어야 한당 이렇게 3차원 visit 배열을 요구하는 BFS문제는 까다로울 수 있기 때문에 주 의 하 자 #include #include using namespace std; typedef struct { int..

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 기본 MST 문제~!~!~!~!~! #include #include #include #define pii pair #define INF 987654321 using namespace std; vector g; int n, m; long long sum; long long pr..

https://programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 레벨 4라서 두려움에 떨었던 문제 백준식 풀이법(안풀리면 컨닝)으로 disjoint set이라는 건 알았지만 어떻게 풀지 고민했다 그래서 처음에는 0이라는 더미 노드를 만들어서 방이 나올 때 마다 union하고, find해서 parent가 0과 다를 때 새로운 node를 더해주는 식으로 구현했다 하지만 그렇게 구현하니까 브루트포스와 다를게 없었다 ... 그래서 효율성에서 광탈하고 카카오 테크 블로그 풀이를 슬쩍했다 이것이 핵심 로직인데 union-find 자료구조의 find 부분을 응용한 부분이 핵심인 것 같당 이렇게 빈 방이 있을 경우에..

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)..