DIBRARY

🤖Algorithm 검색 결과

해당 글 125건

[BOJ] 11048번 | 이동하기 (C++)

🔗문제 보러가기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🧑🏻‍💻풀이 과정 DP(Dynamic Programming)로 풀 수 있습니다. 알고리즘은 다음과 같습니다. 1. (0, 0)부터 시작하여 0행과 0열에 대해 누적합을 저장해 나가며, 초기화를 해줍니다. 예제 입력 1번을 예로 들면 다음과 같이 합니다. // 원본 입력 데이터 1 2 3 4 0 0 0 5 9 8 7 6 // 누적합 적용 후 1 3(2+1) 6(3+3) 10(6+4) 1 (0+1) 0 0 5 10(9+1) 8 7 6 2..

🤖Algorithm/BOJ 2023. 8. 23. 19:11

[BOJ] 1003번 | 피보나치 함수 (C++)

🔗문제 보러가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🧑🏻‍💻풀이 과정 피보나치 함수를 호출했을 때, \( n = 0 \) 또는 \( n = 1 \)일 때의 0과 1의 출력 개수를 세야 합니다. (즉, 위 문제에서 주어진 소스 코드에서 if(n == 0)과 if (n==1)에 해당할 경우) 1. Top-down 방식으로 DP 배열을 통해 중복 계산 최소화 방법 시도 (실패) 피보나치 함수를 재귀로 구현했을 때의 문제점이 바로 중복 계산입니다. 중복 계산이 이루어지기에 시간이 터무니없이 많이 걸리는 것이고, 이것을 개선하기 위해 DP 배열을 사용하여 이미 계산된 N이라면 계산하지 않는 것이죠. 하..

🤖Algorithm/BOJ 2023. 8. 21. 18:06

[BOJ] 11726번 | 2xn 타일링 (C++)

🔗문제 보러가기 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🧑🏻‍💻풀이 과정 \( n = 1\)부터 하나씩 그려보면, 피보나치 수열의 규칙이 생깁니다. \( n = 1\)과 \( n = 2\)를 베이스로 삼아, \( n = 3\)부터는 \( n - 2\)와 \( n - 1\)을 가지고 조합해 나가는 방식이다 보니, 피보나치 수열과 같은 규칙이 생기는 것 같네요. ✏️ 소스 코드 및 결과 #include #include using namespace std; void SetFastIO() { ios::sync_with_stdio(..

🤖Algorithm/BOJ 2023. 8. 21. 16:48

[Programmers] Lv2. 단체사진 찍기 | C++

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 저는 DFS를 이용하여 8명의 캐릭터들의 순열마다 조건식을 검사하였습니다. 한 가지 실수했던 게, 조건식의 다섯번째 글자에 해당하는 간격은 두 캐릭터 사이의 캐릭터 숫자라는 걸 까먹었습니다. 저처럼 인덱스 탐색 방식으로 할 시, 간격에다가 -1을 해주는 추가 작업이 필요합니다. int distance = abs(sourceIndex - targetIndex) - 1; ✏️소스 코드 및 결과 #include #include #include using namespace std; c..

🤖Algorithm/Programmers 2023. 8. 12. 12:43

[Programmers] Lv2. 카카오프렌즈 컬러링북 | C++

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 BFS로 풀 수 있는 쉬운 문제입니다. 색칠되지 않은 영역은 지나간다. 색칠되어 있고, 방문한 적이 없는 픽셀이라면, 해당 픽셀을 기준으로 상하좌우 BFS 탐색을 시작한다. BFS 탐색이 끝났다면 영역 개수를 1개 늘려주고, 이전 영역 크기와 비교하여 더 큰 값으로 갱신한다. ✏️소스 코드 및 결과 #include #include using namespace std; const int DIRECTION_COUNT = 4; const int rowDirections[DIRECTI..

🤖Algorithm/Programmers 2023. 7. 13. 20:07

[Programmers] Lv2. 순위 검색 | C++

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 정말 정말 정말 정말 정말 짜증났던 문제입니다. C++은 왜 Python처럼 문자열 라이브러리가 강력하지 않은 걸까요... 문제를 보자마자 생각났던 건 데이터베이스 수업 시간 때 배웠던 B+ 트리였지만, 코딩 테스트 칠 때 언제 그걸 다 구현하겠습니까... 노가다적인(브루트 포스) 방법 말고 다른 방법이 없나 고민하다가 없어서 다른 사람들 풀이를 약간만 봤는데, 거의 다 브루트 포스로 쿼리를 추가해 놓는 방법을 쓰셨더라구요. 가령 예를 들어, "java backend junio..

🤖Algorithm/Programmers 2023. 7. 10. 15:35