분류 전체보기
-
강한 연결 요소, Strongly Connected Component알고리즘/백준 2024. 7. 7. 14:25
SCC, 강한 연결 요소(Strongly Connected Componet)방향이 존재하는 유향 그래프에서 서로 강하게 연결된 부분 집합을 의미, 강하게 연결되있다 -> 사이클이 형성된다.설명보다 아래 그림을 보면 쉽게 이해된다. 각각의 영역이 SSC를 이룬다. 코사라주 알고리즘(Kosaraju's Algorithm)1. 입력된 그래프에 대해 역방향 그래프를 만듬2. 그래프에 대해서 DFS를 수행하고, 끝나는 순서대로 스택에 push3. 스택을 하나씩 pop하면서 역방향 그래프에서 DFS를 수행- 이미 방문한 정점의 경우 pop만 수행- 방문하지 않은 정점에 대해 DFS를 수행하고, 이 때 탐색되는 정점들이 하나의 SCC 동작 방식0. Input, 그래프와 역방향 그래프를 생성해준다.# Input7 9..
-
[백준] 1738번 - 골목길알고리즘/백준 2024. 7. 6. 23:29
문제1738번 골목길: https://www.acmicpc.net/problem/1738 오랫만에 고통 좀 받은 문제, 얼른 풀고 SCC공부하려 했는데 시간 다 뺏김 ㅜㅜ 양 또는 음의 가중치를 가지는 그래프에서 사이클을 판별하고 경로 추적을 하는 문제 (그래프, 벨만-포드)벨만 포드는 몰라서, SPFA로 품 풀이1. 역방향 그래프를 생성해서 BFS를 돌려 해당 정점에서 N정점에 도달 가능한지 여부를 판단만약 해당 정점이 N정점에 도달하지 않는 정점이라면 1에서 N정점간의 비용을 구할 때 고려하지 않아도 된다. (사이클이 존재하지만 정답을 출력하는 경우!)2. SPFA 돌리기, SPFA 경로추적은 몰라서 그냥 다익스트라처럼 비슷하게 추적함if(check[nxt.n] == 0) continue; 와 같..
-
-
리눅스마스터 2급 합격 후기일상/회고 또는 후기 2024. 7. 1. 07:31
리눅스 마스터 2급 합격 방학인데 딱히 할 것도 없고, 뭐 따두면 나쁜건 없겠지... 하는 마음으로 일단 신청했던 시험후 다른 공부와 프로젝트에 밀려살다보니 미루고 미뤘다.평소에 리눅스라고는 cd / chmod / mkdir / grep ... 시험 3일 전 쯤 책이랑 cbt 돌리면서 벼락치기 했다. 사용한 책https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=334101201&start=pgooglemc 2024 이기적 리눅스마스터 2급 기본서리눅스마스터 2급을 취득하기 위해 필요한 최대한의 것을 전부 제공해준다. 시행처에서 발표한 출제기준에 완벽하게 맞는 핵심이론 내용과 이론을 공부한 뒤 바로 문제를 풀어볼 수 있는 구성www.aladin.co.kr 책 살 생..
-
스네이크 게임, Win32일상/ssafy 2024. 6. 28. 01:45
내용기본적인 스네이크 게임 기능게임시간에 비례해서 난이도 올라감 조작키S: StartP: Pause방향키: 조작 실행결과 코드#include #include #include #include #include #include "resource.h"// 공간 가로 세로#define WIDTH 20#define HEIGHT 20// 블록 크기 픽셀 크기#define TILESIZE 24#define RESOURCESIZE 4#define LINF 999999999999999999// debug flagint DEBUGFLAG = 0;// Window는 한번의 실행으로 끝나는 것이 아니라 윈도우가 종료될 때까지의 무한 루프의 메시지가 필요하기 때문에 callback 함수를 사용한다. 메시지 처리 함수. ..
-
-
-
[백준] 11406 - 책 구매하기 2알고리즘/백준 2024. 6. 27. 07:56
문제https://www.acmicpc.net/problem/11406 풀이Network flow 문제, Network flow는 각 제한들을 어떻게 capacity로 줄 것인지 생각하면서 풀어야 하는듯그냥 많이 풀어보면서 다양한 유형을 접해봐야할듯...그래도 이 문제는 금방 풀었다. 각각의 입력(사려하고 하는 책의 개수, 사람이 서점에서 구매할 수 있는 책의 개수, 서점이 가진 책의 개수)을 다음과 같이 간선에 매핑하고, capacity를 준 뒤 풀면 된다. 코드#include #include #include #include #include #include #include #include using namespace std;int N, M;int capacity[401][401];int flow[40..