티스토리

뭉기구름
검색하기

블로그 홈

뭉기구름

nnoonjy.tistory.com/m

뭉이씨 님의 블로그입니다.

구독자
0
방명록 방문하기

주요 글 목록

  • [백준] 11049번 - 행렬 곱셈 순서 문제 링크 : https://www.acmicpc.net/problem/11049 문제크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.같은 곱셈이지만, 곱셈을 하는 순서에 따라서.. 공감수 0 댓글수 0 2025. 3. 7.
  • [백준] 13398번 - 연속합 2 문제 링크 : https://www.acmicpc.net/problem/13398 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다. 입력첫째 줄에 정수 n(1 ≤.. 공감수 0 댓글수 0 2025. 3. 5.
  • [백준] 1256번 - 사전 문제 링크 : https://www.acmicpc.net/problem/1256 문제동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇.. 공감수 0 댓글수 0 2025. 3. 5.
  • [백준] 1722번 - 순열의 순서 문제 링크 : https://www.acmicpc.net/problem/1722 문제1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오. 입력.. 공감수 0 댓글수 0 2025. 3. 1.
  • [백준] 1717번 - 집합의 표현 문제 링크 : https://www.acmicpc.net/problem/1717 문제초기에 𝑛+1개의 집합 {0},{1},{2},…,{𝑛}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 입력첫째 줄에 𝑛, 𝑚이 주어진다. 𝑚은 입력으로 주어지는 연산의 개수이다. 다음 𝑚개의 줄에는 각각의 연산이 주어진다. 합집합은 0 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎가 포함되어 있는 집합과, 𝑏가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎와 𝑏가 같은 집합에 포함되어 있는지를 확인하는 연산.. 공감수 0 댓글수 0 2025. 2. 20.
  • [백준] 1850번 - 최대공약수 문제 링크 : https://www.acmicpc.net/problem/1850 문제모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 입력첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다. 출력첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다. 풀이A, B = map(int, input().split())ans = 0def mod(b,s,l): global ans l = b%s b.. 공감수 0 댓글수 0 2025. 2. 19.
  • [백준] 1016번 - 제곱ㄴㄴ수 문제 링크 :  문제어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 입력첫째 줄에 두 정수 min과 max가 주어진다. 출력첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다. 풀이import mathA, B = map(int, input().split())num = [False for _ in range(A,B+1)]count = 0for b in range(2,int(math.sqrt(B))+1): k = b*b start = max(A, ((A+k-1)//k)*k) .. 공감수 0 댓글수 0 2025. 2. 19.
  • [백준] 1456번 - 거의 소수 문제 링크 : https://www.acmicpc.net/problem/1456 문제어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력첫째 줄에 총 몇 개가 있는지 출력한다. 풀이import mathA, B = map(int, input().split())b = int(math.sqrt(B))num = [0,0,]for i in range(2,b+1): num.append(i)for n in num: if n != 0: for i in range(n+n,len(n.. 공감수 0 댓글수 0 2025. 2. 19.
  • [백준] 1167번 - 트리의 지름 문제 링크 : https://www.acmicpc.net/problem/1167 문제트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결.. 공감수 1 댓글수 0 2025. 2. 17.
  • [백준] 13023번 - ABCDE 문제 링크 : https://www.acmicpc.net/problem/13023 문제BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 .. 공감수 0 댓글수 0 2025. 2. 16.
  • [백준] 11724번 - 연결 요소의 개수 문제 링크 : https://www.acmicpc.net/problem/11724 문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력첫째 줄에 연결 요소의 개수를 출력한다. 해설import sysinput = sys.stdin.readlinesys.setrecursionlimit(10000)N, M = map(int, input().split())points = [[] f.. 공감수 0 댓글수 0 2025. 2. 16.
  • [백준] 11004번 - K번째 수 문제 링크 : https://www.acmicpc.net/problem/11004 문제수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 출력A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. 풀이import sysinput = sys.stdin.readlineN, K = map(int,input().split())A = list(map(int,input().split()))def quickSort(s,e,k): global A if.. 공감수 1 댓글수 0 2025. 2. 13.
  • [백준] 1377번 - 버블 소트 문제 링크 : https://www.acmicpc.net/problem/1377 문제버블 소트 알고리즘을 다음과 같이 C++로 작성했다.bool changed = false;for (int i=1; i A[j+1]) { changed = true; swap(A[j], A[j+1]); } } if (changed == false) { cout  위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자. 입력첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하.. 공감수 0 댓글수 0 2025. 2. 12.
  • [백준] 11003번 - 최솟값 찾기 문제 링크 : https://www.acmicpc.net/problem/11003 문제N개의 수 A1, A2, ..., AN과 L이 주어진다.Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. 입력첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109) 출력첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다. 풀이from collections import dequeN, L = map(int, input().split())A = list(map(int, input().split()))num = deque(.. 공감수 0 댓글수 0 2025. 2. 11.
  • [백준] 1253번 - 좋다 문제 링크 : https://www.acmicpc.net/problem/11003 문제N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다. 입력첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력좋은 수의 개수를 첫 번째 줄에 출력한다. 풀이N = int(input())nums = list(map(int,input().split()))nums.sort()count = 0for n in range(N): k = .. 공감수 1 댓글수 0 2025. 2. 11.
  • [백준] 10986번 - 나머지 합 문제 링크 : https://www.acmicpc.net/problem/10986 문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이N,M = map(int,input().split())A = [0]+list(map(int,inp.. 공감수 1 댓글수 0 2025. 2. 10.
  • [백준] 11660번 - 구간 합 구하기 5 문제 링크 : https://www.acmicpc.net/problem/11660 문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1234234534564567 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 입력첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000).. 공감수 0 댓글수 0 2025. 2. 10.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

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

    © Kakao Corp.