개인사

[G5] 백준 11578번 팀원 모집 C++ 비트마스킹, 백트래킹

리뷰 https://www.acmicpc.net/problem/11578잘 해놓고 이상한데서 문제를 찾고 있었다. 당분간은 비트마스킹 관련 문제만 풀어야겠다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 문제의 개수를 저장할 변수m : 학생의 수를 저장할 변수tar : 모든 문제를 푼 경우의 상태를 저장할 변수ans : 최소 학생을 저장할 변수lst : 각 학생이 풀 수 있는 문제 번호를 저장할 벡터 배열 함수1. btvoid bt(int cur, int sum, int cnt) { if (cnt > ans) return; if (sum == tar) { ans = min(ans, cnt); return; } if (cur >= m) return; int next = cur + 1; ..

[G4] 백준 13701번 중복 제거 C++ 비트마스킹, 비트 집합

리뷰 https://www.acmicpc.net/problem/13701메모리 효율을 극한까지 활용하여 주어지는 숫자들의 중복 제거를 하는 문제 전역 변수bucket : 주어지는 정수의 중복 체크를 하기 위한 배열, char을 사용해 각 요소를 1바이트로 만들어 준다. 함수없음 문제풀이변수 n에 입력이 끝날때 까지 배열의 요소를 입력 받아 준다.변수 idx를 n을 8로 나눈 몫으로, bits를 1을 n을 8로 나눈 나머지 만큼 왼쪽으로 쉬프트한 값을 저장한다.bucket[idx]와 bits의 비트 and연산이 true일 경우 이미 나왔던 수 이므로 continue처리해 준다.위 조건에 걸리지 않는다면 bucket[idx]에 bits를 더해 방문체크 후 n을 출력 후 공백으로 구분한다. 트러블 슈팅없음..

[네트워크] 캐스팅 방식

개요네트워크 통신 중 패킷 전송 방식에는 여러 캐스트 방식이 존재한다.상세하게는 유니캐스트, 멀티캐스트, 브로드캐스트, 애니캐스트가 있으며, 각 캐스트 방식은 특정 상황과 요구사항에 따라 선택되며, 보통 수신자의 수에 따른 방식으로 나누어 진다. 캐스트라는 용어는 던지다, 보내다라는 의미에서 유래되었으며, 네트워크에서 데이터를 어떤 방식으로 "던져서" 전달할지를 나타내는 개념이다.각각의 접두사를 살펴보면 의미가 모두 존재한다.Uni-: 하나의 (one)Multi-: 여러 개의 (many)Broad-: 넓은, 전체의 (wide, all)Any-: 아무거나 중 하나 (any one) 유니캐스트(Unicast)하나의 송신자가 하나의 특정 수신자에게만 데이터를 전송하는 방식이다.가장 기본적이고 일반적인 통신 방..

[G2] 백준 2481번 해밍 경로 C++ 너비 우선 탐색, 비트마스킹, 해시맵, 역추적

리뷰 https://www.acmicpc.net/problem/2481비트 연산만 신경쓰고 최적화 생각을 미처 못해서 시간 초과를 줄줄이 받은 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수k : 비트의 개수를 저장할 변수m : 쿼리의 개수를 저장할 변수dic : key로 이진 코드의 값을 십진수로 변형한 값을, value로 노드의 번호를 저장할 해시맵lst : 각 노드 번호의 이진 코드의 값을 십진수로 변형한 값을 저장할 배열edges : 간선 정보를 인접 리스트로 저장하기 위한 벡터 배열 함수1. bfsvector bfs(int dn) { queue q; q.push(1); vector v(n + 1, false); vector pat..

[네트워크] 시리얼 통신, RS-232, RS-485

개요시리얼 통신은 데이터를 한 번에 한 비트씩 순차적으로 전송하는 통신 방식을 의미한다.데이터를 직렬로, 즉 하나의 선로를 통해 비트 단위로 순서대로 전송한다. 이는 여러 비트를 동시에 전송하는 병렬(패러럴) 통신과 대비되는 개념이다. 8비트 데이터 'A'(01000001)를 전송할 때 0→1→0→0→0→0→0→1 순서로 한 비트씩 순차적으로 선 하나로 시간차를 두고 전송한다. 보통 2~4개의 적은 수의 전선이 필요하며, 장거리 통신에 적합하다. 전자기 가섭에 상대적으로 강하며 구현이 간단하고 비용이 저렴하다는 장점이 있다.반면 병렬 통신보다 속도가 느리며, 데이터 동기화가 필요하다는 단점이 있다. 시리얼 통신은 임베디드 시스템, 산업 자동화, 센서 네트워크, 디버깅 및 로깅, GPS 수신기, 모뎀 통신..

