본문 바로가기

백준27

백준 1707번 C++ 이분 그래프 이분 그래프https://www.acmicpc.net/problem/1707그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 푸는 법이분 그래프인지 확인하는 법알고리즘 검색하다 보면 꼭 나오는 이 분의 블로그를 보고 그냥 이대로만 하면 맞을 수 있다.주의할 점은 테스트 케이스를 실행할 때마다 그래프와 체크를 초기화해주는 것이다.나는 DFS로 풀었고, 만약 start의 색깔과 next의 색깔이 이미 존재하고(둘다 방문했고) 색깔이 같으면 재귀문을 빠져나와 answer이 N.. 2019. 6. 12.
백준 11004번 C++ K번째 수 K번째 수https://www.acmicpc.net/problem/11004수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 문제는 간단해보였는데...아마 이걸 푸는 사람들을 기다리는 건 시간초과일 것이다.그냥 알고리즘 헤더에 있는 소트함수로 하면 될 것 같았는데 안 돼서 오늘 Min Heap으로 풀었다.그랬더니 아슬아슬하게 통과.radix sort를 이용하면 시간복잡도는 O(dn) (d: 데이터의 가장 큰 자리수, n: 데이터수)이라고 한다. 더 빠르게 풀 수 있을 듯우선순위 큐 최고...시간초과 참고는 여기 코드123456789101112131415161718#include #include using namespa.. 2019. 6. 10.
백준 10824번 C++ 네 수 네 수https://www.acmicpc.net/problem/10824네 자연수 A, B, C, D가 주어진다. 이때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오.두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다. 이게 정답률이 37퍼?이유가 다 있는 거다.입력 조건을 무시하고 풀면 이렇게 된다. 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) 이 조건을 무시하고 그냥 풀었을 때, 만약 백만을 이어 붙이게 되면10000001000000이 되는데, 이는 stoi로 변환했을 때 범위를 초과하므로(int로 변환) 런타임 에러가 날 수밖에 없다.저 조건만 주.. 2019. 6. 7.
백준 2225번 C++ 합분해 합분해https://www.acmicpc.net/problem/22250부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 생각하는 과정아직도 dp를 잘 못 이해하고 있었던 건지 ㅠㅠ 이상하게 풀려고 했었다.끄적거리다가 맥도날드가 시끄러워서 견딜 수 없게 되었을 즈음 이렇게 하면 되는구나 생각이 났다. 예를 들어, 0부터 5까지의 정수 4개를 이용하여 5를 만든다고 해보자.그러면 처음에는1000010000100001로 시작할 수 있다.이 네 개를 단위벡터 단위행렬... 처럼 하나의 단위로 생각하고 2번째도 구하면 된다.1000+1000=.. 2019. 6. 2.
백준 9461번 C++ 파도반 수열 파도반 수열오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 생각하는 과정그냥 나열해 보면 된다.규칙은 바로 보이는데 이게 맞나 싶어서 계속 나열해 보았다. 11 ->11 1 ->11 1 1->1+11 1 1 2->1+11 1 1 2 2->1+2 4차이1 1 1 2 2 3->1+3 4차.. 2019. 6. 1.
백준 1912번 C++ 연속합 연속합https://www.acmicpc.net/problem/1912n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 생각하는 과정이 문제에서 생각해 볼 수 있는 케이스는 연속일 때만을 고려하므로, 두 가지다.i번째를 선택한다는 가정하에1) 연속이 아닐때(i-1번째를 선택하지 않을 때) -> dp[i] 선택(자기 자신만을 가지고 감)2) 연속일 때(i-1번째를 선택할 때) -> dp[i-1]+series[i] 선택(자.. 2019. 5. 30.
백준 1015번 C++ 수열 정렬 수열 정렬https://www.acmicpc.net/problem/1015P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. 코드12345678910111213141516171819202122232425#include using namespace std;int main() { i.. 2019. 5. 29.
백준 2133번 C++ 타일 채우기 타일 채우기https://www.acmicpc.net/problem/21333×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 생각하는 과정처음에는 진짜 단순하게 생각했다.일단 N이 홀수이면 홀수x홀수=홀수이기 때문에 2x1, 1x2크기의 타일로 벽을 채우는 것은 불가능하다.따라서 경우의 수는 0그리고 N이 짝수이면 i)N이 2일 때의 세 가지 경우가 있다.ii)N이 4일 때N이 2일 때 각각 왼쪽 오른쪽에 하나씩 붙이는 경우 3*3 + 위 이미지의 경우 상하 반전할 경우 2이런 식으로dp[6]=3*dp[4] + 2*dp[2]dp[2*i]=3*dp[2*(i-1)] + 2*dp[2*(i-2)]라고 했더니 바로괜히 정답률 35퍼가 아니었다... 그래서 스파게티면을 삶으면서 틈틈히.. 2019. 5. 28.
백준 1699번 C++ 제곱수의 합 제곱수의 합https://www.acmicpc.net/problem/1699어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 생각했던 과정7의 제곱수의 합의 최소 개수를 구한다고 해보자.7보.. 2019. 5. 28.