본문 바로가기
728x90

Algorithm

[백준알고리즘] 1039번: 교환 -C++ [백준알고리즘] 1039번: 교환 -C++ 1039번: 교환 (acmicpc.net) 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 굉장히 어려웠다. 풀고 제출을 했었는데 틀렸다고 나왔고 해당 문제가 뭔지 알았는데, 고치지 못했다. 결국 다른 분의 블로그를 참고해서 문제를 푸는 법을 알았고, 이해한 내용을 바탕으로 다른 내용으로 풀고 싶었다. 아래 블로그의 얍문님의 포스팅을 보고 BFS로 푸는 방법에 대해서 알게 됐다. [ 백준 1039 ] 교환 (C++) :: 얍문's Coding World.. (tistory.com) [ 백준 1039 ] 교환 (C++) 백준의 교환(103.. 더보기
[백준알고리즘] 1890번: 점프 -C++ [백준알고리즘] 1890번: 점프 -C++ 1890번: 점프 (acmicpc.net) 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 누가 봐도 동적 계획법으로 풀어야 할 것 같은 문제다. 그래서 가능한 모든 경우를 찾는데 재귀를 사용했고, DFS를 사용했다. 사실 이전에 Python으로 풀었던 문제였다. 물론 기억은 나질 않았지만.. 아래 링크가 이전에 풀었던 코드다. [백준알고리즘] 1890번: 점프 -Python (tistory.com) [백준알고리즘] 1890번: 점프 -Python [백준알.. 더보기
[백준알고리즘] 1038번: 감소하는 수 -C++ [백준알고리즘] 1038번: 감소하는 수 -C++ 1038번: 감소하는 수 (acmicpc.net) 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쉬운 듯 안 쉬운 듯한 문제.. DFS로 푸시는 분들이 많으신 것 같고 풀이가 많으신 것 같지만, 나는 DP로 풀었다. DP로 푸는 방법 중에서도 벡터를 두개만 사용해서 문제를 풀었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 처음 문제를 접했을 때에는 숫자를 1씩 증가시키면서.. 그러면서 각각의 수가 감소하는 수인지 확인하는 방법으로 코.. 더보기
[백준알고리즘] 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)라던가 출력의 범위 등 구체적으로 정해진 것이 없다. 그래서 어쩔 수 없이 브루트 포스를 이용했는데 그것 마저도 범위가 주어지지 않으니 자료형에서 불편함이 있었다. 문제 자체도 불친절해서 문제에 대한 설명도 같이 하겠다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제 설명 문제 설명이 지문에 굉장히.. 더보기
728x90

티스토리툴바