본문 바로가기

백준198

[백준] 4358번 - 생태학 (C++) 문제 및 풀이 문제) 백준 - 구현 - 생태학 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 해시 맵을 통해 나무 종의 비율을 구하는 문제였습니다. 해시 맵은 쉽게 해결했으나, printf를 통해 소수점을 구현하는 단계에서 맞왜틀을 시전 했습니다.(아직도 왜 틀렸는지 모르겠습니다.) 결국 cout.precision을 통해 소수점 반올림을 처리했더니 AC 받았습니다. C++ 소스코드) 2022. 1. 23.
[백준] 3151번 - 합이 0 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 합이 0 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net N이 최대 10000이므로 O(N*N*logN)의 시간 복잡도로 해결할 수 있었습니다. 두 개의 숫자(이중 반복문)를 선택 후, 이분 탐색을 통해 나머지 숫자들 중 0이 되는 숫자의 개수를 세어주면 해결할 수 있습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Probl.. 2022. 1. 23.
[백준] 19699번 - 소-난다! (Python) 문제 및 풀이 문제) 백준 - 수학 - 소-난다! https://www.acmicpc.net/problem/19699 19699번: 소-난다! 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 www.acmicpc.net 에라토스테네스의 체로 소수 판별을 진행합니다. H의 범위가 1000 이하이고 뽑힐 수의 개수(M)가 최대 9개이기에 MAX를 10000으로 잡았습니다. 조합을 뽑아야 하기 때문에 C++ 대신 Python을 이용해 문제를 해결했습니다. Python 소스코드) 2022. 1. 21.
[백준] 10546번 - 배부른 마라토너 (C++) 문제 및 풀이 문제) 백준 - 문자열 - 배부른 마라토너 https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net 중복된 이름도 존재하기 때문에 set보다는 multiset을 이용합니다. N개의 이름을 입력받아 multiset에 insert 후, N-1개의 이름을 지우고 남은 하나의 이름을 출력합니다. C++ 소스코드) 2022. 1. 21.
[백준] 1072번 - 게임 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 이분 탐색으로 승률이 오를 승수를 계산합니다. 승률이 증가했을 경우 ans 업데이트 후 범위를 줄이는 식으로 이분 탐색을 진행합니다. C++ 소스코드) 2022. 1. 20.
[백준] 14567번 - 선수과목 (Prerequisite) (C++) 문제 및 풀이 문제) 백준 - 위상 정렬 - 선수과목 (Prerequisite) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 선수과목 제목보고 위상 정렬을 예상했으나 역시였습니다. 위상 정렬로 선수 과목을 탐색하면서 해당 과목을 들은 학기를 메모한 후 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/14567_%EC%84%A0%EC%88%98%.. 2022. 1. 20.
[백준] 1159번 - 농구 경기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 농구 경기 https://www.acmicpc.net/problem/1159 1159번: 농구 경기 상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작 www.acmicpc.net 알파벳 배열을 만들어 문자열의 첫 글자만 확인하여 하나씩 세어주어 해결했습니다. C++ 소스코드) 2022. 1. 20.
[백준] 18427번 - 함께 블록 쌓기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 함께 블록 쌓기 https://www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 학생의 인덱스와 높이를 memoization을 진행합니다. 학생 수(N), 블록 개수(M), 높이(H)의 범위가 충분히 작아 O(N*M*H)의 시간 복잡도로 해결할 수 있었습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/ma.. 2022. 1. 19.
[백준] 11562번 - 백양로 브레이크 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 건물의 수(n)가 250 이하이기 때문에 O(n^3)의 시간 복잡도를 가진 플루이드 와샬로 풀이가 가능합니다. 양방향 길은 모두 0, 일방통행 길은 한 방향은 0으로 나머지는 1로 부여해 플루이드 와샬을 진행합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/ma.. 2022. 1. 19.
반응형

티스토리툴바