본문 바로가기

알고리즘/백준코딩

 (13)
백준14502번 - 연구소(C++, 삼성 SW 역량 테스트 기출 문제) 삼성 A형을 목표로 백준 문제풀이를 진행하고 있습니다. 처음 삼성 문제를 풀때 '이렇게 풀어도 되나?' 싶을 정도로 무식하게 구현하다가 제출한 문제에 '맞았습니다'가 뜨는걸 보고 삼성 A형 스타일 문제가 어떤 느낌인지 알게 되었습니다.. 괜히 머리 굴리면서 효율적인 문제풀이 방법을 생각하기 보다는 그냥 있는 그대로 구현하는게 정답이였습니다. 다만 구현이 좀 복잡하기 때문에 main함수에 무식하게 구현하기 보다는, 기능 하나하나를 함수화하여 푸는게 간편하다고 느껴졌습니다. 아래 문제집에서 이제 겨우 4문제를 푼 어린이지만.. 1일 1문제씩 풀어서 2월달에 A형 시험을 꼭 합격해보도록 하겠습니다. 문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon) www.acmicpc.net #include #d..
백준 200문제 달성 후기 2021.08.16 백준 알고리즘 200문제 달성 이전까지는 뭐를 공부해야할지도 몰라서 그냥 눈에 보이는 문제들만 풀어왔다면, 200문제 정도 푸니까 이제 뭐가 부족하고 어떤걸 공부해야할지 감이 오는듯 하다. 구현문제는 나름 자신있었는데.. 조금 어려운 구현문제를 보다보니까 내가 구현을 잘한다고 착각하고 있었다는걸 깨달았다. 풀때는 제일 재밌는데 조건 하나씩 틀리기 시작하면 진짜 멘붕.. 그래도 어떻게 풀어야할지 감이 하나도 안오는 DP보다는 구현이 편하다 ㅜ 문제 난이도 분포 거의 브론즈문제를 풀어서 해결한 문제 수를 뻥튀기 시켰다. 무려 4가지 언어를 백준에서 연습했어서(C#, C++, JS, Python) 브론즈 문제의 비중이 유독 높은것같다. 앞으로의 목표는 실버문제를 옛날 브론즈 문제 풀듯이 슉..
백준16496번 - XML 자바스크립트(Node.js)풀이 난이도: 플래티넘 5 문제 음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다. 출력 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다. 출처 University > 한양대 ERICA > 2018 ERICA Software-U..
백준4828번 - XML 자바스크립트(Node.js)풀이 난이도: 플래티넘 4 문제 인터넷프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 항상 학생들에게 XML의 장점을 어필한다. 그러나 잘못 사용되었다가는 지구를 파괴할 수도 있는 무시무시한 부작용도 존재하기에, 문법이 맞게 되었는지를 판정하는 파서가 필요하게 되었다. 그러나 이다솜은 XML을 할 줄 모르기에 여러분이 판독기를 구현해야 한다. 우리가 XML 문서의 형식이 유효한지 판별하는 기준은 다음과 같다. 평문---32~127 사이에 있는(32, 127도 포함) ASCII코드값으로 이루어지며, 다음 문자는 포함되면 안 된다: , & 다음과 같은 문자열: & 이것들은 각각 , &를 인코딩한다. &xHEX; HEX는 양의 짝수 자릿수의 16진수여야 하며, 0~9 또는 알파..
백준9020번 - 골드바흐의 추측 자바스크립트(Node.js)풀이 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수..
백준2960번 - 에라토스테네스의 체 자바스크립트(Node.js)풀이 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000) 출력 첫째 줄에 K번째 지워진 수를 출력한다. 문제유형 수학 구현 정수론 소수 판정 에라토스테네스의 체 에라토스테네스의 체를 몰라도 문제만 잘 읽으면 풀 수 있는 문제이다..
백준1038번 - 감소하는 수 자바스크립트(Node.js)풀이 문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 N번째 감소하는 수를 출력한다. 문제유형 브루트포스 알고리즘 백트래킹 백줄이 넘어가는 정말 보기힘든 코드로 풀고있다가 너무나도 신박한 풀이를 발견하였다. 이 풀이를 nodejs 코드로 변환하고 산책을 하면서 코드를 이해해보았다. encrypted..
백준10830번 - 행렬 제곱 자바스크립트(Node.js)풀이 문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 문제유형 수학 분할 정복 분할 정복을 이용한 거듭제곱 선형대수학 행렬을 n제곱시키는 (개념적으로는)간단한문제. 하지만 시간 제한(1초)에 비해 B값이 커서 최적화를 시켜야 한다. 보통 행렬의 제곱을 최적화하는 연산은 행렬..

티스토리툴바