티스토리

E-room Achievement Logs

검색하기

블로그 홈

E-room Achievement Logs

e-room.tistory.com/m

나의 성취 기록들

구독자: 3

방명록 방문하기

주요 글 목록

프로그래머스 - 뉴스 클러스터링 [자바] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 요약 두 문자열의 자카드 유사도를 구하시오. 2. 접근 방법 문자열이 주어질 때, 알파벳의 경우에만 원소로 사용한다는 점을 이용합니다. 2글자까지만 사용하기 때문에 경우의 수는 26 * 26이 됩니다. 각각의 문자열을 검사하여 26 * 26의 int[][] 배열에 담아줍니다. 문제를 읽어보면 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 라고 힌트를 주고 있습니다. 이전 단계에서 생성한 배열에 힌트를 그대로 사용.. 공감수 0 댓글수 0 2023. 11. 28.
백준 - 11725 트리의 부모 찾기 [DFS][BFS] 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 요약 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 2. 파이썬 2 - 1. BFS 백준 - 2606 바이러스 [BFS] 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 e-room.tistory.com 2 - 2. 코드 N = int(input()) tree = [[] for _ in range(.. 공감수 0 댓글수 0 2023. 11. 5.
백준 - 1991 트리 순회 [Tree] 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 문제 요약 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하라. 2. 접근 방법 새로운 노드로 이동할 때마다 순회별 방문 순서를 반복한다고 생각하면 됩니다. 순서가 헷갈릴 수 있는데, 세 단계를 반복하면 쉽습니다. 예시) 전위 순회의 경우 현재 노드 출력 왼쪽 이동 오른쪽 이동 2 - 1. 전위 순회 ABDCEFG /.. 공감수 0 댓글수 0 2023. 11. 1.
프로그래머스 - 짝지어 제거하기 [Stack] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 요약 문자열 s가 주어집니다. 문자열 s안에 연속으로 같은 알파벳 2개가 있으면 제거하고 앞뒤로 이어 붙입니다. 해당 과정을 계속 반복하여 모든 알파벳을 제거할 수 있으면 1을 리턴하고, 없으면 0을 리턴합니다. 2. 접근 방법 제거할 수 없는 알파벳을 담을 Stack을 초기화합니다. 문자열을 순차적으로 방문합니다. Stack이 비어있으면 현재 알파벳을 넣습니다. Stack에 최근에 넣은 알파벳과 현재 알파벳이 다를 경우 제거할 수 없으므로 현재 알파벳을 넣습니다. Stack에 최근에 넣은 알파벳과.. 공감수 0 댓글수 0 2023. 10. 30.
백준 - 2606 바이러스 [BFS] 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1. 문제 요약 컴퓨터의 수 n, 직접 연결된 컴퓨터의 수 m, 연결된 컴퓨터 쌍의 번호가 주어진다. 1번 컴퓨터와 직간접적으로 연결되어 있는 컴퓨터의 수를 구하시오. 2. 접근 방법 BFS(너비 우선 탐색) 알고리즘을 활용합니다. 1번을 기준으로 찾으면 되기 때문에, 4번과 7번은 무시합니다. 방문할 리스트를 생성하고 해당 리스트의 맨 앞부분에 1번을 추가합니다. (Deque 추천) 방문 리스트의 맨 앞 인덱스부터 순차적으로 방문합니다. 1번을 방문합니다. 1번을 .. 공감수 0 댓글수 1 2023. 10. 28.
백준 - 2606 바이러스 [DFS] 자바 백준 1위 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1. 문제 요약 컴퓨터의 수 n, 직접 연결된 컴퓨터의 수 m, 연결된 컴퓨터 쌍의 번호가 주어진다. 1번 컴퓨터와 직간접적으로 연결되어 있는 컴퓨터의 수를 구하시오. 2. 접근 방법 DFS(깊이 우선 탐색) 알고리즘을 사용합니다. 1번을 기준으로 찾으면 되기 때문에, 4번과 7번은 무시합니다. 1번에서 2번을 방문하고, 2번은 방문했다고 표시를 합니다. 2번에서 방문할 수 있는 곳들 중 방문하지 않은 곳을 방문합니다. 3번으로 방문 후, 더 이상 방문할 곳이 없으므.. 공감수 0 댓글수 1 2023. 10. 28.
백준 - 2805 나무 자르기 [이분 탐색] 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 문제 요약 나무의 수 n, 가져가려고 하는 나무의 길이 m이 주어지고, 나무의 높이 수열이 주어진다. 자를 높이를 지정하면 해당 높이에 맞게 모든 나무가 잘리며, 지정한 높이 이하의 나무들은 잘리지 않는다. m을 만족하면서 자를 수 있는 나무의 높이의 최솟값을 구하시오. 2. 접근 방법 자르는 높이 별로 얻을 수 있는 나무의 길이를 수열이라 생각하고 이분 탐색을 활용하여 풀면 쉽게 풀 수 있습니다. 빨간색이 배열의 인.. 공감수 0 댓글수 1 2023. 10. 25.
백준 - 10815 숫자 카드 [이분탐색] 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. 문제 요약 숫자 배열이 주어지고, 찾고자 하는 숫자가 주어졌을 때, 찾고자 하는 숫자가 배열에 존재하는지 판단하시오. 2. 접근 방법 이분 탐색 알고리즘을 사용합니다. 해당 알고리즘은 일반적으로 하는 up down 게임과 같은 원리입니다. 정렬된 상태에서 절반씩 소거하며 찾아내는 방법입니다. 오름차순으로 정렬된 배열에서 중간 부분을 탐색하고, 찾고자 하는 숫자보다 크면 해당 지점부터 끝부분까지의 중간 부분을 탐색합니다. 찾고자 .. 공감수 0 댓글수 0 2023. 10. 24.
백준 - 16472 고냥이 [투포인터] 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 1. 문제 요약 n과 문자열이 주어지고, 문자열에서 최대 n개의 종류의 알파벳을 포함한 문자열의 길이를 구하라. 2. 접근 방법 투포인터 알고리즘을 사용하여 문자열을 순차적으로 검사합니다. j(끝) 위치의 알파벳이 새로운 알파벳일 경우 count += 1을 하고 사용 중인 알파벳으로 표시합니다. 사용 중인 알파벳의 종류가 n보다 클 경우 줄어들 때까지 i(시작) 위치의 알파벳을 이동합니다. 사용 중인 알파벳 종류가 하나 줄어들 경우 count -= 1 표시를 해줍니다. 현.. 공감수 0 댓글수 0 2023. 10. 23.
백준 - 22988 재활용 캠페인 [투포인터] 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 1. 문제 요약 헤어에센스 용기의 수 n, 용기의 용량 x, 각 용기에 현재 들어있는 양의 수열 arr이 주어진다. 용기 2개를 갖다 주면, 두 용기에 남아있는 잔량 + x/2 만큼 채워진 헤어에센스를 준다. 단, 용기의 용량보다 넘치게 주지는 않는다. 현재 가지고 있는 용기를 이용하여 가득 찬 헤어에센스를 최대 몇 병 만들 수 있는지 구하시오. 2. 접근 방법 이미 가득 .. 공감수 0 댓글수 1 2023. 10. 23.
백준 - 3273 두 수의 합 [투포인터] 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 1. 문제 요약 자연수 수열이 주어지고 해당 수열의 수들 중, 두 수를 합하여 x와 같은 경우의 수를 구하라. 2. 접근 방법 - 투 포인터 배열을 오름차순으로 정렬합니다. 성능 향상 : x보다 작은 수들만 사용하도록 필터링 i = 0, j = 수열의 크기 - 1 arr[i] + arr[j] == x 일 경우 answer += 1 i += 1, j -= 1 (정렬을 했기 때문에, 해당 수들을 더했을 때, x.. 공감수 0 댓글수 1 2023. 10. 21.
백준 - 9251 LCS [LCS] 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 요약 최장 공통 부분 수열의 길이를 구하시오. 2. 접근 방법 LCS는 굉장히 잘 알려진 유명한 알고리즘입니다. 범위를 지정하여 끝의 문자를 비교하는 방식입니다. m = "ACAYKP" n = "CAPCAK" 문자를 하나씩 비교하여 같을 경우는 dp[i][j] = [i-1][j-1] +1 이 됩니다. ACA와 CA를 비교할 경우 A가 같습니다. A를 떼놓고 비교한다면 AC와 C를 비교한값 + 1(A가 같으므.. 공감수 0 댓글수 0 2023. 10. 20.
백준 - 2565 전깃줄 [LIS] 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. 문제 요약 전깃줄의 좌표가 주어지고 전깃줄이 꼬여있지 않도록 하기 위해 제거해야 할 전깃줄의 최솟값을 구하시오. 2. 접근 방법 A전봇대를 기준으로 정렬한 뒤, B전봇대 값으로 LIS를 사용하면 쉽게 답을 구할 수 있습니다. 백준 - 11053 가장 긴 증가하는 부분 수열 [LIS] 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30,.. 공감수 0 댓글수 0 2023. 10. 19.
백준 - 11053 가장 긴 증가하는 부분 수열 [LIS] 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 문제 요약 수열 A가 주어졌을 때, 최장 증가 부분 수열의 길이를 구하시오. 2. 접근 방법 배열을 순회하며, 현재 숫자의 이전 인덱스의 숫자들 중, 현재 숫자보다 작은 경우, 현재 dp와 찾은 숫자의 dp를 비교하여, 더 큰 값을 현재 dp에 저장한다. 현재 숫자의 이전 숫자가 없는 경우 1을 저장한다. 2 이전 숫자들 중, 1이 가장 작으므로 데려오며, +1을 해준다. 1의 이.. 공감수 0 댓글수 1 2023. 10. 18.
백준 - 1520 내리막 길 [DP] 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 요약 M * N 의 지도가 주어지고, 해당 지도에는 각 칸의 높이가 표시되어 있다. 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 현재 위치보다 낮은 위치로만 이동할 수 있다. 세준이는 0, 0의 위치에서 시작하여 지도의 가장 우측하단까지 이동하는 방법은 모두 몇 가지인가? 2. 접근 방법 0, 0 에서 가능한 모든 경우의 수를 탐색합니다. 재귀로 구현합니다. def solution(y, x): # 목적지 도착 여부 if y == M-1 .. 공감수 0 댓글수 0 2023. 10. 17.
백준 - 1937 욕심쟁이 판다 [DP] 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 문제 요약 N * N 의 대나무 숲이 주어지고, 해당 숲에는 대나무의 양이 적혀있다. 판다는 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 이동한 곳의 대나무 양은 이전 위치보다 많아야 한다. 판다가 가장 많이 이동할 수 있는 횟수는 몇번인가? 2. 접근 방법 모든 대나무 숲을 방문합니다. 재귀 함수로 구현합니다. # 재귀함수로 구현 def solution(y, x): move = 0 for dy, dx in [[y-1, x],.. 공감수 0 댓글수 0 2023. 10. 16.
백준 - 1149 RGB거리 [DP] 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 문제 요약 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 빨강, 초록, 파랑으로 집을 칠할 때, 연속되지 않게 칠할 수 있으며, 최소 비용을 구하라. 2. 접근 방법 먼저 가장 완벽한 알고리즘인 완전탐색으로 구현해 보았습니다. N = int(input()) rgb = [list(map(int, input().split())) for _ in range(N)] answer = 1.. 공감수 0 댓글수 0 2023. 10. 13.
백준 - 11726 2×n 타일링 [DP] 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1. 문제 요약 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하시오. 2. 접근 방법 숨어있는 규칙을 찾아봅시다. i : 방법 1 -> 1 2 -> 2 3 -> 3 4 -> 5 5 -> 8 6 -> 13 7 -> 21 자세히 살펴보면 규칙을 발견할 수 있습니다. 현재 인덱스의 방법은 이전의 두 인덱스의 방법의 합과 같습니다. 즉, n = (n-1) + (n-2) 가 됩니다. 이는 피보나치 수열의 형태입니다. 이를 토대로 재귀함수를 이용합니다. def solut.. 공감수 0 댓글수 1 2023. 10. 12.
백준 - 12865 평범한 배낭 [DP][탑다운][바텀업] 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제 요약 물품의 수 N, 버틸 수 있는 무게 K, 각 물건의 무게 W, 물건의 가치 V가 주어집니다. 물건들을 가장 많이 가져갈 수 있는 조합을 구하시오. 2. 접근 방법 먼저 완전탐색으로 모든 경우의 수를 다 때려 넣어봅니다. def solution(idx, w, v): global answer if w > K: return if idx == N: answer = max(answer, v).. 공감수 0 댓글수 1 2023. 10. 10.
백준 - 14501 퇴사 [브루트포스] 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 문제 요약 스케줄이 주어지고 해당 스케줄에서 가장 많은 수익을 낼 수 있는 조합을 구하시오 2. 접근 방법 재귀함수를 이용하여 모든 조합을 계산합니다. 그중 가장 많은 수익을 낸 조합을 출력합니다. 3. 파이썬 def solution(index:int, p:int): global P if index == N: P = max(P, p) return elif index < N: solution(index+TP[index][0],p+TP[index][1]) # 일을 하거나 solution(index+1, p) # 하지 않거나 4. 자바 static private void recursive(int in.. 공감수 0 댓글수 0 2023. 10. 7.
백준 - 19942 다이어트 [백트래킹] 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 1. 문제 요약 N개의 식재료가 주어지고, 해당 식재료를 이용하여 영양성분을 만족하는 최저 비용 조합을 구하라 2. 접근 방법 재귀함수를 이용하여 모든 조합을 구한다. 영양성분을 만족하는 조합들 중 최저 비용을 계산한다. 3. 파이썬 def solution(index:int, used:list): global C, USED if index == N: p, f, s, v, c = 0, 0, 0, 0, 0 for i in used: p += PFSVC[i-1][0].. 공감수 0 댓글수 1 2023. 10. 6.
백준 - 2961 도영이가 만든 맛있는 음식 [백트래킹] 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 1. 문제 요약 재료의 개수 N, 그 재료의 맛 S, B가 주어진다. S는 곱, B는 덧셈으로 맛이 변한다. 재료를 적절하게 조합하여 S와 B의 차가 가장 작은 경우의 맛을 출력하라. 2. 접근 방법 재귀함수를 이용하여 조합을 구해줍니다. 재료를 사용하거나, 사용하지 않거나로 구분하여 진행합니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth:int, used:.. 공감수 0 댓글수 0 2023. 10. 6.
백준 - 15656 N과 M (7) [백트래킹] 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 골라 오름차순으로 정렬된 수열을 생성하라. 같은 수를 여러 번 사용해도 된다. 2. 접근 방법 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 수열 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: print(' '.join(map(str, arr))) return for i in range.. 공감수 0 댓글수 0 2023. 9. 28.
백준 - 15650 N과 M (6) [조합] 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 뽑아 조합(Combination)을 만드는 문제입니다. 고른 수열은 오름차순이어야 합니다. 2. 접근 방법 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 조합 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(start: int, depth: int): if depth == M: print(' '.join(map(str, arr))) re.. 공감수 0 댓글수 0 2023. 9. 28.
백준 - 15654 N과 M (5) [순열] 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다. 출력 시 오름차순으로 정렬하여야 합니다. 2. 접근 방법 순열을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 순열 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: prin.. 공감수 0 댓글수 0 2023. 9. 28.
백준 - 15652 N과 M (4) [백트래킹] 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 자연수를 사용하여 길이가 M인 수열을 생성하라 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 2. 접근 방법 재귀 함수를 사용합니다. 15650(조합) 과 15651 을 적절히 섞으면 됩니다. 3. 파이썬 from sys import stdin input = stdin.readline def soluti.. 공감수 0 댓글수 2 2023. 9. 28.
백준 - 15651 N과 M (3) [백트래킹] 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 수열을 생성하라. 같은 수를 여러 번 골라도 된다. 2. 접근 방법 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: # print(*arr) print(' '.join(map(str, arr))) # 위 방식보다 좀 더 효율적입니다. retu.. 공감수 0 댓글수 0 2023. 9. 28.
백준 - 15650 N과 M (2) [조합] 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 조합(Combination)을 만드는 문제입니다. 2. 접근 방법 조합을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(start: int, depth: int): if depth == M: print(*arr) return for i in range(start, .. 공감수 0 댓글수 0 2023. 9. 27.
백준 - 15649 N과 M (1) [순열] 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다. 2. 접근 방법 순열을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 3 - 1. 재귀함수 이용 from sys import stdin input = stdin.readline n, m = map(int, input().split()) def solution(num: int, arr: list): if num == m: print(.. 공감수 0 댓글수 0 2023. 9. 26.
백준 자바1위 - 17611 직각다각형 [누적합][이모스] 17611번: 직각다각형 입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (xi, yi)가 차례대로 주어진다. 주어지 www.acmicpc.net 1. 문제 요약 다각형의 좌표가 주어지고 수직선과, 수평선에 대하여 해당 다각형의 수직선분과, 수평선분이 가장 많이 교차하는 횟수를 구하라. 2. 접근 방법 백준 - 3020 개똥벌레 [누적합][이모스] 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종 e-room.tistory.com 해당 문제.. 공감수 0 댓글수 0 2023. 9. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.