본문 바로가기

C++

 (113)
[백준 15904번] UCPC는 무엇의 약자일까? link : https://www.acmicpc.net/problem/15904 UCPC는 무엇의 약자일까? 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초 (언어별 추가 시간 없음)512 MB36615913749.818%문제UCPC는 '전국 대학생 프로그래밍 대회 동아리 연합 여름 대회'의 줄임말로 알려져있다. 하지만 이 줄임말이 정확히 어떻게 구성되었는지는 아무도 모른다. UCPC 2018을 준비하던 ntopia는 여러 사람들에게 UCPC가 정확히 무엇의 줄임말인지 물어보았지만, 아무도 정확한 답을 제시해주지 못했다. ntopia가 들은 몇 가지 답을 아래에 적어보았다.Union of Computer Programming Contest club contestUnion of Computer Pr..
[백준 15903번] 카드 합체 놀이 link : https://www.acmicpc.net/problem/15903 카드 합체 놀이 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초 (언어별 추가 시간 없음)512 MB34215014250.000%문제석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)계산한 값을 x번 카드와 y번 카..
[백준 15894번] 수학은 체육과목입니다 link : https://www.acmicpc.net/problem/15894 수학은 체육과목 입니다 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초 (언어별 추가 시간 없음)512 MB43524122464.928%문제성원이는 수학을 정말 못 하는 고등학생이다. 수학을 못하는 대신 근성과 팔 힘이 뛰어난 성원이는 수학 시험에서 수학 지식을 사용하지 않고 근성과 체력을 사용해 문제를 푼다. 지난 시험에서는 아래 사진에 나와있는 문제를 근성과 체력을 사용해 열심히 풀었지만 사진에서 볼 수 있듯이 틀려버리고 말았다!결국 이 문제는 틀려버렸지만 성원이는 여전히 자신의 체력에 강한 자신감을 갖고 있다. 어떤 어려운 문제가 나와도 이런 식으로 근성과 체력을 사용하면 다 풀 수 있으니 이 방법은 최고의 방법..
[백준 2252번] 줄세우기 link : https://www.acmicpc.net/problem/2252 줄 세우기 성공 스페셜 저지시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB50582597176751.217%문제N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.입력첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B..
위상정렬(topological sorting) 1. 개념 위상 정렬은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequistie) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 이 점에서 비순환 유향 그래프이다. *출처 : 위키디피아 ..
[백준 2188번] 축사 배정 link : https://www.acmicpc.net/problem/2188 축사 배정 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB32921668101248.771%문제농부 John씨는 그의 소 축사를 갓 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, John씨는 축사를 N개의 칸으로 구분하여 두고, 한 칸에는 한 마리의 소만을 들어가도록 하였다.첫 주에는 소들을 임의적으로 칸에 배정하여 축사를 운영하였으나, 곧 문제가 발생하게 되었다. 자신들이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.농부 John씨를 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다고 한다.입력첫째 줄에 소의 마릿수 ..
[백준 5397번] 키로거 link : https://www.acmicpc.net/problem/5397 키로거 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB79881873112022.047%문제창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 하지만, 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력하면 정확한 비밀번호를 알아낼 수가 없다.강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 ..
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) 1. 개념 정점 V개가 있고, 거리가 모두 주어져 있을 때 단 한 번의 시행으로 모든 정점 쌍 사이의 거리를 모두 구하는 알고리즘이다. 음의 가중치가 있는 간선 그래프에서도 사용이 가능한 것이 특징이다. 2. 구현 플로이드 알고리즘은 전형적인 3중 for문의 형태를 하고 있고, 시간 복잡도가 O(n^3)이다. 각 정점 a, b 쌍에 대해서 a에서 b로 가는 최단 경로를 한 번에 다 구해야하므로 2차원 배열 ary를 준비한다. 초기값은 자기 자신에게 가는 ary[i][i] = 0 , 나머지는 ary[i][j] = ∞ 로 초기화한다. 그리고 간선 정보를 받은 후에 a->b로 가는 거리가 w라면 ary[a][b] = w로 갱신한다. 만약 a->b로 가는 거리가 여러 개라면 그 중 가장 작은 값을 사용한다. 플..

티스토리툴바