2JINISHAPPY 2JINISHAPPY

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

DAG는 Topological Sort, Strongly Connected Component 등을 정의할 때 자주 사용되는 자료구조로 사이클이 존재하지 않는 방향 그래프 를 의미한다 DAG를 이해하기 위해 Directed graph G가 cycle이 있다 ↔ G의 DFS Tree가 back edge를 가지고 있다 이러한 성질들은 서로 필요충분조건을 만족한다는 사실을 알 필요가 있다 1️⃣ ⬅ (G의 DFS Tree가 back edge를 가지고 있다면 G에는 cycle이 존재한다) : 그래프 G에서 임의의 정점 u와 v에 대해 back edge(v,u)가 존재한다고 가정한다(위의 그림). 그러면 u ➡ ... ➡ v ➡ u로의 cycle이 존재한다 2️⃣ ➡ (Directed Graph G가 cycle이 ..

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

모든 프로세스는 부모-자식 관계를 지닌다. 프로세스의 생성에는 처음부터 새로 생성하는 방식과, 부모 프로세스를 복제해서 생성하는 방식이 있다. 프로세스를 처음 생성할 때 에는 프로그램 코드와 데이터를 메모리에 적재하고, 새로운 PCB를 생성하여 초기화하고, 프로세스를 Ready Queue에 enqueue한다. 프로세스를 복제할 때 에는 기존 프로세스를 부모(Parent) 프로세스, 새로운 프로세스를 자식(Child) 프로세스의 관계를 가진다. 복제와 동시에 현재 실행중이던 프로세스를 중단하고 상태를 저장 부모 프로세스의 PCB를 복사해서 새로운 PCB를 생성한 뒤 Ready Queue에 추가 Linux) fork() 함수 사용 부모 프로세스는 여러 자식 프로세스를 가질 수 있기 때문에 그림과 같은 트리 ..

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

https://www.acmicpc.net/problem/21776 21776번: 가희와 읽기 쓰기 놀이 1번째 줄에 N, C가 공백으로 구분되어 주어집니다. 2번째 줄 부터 N+1번째 줄까지 1번 사람부터 N번 사람까지 낸 카드의 갯수와 카드를 낸 순서가 주어집니다. 예를 들어 3번째 줄에 3 2 4 5 가 있다면 www.acmicpc.net 요즘은 순열 어렵게 구하기가 유행인가.....??^^ 이 문제 또한 순열을 이용한 문자열 문제이다 요즘은 시뮬레이션 없는 순열은 파이썬으로 하는게 편해서 ... 이 문제 또한 파이썬 각각의 사람마다 수행할 카드들의 순서가 정해져 있고, 해당 카드에는 여러 연산이 쓰여있을 수 있다 또한 본인의 카드 순서가 섞이지 않는 선에서 다른 사람과 교차 시행이 가능하다 A가 ..

https://programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 진짜 ... 지금까지 푼 BFS중에 제일 까다롭고 빡치고 어려웠다 ^-^.............. 정답률 0.95의 위엄인가 ........ 어떤 카드를 먼저 뒤집을지 (라이언-어피치-프로도) or (어피치-프로도-라이언) 등 을 먼저 구해주어야 하기 때문에 카드 종류에 맞춰 순열을 구해주고 해당 카드의 짝(라이언A, 라이언B)들 중 어느 카드를 먼저 뒤집을 지도 ..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 오랜만에 disjoint set 문제 파티에 참석한 인원들을 전부 union해준 뒤 진실을 알고 있는 사람과 같은 parent를 가진 팀으로만 이루어져 있는지 체크해주었다 #include #include using namespace std; typedef struct disjointSet { vector parent, rank; disjointSet(int n) { rank = vector(n + 1); f..