본문 바로가기

알고리즘/백준

 (263)
[백준] 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로 부터 개수를 새..
[백준] 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,..
[백준] 1038번 : 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 해당 문제는 다이나믹 프로그래밍으로 문제를 해결 하였습니다. N 자리수의 값을 구할때 N-1 자리수에서 가져와 이어 붙힙니다. 예를들어서30,31,32 을 (두번째자리) 구한다고하면 3보다 작은 N-1 자리수에 3을 이어붙힌 값인 310, 320, 321 입니다. [10]은 1로 시작하는 2번째 자리수, [20,21] 2로 시작하는 2번째 자리수 입니다. dp[3] = prev_dp..
[백준] 17142번 : 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 해당 문제는 완전탐색 + 너비우선탐색 + 조합 문제로 해결하였습니다. 1. 완전탐색 : 가능한 모든 경우의 수를 다 탐색해본다 ( M개의 활성바이러스를 가질 수 있는 경우의 수를 모두 탐색해본다.) 2. 너비우선탐색 : 해당 바이러스에서 빈방으로 바이러스를 퍼트린다. (최소 거리 탐색이기때문에 너비우선탐색 선정) 3. 조합 : M개의 활성화 바이러스를 가질 수 있는 경우의 수를 모두 구한다. 생각해야할 ..

티스토리툴바