DOTY

코딩테스트 연습 - N으로 표현 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr SET 활용이 미숙해서 헤맴 + 아이디어가 떠오르지 않음 이었다.... #include using namespace std; int DP[9]; int solution(int N, int number) { int answer = -1; fill_n(DP, 9, 0); set DP[9]; set::iterator iter_find; set::iterator iter_begin; set::iterator iter_end; i..

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 어렵지 않았는데 왤케 꼬였었는지....ㅜㅜ #include using namespace std; string solution(string number, int k) { string answer = ""; int answer_size = number.length() - k; int start = 0; int big = 0; for(int i = 0; i < answer_size; i++) { for(int j = star..

18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net BFS였는데 왜이리 안풀리지 했는데 잔오류가 너무 많았었다 #include using namespace std; int city[300001]; int check[300001]; int main(void) { int N, M, K, X; cin >> N >> M >> K >> X; fill_n(check, 300001, 0); f..

코딩테스트 연습 - 최소직사각형 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include using namespace std; int solution(vector sizes) { int answer = 0; int max_w = 0; int max_h = 0; for(int i = 0; i < sizes.size(); i++) { if(sizes[i][0] < sizes[i][1]) { int temp = sizes[i][0]; sizes[i][0] = sizes[i][1]; sizes[i][..

1504번: 특정한 최단 경로 (acmicpc.net) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 시간 초과나 생각하지 않은 예외가 있어 틀릴줄 알았던 문제 #include using namespace std; int vertex_1[801]; // v1먼저 가는 경우 int vertex_2[801]; // v2먼저 가는 경우 int dij[801]; // 0. DIJ 구현 (3.2) // 1. 1에서 V1 또는 V2로 가는 길 찾기 // 2. V1또는 V2에..

2468번: 안전 영역 (acmicpc.net) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 괜히 넘겨짚어서 이런이런... #include using namespace std; int pos_x[4] = {0, 1, 0, -1}; int pos_y[4] = {1, 0, -1, 0}; int building[100][100]; int check[100][100]; void dfs(int x, int y, int rain, int N) { check[x][y] = 1; for(int i = 0; i < 4; i++)..

2477번: 참외밭 (acmicpc.net) 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 머리로는 대충 떠오르는데 예외 처리 하는데 하나씩 놓치는거 보면 머리가 안굴러가는 것 같기도..ㅠㅠ #include using namespace std; int main(void) { int K; cin >> K; pair way_check[6]; int way, length; int max_H = 0; int max_V = 0; int answer = 0; for(int i = 0; i < 6; i++) { cin..

코딩테스트 연습 - 등굣길 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀다가 김 빠진 문제. #include using namespace std; int solution(int m, int n, vector puddles) { int answer = 0; int map[101][101] = {0, }; for(int i = 0; i < puddles.size(); i++) { map[puddles[i][1]][puddles[i][0]] = -1; } for(int i = 1; i

10830번: 행렬 제곱 (acmicpc.net) 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 지옥 같았던 문제..... #include using namespace std; vector temp_power(vector &tempA, vector &tempB, int N) { vector power_temp(5, vector(5, 0)); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { int temp = 0; for(int k = 0; k < N; k++) { te..

A^2 = A * A 인 것은 알고 있다. A^4 = A * A * A * A 도 알고 있다. A^8 = A * A * A * A * A * A * A * A 인것도 당연하다. 그러나 이런 방법으로 알고리즘을 짠다면 시간이 더욱 걸릴 것이다. 그렇기에 연산을 줄여야 한다. A^4 = (A^2)^2 처럼 표현하여 연산을 3번에서 2번으로 줄일 수 있다. A^8 = ((A^2)^2)^2 또한 연산을 7번에서 3번으로 줄일 수 있다. 이 방법을 사용한다면 시간이 확 줄어들 것이다. 만약 A^6 과 같은 경우에는 어떻게 할까? A^6 = A * (A^2)^2 처럼 쓸 수 있을 것이다. 지수가 홀수가 되버리면 따로 A를 빼주는 방법이다. 기존의 방법은 O(n)의 시간복잡도를 가졌다면 최적화를 한 경우에는 O(lo..