⭐ 코딩테스트
[백준 7562번 C/C++] 나이트의 이동
[백준 7562번 C/C++] 나이트의 이동
2023.09.01[백준 7562번 C/C++] 나이트의 이동 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 해결전략 너비우선 탐색, BFS 코드 #include #include #include #include // 메모리를 설정하는 함수들을 사용하기 위한 라이브러리 (예: memset) using namespace std; int t, n; // t: 테스트 케이스의 수, n: 체스판 한 변의 길이 int c, d; // 도착 위치 (c,d) int ch[30..
[백준 1697번 C/C++] 숨바꼭질
[백준 1697번 C/C++] 숨바꼭질
2023.08.31[백준 1697번 C/C++] 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해결전략 너비우선탐색, BFS 코드 #include #include #include using namespace std; int n, k; //n: 수빈 현재 점, k: 동생 점 queue Q; // 첫 번째 원소는 위치, 두 번째 원소는 해당 위치에 도달하기까지 걸린 시간 vector ch; //해당 위치를 방문했는지 여부를 체크..
[프로그래머스 C++] 멀리 뛰기
[프로그래머스 C++] 멀리 뛰기
2023.08.30[프로그래머스 C++] 멀리 뛰기 https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 동적계획법 Dynamic Programming, DP 코드 #include using namespace std; long long solution(int n) { long long answer = 0; if (n == 1) return 1; if (n == 2) return 2; vector dp(n+1); dp[0] = 0; dp[1] = 1; dp[2..
[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2
[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2
2023.08.29[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해결 전략 최대 증가길이 수열, 이분 탐색 Longest Increasing Subsequence, LIS 처음 시도한 코드 - 시간 초과 #include #include using namespace std; int n, result; vector v, LIS; int main() { ios::sync_with_stdio(false)..
[프로그래머스 C++] 예상 대진표
[프로그래머스 C++] 예상 대진표
2023.08.28[프로그래머스 C++] 예상 대진표 https://school.programmers.co.kr/learn/courses/30/lessons/12985 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 토너먼트 Tournament 브루트포스 Brute Force 코드 #include using namespace std; int solution(int n, int a, int b) { int answer = 0; while(a != b) { a = (a + 1) / 2; b = (b + 1) / 2; answer++; } return answer; } ..
[프로그래머스 C++] N개의 최소공배수
[프로그래머스 C++] N개의 최소공배수
2023.08.27[프로그래머스 C++] N개의 최소공배수 https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 최소공배수 코드 #include #include #include using namespace std; int solution(vector arr) { int answer = *max_element(arr.begin(), arr.end()) - 1; while (true) { answer++; for (int i = 0; i ..
[프로그래머스 C++] 올바른 괄호
[프로그래머스 C++] 올바른 괄호
2023.08.26[프로그래머스 C++] 올바른 괄호 https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 괄호 누적 코드 #include #include using namespace std; bool solution(string s) { bool answer = true; int cnt = 0; for (const auto& i : s) { if (i == '(') cnt++; else if (i == ')') cnt--; if (cnt < 0) retur..
[프로그래머스 C++] 점프와 순간 이동
[프로그래머스 C++] 점프와 순간 이동
2023.08.24[프로그래머스 C++] 점프와 순간 이동 https://school.programmers.co.kr/learn/courses/30/lessons/12980 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 홀수, 짝수 코드 #include using namespace std; int solution(int n) { int ans = 0; // 문제풀이 Tip // 점프, 순간이동의 순서를 고려하지 않아도 된다.(이 부분을 생각하기 힘들었다) // 도착위치에서 거꾸로 계산해 나간다. // 순간이동은 x2이기 때문에 /2로 되돌아간다고 생각한다. // ..
[프로그래머스 C++] 구명보트
[프로그래머스 C++] 구명보트
2023.08.23[프로그래머스 C++] 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결방법 탐욕법. 탐욕 알고리즘 (Greedy Algorithm) 투 포인터 (Two Pointer) 처음 시도한 코드 - 시간 초과 및 몇 개의 테스트 케이스 실패 #include #include #include using namespace std; int solution(vector people, int limit) { int answer = 0; sort(pe..
[프로그래머스 C++] 카펫
[프로그래머스 C++] 카펫
2023.08.22[프로그래머스 C++] 카펫 https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 완전 탐색 코드 #include #include #include using namespace std; vector solution(int brown, int yellow) { vector answer; int total = brown + yellow; int row = 0, column = 0, dif = total; for (int i=1; i abs(tem..
[프로그래머스 C++] 짝지어 제거하기
[프로그래머스 C++] 짝지어 제거하기
2023.08.21[프로그래머스 C++] 짝지어 제거하기 https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 문자열 첫 풀이 - 실행 통과, 효율성 테스트 시간 초과 #include #include using namespace std; int solution(string s) { int answer = -1; string temp; while (!s.empty()) { temp.clear(); //연속된 문자를 찾은 다음 뺀다 for (int i = 0; ..
[백준 2580번 C/C++] 스도쿠
[백준 2580번 C/C++] 스도쿠
2023.08.20[백준 2580번 C/C++] 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 해결전략 재귀 백트랙킹 Backtracking DFS 코드 #include #include using namespace std; vector v(9, vector(9)); // 현재 위치 (y, x)에 newNum을 놓았을 때 유효한지 행, 열, 3x3 작은 사각형을 검사하는 함수 bool isSafe(int y, int x, int newNum) { // 행..