본문 바로가기

분류 전체보기

 (328)
[백준] 1967번 : 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 해당 문제는 깊이 우선탐색으로 문제를 해결 하였습니다. 1. 아무노드로 부터 시작하여 깊이우선탐색을 하여 가장 긴 노드를 찾습니다. 2. 가장 긴 노드로부터 다시 깊이우선탐색을하여 다른 노드까지의 긴 길이를 찾습니다. 가장 긴 길이가 트리 의 지름입니다. 이유 : 트리는 사이클이 없어서, 한 노드로부터 다른 한노드까지의 경로는 단 하나 존재합니다. 따라서 아무 노드로부터 시작하..
[백준] 1043번 : 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 해당 문제는 파티리스트들을 2번 스캔 해야합니다. 진실을 알고 있는 사람과 같은 파티에 참석할 경우 해당하는 파티원들은 모두 진실만 들을 수 있습니다. 따라서 파티 리스트들을 한번 스캔하는데 진실을 알고있는 사람들의 그룹을 만듭니다. ( 파이썬 set 자료구조 사용 ) 두번째 스캔에는 파티원들 모두 진실을 알고 있는 그룹에 속하지 않아야 지민이는 거짓말을 할 수 있습니다. N, M = map(int, inp..
[백준] 1976번 : 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 해당 문제는 아래의 문제와 동일한 문제로 볼 수 있습니다. https://bigkwangs.tistory.com/80 [백준] 1717번 : 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되..
[백준] 1717번 : 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 해당 문제는 유니온 파인드 문제로 해결 할 수 있습니다. 집합 a, b 가 주어졌을때 a,b를 합칩니다. 합치는 방법은 유니온 방법으로 합치는데 두개의 집합중 작은 부모노드를 자기자신의 부모노드로 만들면 됩니다. 즉, 부모노드를 동일하게 가져가면 합쳐집니다. 해당집합이 서로 속해있지 않는것을 알기위해서는 파인드를 사용합니다. 집합 a, b의 부모노드를 구해보아..
[백준] 9466번 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 순열 사이클 문제로 접근하여 문제를 해결하였습니다. 깊이우선 탐색으로 한 학생으로부터 선택한 팀원을 깊이우선 깊이 우선 탐색하면서 마지막 학생이 시작한 한 학생을 가르킨다면 사이클이 생기고 이 사이클이 생긴 리스트들을 결과 값에 저장합니다. 또한 자기자신이 자기자신을 뽑은경우는 자기혼자 팀원이 될 수 있습니다. cycle[cycle.index(newstudent) 자기자신의 Index로 부터 개수를 새..
CacheManager NestJS 사용 예제 ( 채팅정보 캐싱 ) 오늘의 주제는 채팅방에 있는 채팅내용을 DB조회가 Redis에 캐싱을 하여 조회하는 방법에 대해서 이야기 해보고자 합니다. NestJS에서 Custom Interceptor를 활용하여 채팅 추가/조회 하는 부분에 Interceptor를 적용하였습니다. Redis를 사용하기위하여 docker파일을 작성하였습니다. ( Mac M1 기준) version: '3' services: local-redis: image: redis:latest container_name: local-redis restart: always ports: - "6379:6379" volumes: - ./db/redis/data:/data platform: linux/x86_64 CacheManager를 사용하기위한 모듈을 추가해줍니다. ..
[백준] 9019번 : DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 해당 문제는 너비 우선 탐색으로 문제를 해결한다. 첫 숫자를 큐에 넣고 pop하여 4가지의 연산을 한뒤에 다시 큐에 넣는다. 큐와 팝을 반복을 하면서 B의 숫자가 만들어질때까지 결과값을 구한다. visited처리는 연산한 값으로 visited처리를 하였습니다. 해당 visited값 안에는 연산의 누적 합니다. from collections import deque T = int(inpu..
[백준] 15683번 : 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 해당 문제는 완전탐색 + 깊이우선탐색 + 조합 문제로 해결 하였습니다. 1. CCTV를 하나씩 모두 다 돌려보며 사각지대의 최소값을 구합니다. 2. 해당 CCTV로부터 감시영역은 깊이우선탐색으로 탐색합니다.( 방향성이 있기 때문 ) 3. 재귀 함수를 통하여 CCTV를 하나씩 돌려보며 모든 조합을 호출 합니다. import copy cctv = ['1','2','3','4','5'] N,..

티스토리툴바