⭐ 코딩테스트
[백준 13334번 C/C++] 철로
[백준 13334번 C/C++] 철로
2024.02.05[백준 13334번 C/C++] 철로 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 해결전략 정렬 set, multiset 우선순위 큐 priority_queue ※ 주의할 점 이 문제에서 set을 사용할거면 multiset을 사용해야 한다. set은 중복된 원소를 허용하지 않는다. 반면 첫 번째 코드에서는 multiset을 허용한다. multiset을 사용하여 시작점이 같은 데이터도 모두 ..
[백준 14725번 C/C++] 개미굴
[백준 14725번 C/C++] 개미굴
2024.02.04[백준 14725번 C/C++] 개미굴 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 해결전략 Tree 트리 Trie 트라이 자료구조 정답 코드 #include #include #include #include using namespace std; int n; // 먹이의 정보 개수 int k; // 먹이 사슬의 길이 struct Node{ // 노드를 표현하는 구조체 private: map child; // 자식 노드를 가리..
[프로그래머스 C++] 미로 탈출
[프로그래머스 C++] 미로 탈출
2024.02.03[프로그래머스 C++] 미로 탈출 https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결 전략 너비우선탐색 BFS 레버(L)를 먼저 찾은 후에 탈출구(E)를 찾아야 한다. 레버(L)를 찾는 BFS 수행 주의할 점: 이 때 탈출구를 지나칠 수 있다. 탈출구를 지나도 밖에 나가 끝나지 않고 그냥 지나친 시간만 카운팅한다. 방문 체크 초기화 fill(ch.begin(), ch.end(), vector(c, 0)); 탈출구(E)를 찾는 BFS 수행 주..
[프로그래머스 C++] 테이블 해시 함수
[프로그래머스 C++] 테이블 해시 함수
2024.02.02[프로그래머스 C++] 테이블 해시 함수 https://school.programmers.co.kr/learn/courses/30/lessons/147354 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 정렬 누적 합계 비트 연산 정답 코드 #include #include #include #include using namespace std; // 행 번호, (문제에서 col로 주어진)특정 열의 값, 첫 번째 열의 값을 저장하는 구조체 struct Value { int rowNum; int colVal; int firstVal; // Value의 ..
[프로그래머스 C++] 거리두기 확인하기
[프로그래머스 C++] 거리두기 확인하기
2024.02.01[프로그래머스 C++] 거리두기 확인하기 https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 너비우선탐새 BFS 별 위치 확 정답 코드 #include #include #include #include using namespace std; int dirY[8] = { -1, 0, 1, 0, -1, -1, 1, 1 }; int dirX[8] = { 0, -1, 0, 1, -1, 1, -1, 1 }; vector solution(vector v..
[백준 16946번 C/C++] 벽 부수고 이동하기 4
[백준 16946번 C/C++] 벽 부수고 이동하기 4
2024.01.31[백준 16946번 C/C++] 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 해결전략 너비우선탐색 BFS 풀이전략 0 위치 한 곳에서 BFS를 실행한다. 인접한 0을 모두 방문하고 카운팅(cnt)하고 방문체크한다. // 빈 공간이고 방문하지 않았다면 if (v[ny][nx] == 0 && ch[ny][nx] == 0) { Q.push({ ny, nx }); ch[ny][nx] = 1; cnt++;..
[백준 17387번 C/C++] 선분 교차 2
[백준 17387번 C/C++] 선분 교차 2
2024.01.30[백준 17387번 C/C++] 선분 교차 2 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 해결전략 수학 기하학 선분 교차 판정 외적 Cross 행렬식 외적를 구할 때 사용하는 행렬식 int CCW(const Point& a, const Point& b, const Point& c) { // 행렬식을 사용해서 외적 구하기 long long result = (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x); if (res..
[백준 1025번 C/C++] 제곱수 찾기
[백준 1025번 C/C++] 제곱수 찾기
2024.01.30[백준 1025번 C/C++] 제곱수 찾기 해결전략 정답 코드 #include #include #include #include using namespace std; int n, m; int answer = -1; bool flag = false; int arr[10][10]; bool isSqureNum(int n) { int root = (int)sqrt(n); if (root * root == n) return true; return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; string tmp = ""; for (int i = 1; i > tmp; for (int j = 1; j
[백준 17404번 C/C++] RGB거리 2
[백준 17404번 C/C++] RGB거리 2
2024.01.26[백준 17404번 C/C++] RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 해결전략 동적계획법 Dynamic Programming (DP) 첫 번째 집을 각각 빨강, 초록, 파랑으로 칠하는 세 가지 경우를 각각 계산한다. 첫 번째 집을 특정 색으로 칠한 경우, 그 색을 제외한 다른 두 색의 비용은 계산할 수 없으므로 무한대(INF)로 설정한다. dp[1][0] = v[1].red; dp[1][1]..
[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다
[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다
2024.01.25[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다 https://www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 해결전략 수학 정렬 조합론 분할 정복을 이용한 거듭제곱 정답코드 #include #include #include using namespace std; int n; // 메뉴의 총 개수 vector v; vector two; const int MOD = 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; v.r..
[백준 1019번 C/C++] 책 페이지
[백준 1019번 C/C++] 책 페이지
2024.01.24[백준 1019번 C/C++] 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 해결전략 수학 일단 이번 문제는 답지를 봤다. 풀이를 생각해내기 힘들었다. 문제 풀이 방향은 start 숫자부터 end 숫자까지 등장한 0~9 숫자를 카운팅 하는 것이다. 정답코드 #include using namespace std; long long digit[10]; // 0부터 9까지 각 자릿수가 등장하는 횟수를 저장 // 주어진 숫자 n에서 각 자릿수가 얼마나 많이 등장하는지 계산하는 함수 void Cal(long ..
[백준 10942번 C/C++] 팰린드롬?
[백준 10942번 C/C++] 팰린드롬?
2024.01.23[백준 10942번 C/C++] 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 해결전략 동적계획법 Dynamic Programming (DP) 메모이제이션 Memoization 시도한 코드 - 시간초과 처음 시도한 코드 #include #include using namespace std; int n, m; vector v; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; v.resiz..