algorithm/문제
-
[Python] 백준 1717번/집합의 표현/유니온파인드 Union Findalgorithm/문제 2023. 6. 16. 17:55
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net ⚡️ 문제 설명 전형적인 Union Find 문제! union find 개념을 안다면 바로 풀 수 있는 문제다. 2023.06.16 - [algorithm/개념] - [Python] Union - Find 유니온 파인드/서로소 집합 [Python] Union - Find 유니온 파인드/서로소 집합 🔎 Union Find (서로소 집합) 란? 서로소 부분 집합들..
-
[Python]프로그래머스/베스트앨범/해시algorithm/문제 2023. 5. 26. 21:07
https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚡️ 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는..
-
[Python]프로그래머스 N으로 표현/dpalgorithm/문제 2023. 4. 28. 14:39
https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚡️ 문제 설명 ⚡️ 해결 방법 5를 1번 사용해서 만들 수 있는 수 set {5} 5를 2번 사용해서 만들 수 있는 수 set {0, 1, 10, 55, 25} 5를 3번 사용해서 만들 수 있는 수 set = 5를 2번 사용해서 만들 수 있는 수 set 과 5를 1번 사용해서 만들 수 있는 수 set 의 사칙연산 한 set {0, 2, 4, 5, 6, 555, -20, -4, -50, 15, 1..
-
[Python]백준 9663번/N-Queen/백트래킹algorithm/문제 2023. 3. 31. 16:02
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ⚡️ 문제 설명 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제 퀸을 놓는 방법의 수를 구하는 프로그램 ⚡️ 해결 방법 퀸이 서로 공격할 수 없도록 하는 방법 1. 같은 행에 위치하면 안됨 2. 같은 열에 위치하면 안됨 3. 대각선상에 위치하면 안됨 graph_col 은 X행에서 퀸이 놓인 열의 위치를 저장할 것이다. queen을 놓은 뒤 이 queen의 자리가 p..
-
[Python]백준 13335번/트럭/queuealgorithm/문제 2023. 3. 29. 11:45
https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net ⚡️ 문제 설명 다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램 ⚡️ 해결 방법 bridge에 모든 트럭이 지나갈 때 까지 ( while bridge) 반복한다. 기다리고 있는 truck 이 있다면 현재 bridge 위에 있는 트럭의 무게 합 sum(..
-
[Python]백준 11441/합 구하기 / 누적합algorithm/문제 2022. 3. 14. 16:01
https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net ⚡️ 문제 설명 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램 ⚡️ 해결 방법 처음에 for _ in range(m): i,j=map(int,input().split()) print(sum(A[i-1:j])) 이렇게 코드를 작성하여 더하였더니 시간초과가 발생하였다. 시간초과를 해결하..
-
[Python]백준 11053/가장 긴 증가하는 부분 수열/LIS/dpalgorithm/문제 2022. 3. 13. 13:01
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ⚡️ 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. ⚡️ 해결 방법 가장 긴 증가하는 부분 수열 Logest Increasing Subsequence (LIS) 는 전형적인 dp의 문제이다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에..
-
[Python]백준 14502/연구소 / 조합 / 배열 복사 copyalgorithm/문제 2022. 3. 12. 16:18
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ⚡️ 문제 설명 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램 ⚡️ 해결 방법 ex) 1 단계 : 빈칸인 위치 모두 찾기 empty_list = [] for empty_x in range(n): for empty_y in range(m): if initGraph[empty_x][empty_y] =..