본문 바로가기

분류 전체보기

 (97)
[PS] 백준 #2012. 등수 매기기 문제 정보 난이도: 실버 III 문제 주소: https://www.acmicpc.net/problem/2012 이 문제를 푼 이유: 그룹 연습 Div.2 문제 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명..
[PS] 백준 #21313. 문어 문제 정보 난이도: 브론즈 II 문제 주소: https://www.acmicpc.net/problem/21313 이 문제를 푼 이유: 그룹 연습 Div. 2 문제 문어에게 여덟개의 팔이 있다는 사실은 잘 알려져 있다. 하지만 문어들이 자신의 팔들을 1번, 2번, 3번, ..., 8번이라고 부른다는 말은 오늘 처음 들었을 것이다! 단, 시계방향으로 오름차순이라던가 하는 규칙은 없다. (물론 그러한 문어도 존재할 수 있다.) 문제에선 편의상 팔 대신 손이라고 부르자. 문어들은 정월 대보름을 맞아 강강술래를 하려고 한다. 각 문어는 양 옆의 서로 다른 두 문어와 손을 맞잡아 원을 만든다. 문어끼리 손을 잡을 때 지켜야 할 예절이 있다. 서로 같은 번호의 손을 잡아야 한다. 한 문어와 둘 이상의 손을 잡을 수 ..
[PS] 백준 #21968. 선린의 터를 문제 정보 난이도: 실버 IV 문제 주소: https://www.acmicpc.net/problem/21968 이 문제를 푼 이유: 그룹 연습 Div.2 문제 드높은 남산 위에 우뚝 선 (중략) 세워라 반석 위에 선린의 터를 1899년, 여러분들은 대한제국 고종 황제의 칙령을 받아 한국 최초의 실업교육기관인 관립상공학교를 세울 터를 선택해야 한다. 대한제국에서 학교를 지을만한 터는 여러 개 있는데, 각 터는 서로 다른 자연수를 번호로 갖고 있다. 특히, 선린의 터의 번호는 $3^k$꼴의 자연수가 최대 한 번씩 더해진 자연수이다(단, $k \ge 0$). 즉, 선린의 터의 번호는 $1(=3^0), 3(=3^1), 9(=3^2), 27(=3^3), 81(=3^4), 90(=3^2+3^4), 91(=3^0+3..
[PS] 백준 #21966. (중략) 문제 정보 난이도: 실버 V 문제 주소: https://www.acmicpc.net/problem/21966 이 문제를 푼 이유: 그룹 연습 Div.2 문제 드높은 남산 위에 우뚝 선 (중략) 세워라 반석 위에 선린의 터를 1개 이상의 문장들이 주어진다. 아래 규칙에 따라 문장들의 중간 부분을 적당히 생략해 25글자 이내로 요약해서 출력하는 프로그램을 작성하자. 단, 입출력의 편의를 위해 문장들을 공백 없이 모두 붙여 구성한 문자열 S$S$가 대신 주어진다. 문자열의 첫 글자부터 가장 먼저 만나는 '.'(마침표)까지, 그리고 각 '.'의 다음 글자부터 가장 먼저 만나는 '.'까지를 한 문장으로 생각하기로 하자. 예를 들어 주어진 문자열 $S$가 'IamInevitable.IamIronMan.'이라면 'I..
[종만북] 6장. 완전 탐색 (2) PICNIC 문제 바로가기: https://www.algospot.com/judge/problem/read/PICNIC 1. 중복된 답 아래 코드의 문제점은 중복된 답을 세는 경우를 처리하지 않은 점이다. 중복이 된 원인은 (0, 1)과 (1, 0)을 각각 다른 경우로 봤고 다른 순서로 학생들을 짝지어 주는 것도 서로 다르다고 카운트했기 때문이다. #include using namespace std; int n; bool graph[10][10]; // 최대 10 int countPairings(bool taken[10]) { // taken[i]: i번 학생이 짝을 찾은 경우 true // Base case: 전부 짝이 생기면 종료 bool finished = true; for (int i = 0; i < n; i..
[종만북] 6장. 완전 탐색 (1) 원소 고르기, BOGGLE 1. 예제: n개의 원소 중 m개를 고르는 모든 경우의 수 찾기 #include using namespace std; void printPicked(vector& picked) { for (int p : picked) { cout > t; while (t--) { wordmap.resize(5); for (int i = 0; i > wordmap[i][j]; } int n; cin >> n; while (n--) { string str; cin >> str; bool isFind = false; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5..
[220117] 백준 300문제 달성 이번 방학에 본격적으로 백준 알고리즘 문제를 풀게된건 어제부터였다. 작년 여름방학때 300문제 살짝 모자라게 풀고 끝나서 조금 아쉬웠는데, 이번에 이틀만에 300문제를 달성하였다. 300번째로 푼 문제는 볼록 껍질 문제로, 블로그에 풀이를 올렸다. (https://pongkijoa.tistory.com/53) 이번 방학 때는 군대가기 전까지 400~500문제를 목표로 더 열심히 풀어봐야겠다.
[PS] 백준 #1708. 볼록 껍질 문제 정보 난이도: 플래티넘 V 문제 주소: https://www.acmicpc.net/problem/1708 이 문제를 푼 이유: 300번째 문제 기념 문제 다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다. 조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다. 2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라..

티스토리툴바