개인사

[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값을 입..

리뷰 https://www.acmicpc.net/problem/22870뭐가 문제일까 싶을때 간선 정렬을 가중치 우선이 아닌 노드 번호 우선을 해주니 AC를 받았다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수v : 노드 방문 여부를 저장할 배열Edge : 간선 정보를 정의할 구조체, 노드 번호가 같다면 가중치, 아니라면 노드 번호순으로 오름차순 정렬한다.edges : 간선 정보를 인접 리스트로 저장하기 위한 Edge타입 벡터 배열Pos : 현재 노드와 누적 가중치 정보를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstravector dijkstra(int sn) { priority_queue pq..

리뷰 https://www.acmicpc.net/problem/13306오프라인쿼리를 통해 쿼리를 모두 받은 후 유니온 파인드를 통해 처리해 주는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수q : 쿼리의 개수를 저장할 변수par : 부모 노드의 번호를 저장할 배열nodes : 자신이 속한 그룹의 루트 노드 번호를 저장할 배열Query : 쿼리 정보를 정의할 구조체 함수1. Findint Find(int a) { if (nodes[a] == a) return a; return nodes[a] = Find(nodes[a]);} 자신이 속한 루트 노드의 번호를 찾기 위한 함수, 경로 압축까지 진행해 준다. 2. Unionvoid Union(int a, int b..

개요앞서 프로젝트를 진행하면서 항상 문제가 되었던건 회원 인증에 대한 내용이었다.어차피 SSAFY라는 교육기관 내에서 프로젝트를 진행하기에 배포 시 사람들의 참여를 유발하기 위해선 가장 간단한 인증 절차가 유리했다.따라서 OAuth기반의 Google, SSAFY로그인을 사용하거나 그냥 이메일 형식의 정규식을 검증을 거친 후 가입을 성사시켰다. 하지만 이런 방식의 문제점은 비밀번호를 까먹었을때 찾아줄 수가 없다!비대칭 형식의 암호 알고리즘을 사용했더니 이메일을 통해 사용자를 식별해 줄 수가 없었다. 따라서 이번 프로젝트는 살짝 고민이 되는 부분이 있다. 실시간 랭킹 시스템을 도입하곤 싶은데 그럼 실제 사람을 제대로 식별해 주어야 할 것 같기 때문! 그래서 인증 절차는 아직 고민이 되는 부분에 있다. 하기엔..

개요어느새 SSAFY도 끝이 났다. 덕분에 세 번의 팀 프로젝트를 진행하며 경험을 쌓았지만 앞으로 더 발전 하기 위해서 사이드 프로젝트는 꾸준히 진행해야겠다는 생각이 들었다.이전의 프로젝트들을 진행하면서 백엔드 개발 역량을 많이 쌓았다. Spring Boot와 같은 웹 프레임워크를 통해 MSA 구조를 설계하고 마이크로서비스를 구현, 인증, 로깅과 같은 시스템도 많이 경험해 보았다.또한 게임 프로젝트를 진행하며 소켓 서버를 통해 stateful 서버도 개발을 해 보았다. 이러한 경험을 쌓을 수 있었던 이유는 6명의 팀원과 함께하며 SSAFY 측에서 제공해 주는 서버를 사용하면서 부터였다. 하지만 이제 내겐 팀원도 지원 받을 수 있는 교보재도 존재하지 않는다. 따라서 이번 사이드프로젝트는 SSAFY 입과 전..

리뷰 https://www.acmicpc.net/problem/1854다익스트라 + 우선순위 큐를 활용해 각 노드별 k번째 최단 경로를 관리하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수k : 구하고자 하는 최단 경로의 수를 정의할 변수Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열Pos : 현재 정보를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstravoid dijkstra() { priority_queue pq; pq.push({ 1, 0 }); vector> dist(n + 1); while (!pq.e..

리뷰 https://www.acmicpc.net/problem/10217문제의 정답 비율이 굉장히 낮았다. 첫번째는 실수, 두번째는 dp의 공간 복잡도로인한 제어 불가로 틀렸지만 pq에 push하는 경우의 수를 줄여주니 AC를 받았다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : 노드의 개수를 저장할 변수m : 사용 가능한 최대 비용을 저장할 변수k : 간선의 개수를 저장할 변수Edge : 이동할 노드, 간선의 비용과 가중치를 정의할 구조체, 가중치를 기준으로 오름차순 정렬한다.Pos : 현재 노드, 누적 비용과 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra(const vector..

리뷰 https://www.acmicpc.net/problem/13907슬슬 고난도 다익스트라 + DP문제도 어떻게 접근해야할지 최적해가 보이기 시작했다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수k : 쿼리의 개수를 저장할 변수s, d : 시작 지점과 도착 지점의 노드 번호를 저장할 변수Edge : 이동할 노드 번호와 간선의 가중치를 정의할 구조체, 간선의 가중치를 기준으로 오름차순 정렬한다.edges : 인접 리스트를 저장하기 위한 Edge타입 벡터 배열Pos : 현재 위치와 사용한 간선의 개수, 누적 가중치를 정의할 구조체, 누적 가중치 기준으로 오름차순 정렬한다. 함수1. dijkstravector dijkstra() {..

리뷰 https://www.acmicpc.net/problem/1162다익스트라 + DP의 또다른 유형의 문제, 풀면 풀수록 이 유형이 재밌다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수k : 최대로 포장할 수 있는 도로의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체, 간선의 가중치를 기준으로 오름차순 정렬한다.edges : 간선 정보를 인접 리스트로 저장하기 위한 Edge타입 벡터 배열Pos : 현재 노드와 포장 횟수, 누적 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstrall dijkstra() { priority_queue pq; pq.push({ 1, 0, 0 });..

리뷰 https://www.acmicpc.net/problem/13308다익스트라 + DP문제에 대해 어느정도 이해가 가기 시작했다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수p : 각 노드의 가중치들을 저장할 배열Edge : 이동할 노드와 가중치 등 간선 정보를 정의할 구조체, 간선 가중치를 기준으로 오름차순 정렬한다.edges : 간선 정보를 저장할 Edge타입 벡터 배열Pos : 현재 노드와 누적 연료 최소값, 누적 비용을 정의할 구조체, 누적 비용을 기준으로 오름차순 정렬한다. 함수1. dijkstrall dijkstra() { priority_queue pq; pq.push({ 1, p[1], 0 }); vector> ..

리뷰 https://www.acmicpc.net/problem/12930간선이 두개인 그래프에서 최단 경로를 찾는 DP + 다익스트라를 활용한 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수Edge : 간선의 두 가중치를 정의할 구조체Pos : 현재 노드 번호와 누적 가중치를 정의할 구조체, 두 가중치의 곱을 기준으로 오름차순 정렬한다.edges : 간선 정보를 인접 행렬로 저장하기 위한 Edge타입 2차원 배열 함수1. get_edgesvoid get_edges(int index) { for (int i = 0; i > ch; if (ch == '.') continue; int w = ch - '0'; if (index == 1) edges[i][..