본문 바로가기
728x90

C++

[백준알고리즘] 1032번: 명령 프롬프트 -C++ [백준알고리즘] 1032번: 명령 프롬프트 -C++ 1032번: 명령 프롬프트 (acmicpc.net) 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 문자열 정규 표현식과 관련된 문제다. 실제로 문제에서 주어진 것처럼 '?'는 정규식에서 '임의의 한 글자'를 의미한다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 입력이 들어오는 여러 문자열을 받은 뒤, 첫 문장을 기준으로 비교를 했다. 각 위치마다 모든 문자열에 같은 문자(\(character\))가 들어간다면 해당 문자를 추가해주었고, 그렇지.. 더보기
[백준알고리즘] 1014번: 컨닝 -C++ [백준알고리즘] 1014번: 컨닝 -C++ 1014번: 컨닝 (acmicpc.net) 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 으으음.. 되게 어려웠다. 처음에는 단순히 Bruteforce 방식으로 푸는데 DFS를 적용해서 풀었다. 거의 다 풀었다가 생각해보니까 시간 복잡도가 초과한다는 것을 알게 되었다. 사실상 브루트 포스를 푸는 것이기 때문에 \(O(2^(n * m))\)의 시간 복잡도가 걸려 최대 \( 2^{100} = 1,267,650,600,228,229,401,496,703,205,376 \)라는 말도 연산.. 더보기
[백준알고리즘] 1026번: 보물 -C++ [백준알고리즘] 1026번: 보물 -C++ 1026번: 보물 (acmicpc.net) 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 음 뭔가 브루트포스로 돌리면서 어려울 것 같았는데, 실상은 그렇지 않았다. 정답률이 보장하는 쉬운 문제였던 것 같다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제는 A 배열과 B 배열을 정렬해서 각 원소의 곱의 합이 최소가 되도록 만들면 된다. 문제에서는 B 배열의 순서를 이동시킬 수 없다고 해서 변수 명도 \(vecNonVariable\)로 잡기는 했지만,.. 더보기
[백준알고리즘] 1027번: 고층 건물 -C++ [백준알고리즘] 1027번: 고층 건물 -C++ 1027번: 고층 건물 (acmicpc.net) 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net Gold IV 단계의 난이도인데 생각보다 쉬웠던 것 같다. 문제 자체도 크게 어렵지 않은 것 같고.. 논리적으로도 명확하게 주제를 준 것 같다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제의 요구 사항부터 살펴보도록 하겠다. 선분으로 나타낼 수 있는 빌딩들이 존재한다. 각 빌딩의 지붕에서 다른 빌딩의 지붕으로 선분을 그린다. 다른 빌딩의 지붕과의 선분 사.. 더보기
[백준알고리즘] 1025번: 제곱수 찾기 -C++ [백준알고리즘] 1025번: 제곱수 찾기 -C++ 1025번: 제곱수 찾기 (acmicpc.net) 1025번: 제곱수 찾기 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 이번 문제는 생각보다 불친절하다. 입력의 범위(n, m)라던가 출력의 범위 등 구체적으로 정해진 것이 없다. 그래서 어쩔 수 없이 브루트 포스를 이용했는데 그것 마저도 범위가 주어지지 않으니 자료형에서 불편함이 있었다. 문제 자체도 불친절해서 문제에 대한 설명도 같이 하겠다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제 설명 문제 설명이 지문에 굉장히.. 더보기
[백준알고리즘] 1024번: 수열의 합 -C++ [백준알고리즘] 1024번: 수열의 합 -C++ 1024번: 수열의 합 (acmicpc.net) 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 10억 이하의 자연수 N과 100 이하의 자연수 L이 주어졌을 때, 수열의 합이 N이면서 길이가 100 이하인 수열을 찾는 문제다. 이번 문제의 경우 쉽게 접근할 수 있었으나, 예상치 못한 곳에서 오버플로우가 발생해서 골치아팠다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제에 대한 접근법은 실제 여러 수를 직접 해보면서 알아냈다. 먼저, 홀수는 \(l = 2\)로 모두 찾아지기 때문에 이 경우를.. 더보기
[백준알고리즘] 1019번: 책 페이지 -C++ [백준알고리즘] 1019번: 책 페이지 -C++ 1019번: 책 페이지 (acmicpc.net) 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 어렵다..... 결국 풀이를 봤다.... 풀이 보고도 이해를 겨우 했다.... 다른 분들의 코드들도 모두 같길래, 아이디어를 가지고 비슷한 방식으로 이래저래 엄청 시도해봤는데 전혀 되는 게 없었다.. 다들 백준 님이 푸신 방법대로 풀었다.. 백준 님의 풀이는 링크의 강의자료를 보면 된다.. 결국 나도 일반적으로 다들 푼 방법으로 코드를 올린다.. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 백준님의 풀이는 문제를 \(A\)에서.. 더보기
[백준알고리즘] 11060번: 점프 점프 -C++ [백준알고리즘] 11060번: 점프 점프 -C++ 11060번: 점프 점프 (acmicpc.net) 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 동적 계획법 문제다. 그렇게 어렵게 풀지는 않았으나, 생각지도 못한 반례가 있었어서 살짝 시간을 썼다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 재환이가 이동할 수 있는 칸만큼 오른쪽으로 이동하면 된다. 처음에 이 문제에서 놓쳤던 반례는 1x1 크기의 미로에 갇힌 경우도 있을 수 있다는 것이다. 이 부분을 고치고 나니 문제를 해결할 수 있었다... 더보기
728x90

티스토리툴바