[G2] 백준 17244번 아맞다우산 C++ 너비 우선 탐색, 비트마스킹

리뷰 https://www.acmicpc.net/problem/17244BFS + 비트마스킹을 통해 물건 챙긴 상태를 분기처리하여 탐색하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n, m : 맵의 세로/가로 길이를 저장할 변수idx : 물건의 번호를 식별하고, 개수를 저장할 변수sx, sy : 시작 위치의 x, y좌표를 저장하기 위한 변수ex, ey : 도착 위치의 x, y좌표를 저장하기 위한 변수lst : 맵 정보를 저장하기 위한 2차원 배열v : 맵 정보, 물건을 찾은 상태를 방문 체크하기 위한 3차원 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 현재 위치와 누적 소요 시간, 찾은 물건 정보를 정의할 구조체 함수1. bfsint bfs() { queue q; q.pu..

리뷰 https://www.acmicpc.net/problem/19538문제를 이해하는데 시간이 좀 많이 소요된 듯 하다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 시작 노드의 개수를 저장할 변수lst : 루머를 믿는 최초 시간을 저장할 배열cnt : 루머가 도달한 개수를 저장할 배열conn : 인접 리스트의 크기를 저장할 배열v : 방문 여부를 저장할 배열edges : 인접 리스트를 저장할 벡터 배열q : 탐색할 요소를 저장할 큐 함수1. bfsvoid bfs() { int ct = 0; while (!q.empty() && ++ct) { queue q2; swap(q, q2); unordered_set visit; while (!q2.empt..

리뷰 https://www.acmicpc.net/problem/3988쉬울줄 알았는데 생각보다 어려웠다... 슬라이딩 윈도우의 인덱스 처리, 삽입 시점 등 생각해야 할 것이 너무 많았다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 수열의 길이를 저장할 변수k : 제거할 수 있는 정수의 개수를 저장할 변수lst : 수열 정보를 저장할 배열dic : 현재 윈도우의 두 원소 차이 집합을 저장할 멀티셋 함수없음 문제풀이n, k값을 입력 받고, n개의 수열의 요소를 lst에 입력 받아준다.sort함수를 통해 lst배열을 오름차순으로 정렬해 준다.변수 w에 윈도우 크기인 n-k값을 저장해 준다.0~w-2을 순회하며 lst[i+1] - lst[i]를 dic에 insert처리해 주어 m값을 dic에..

리뷰 https://www.acmicpc.net/problem/1185MST 기반 문제인 것을 보고 노드 가중치, 트리 형태를 생각해 뇌피셜로 문제 접근을 했는데 한번에 AC를 받았다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수p : 간선의 개수를 저장할 변수cost : 노드의 가중치를 저장할 변수nodes : 노드가 속한 루트 노드 번호를 저장할 변수Edge : 간선 정보를 저장할 변수, 가중치를 기준으로 오름차순 정렬한다.edges : 간선 정보를 저장하기 위한 Edge타입 벡터 함수1. Findint Find(int a) { if (nodes[a] == a) return a; return nodes[a] = Find(nodes[a]);} 현재 노드가 속한..

리뷰 https://www.acmicpc.net/problem/1422백준 16496번 큰 수 만들기 파이썬 백준 16496번 큰 수 만들기 파이썬리뷰나의 첫번째 플래티넘 문제 도전기였다.자료구조, 그리디 알고리즘, 정렬에는 자신이 있었기에 문제를 읽었을 때 플래티넘 문제가 이렇게 쉽다고? 라는 생각이 들었다.문제풀이처음 생각했zzzz955.tistory.com 위 문제의 응용 버전인 문제, 유사 문제를 접근한 적이 있어 쉽게 풀 수 있었다 전역 변수k : 자연수의 개수를 저장할 변수n : 뽑아낼 수의 개수를 저장할 변수S : 뽑아낼 수의 우선 순위를 정의하기 위한 구조체, 정렬용 문자열을 기준으로 내림차순 정렬한다.s1 : 각 수를 저장하고 정렬하기 위한 S타입 벡터 함수없음 문제풀이k, n값을 입..