DOTY

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS로 풀었다. 잔실수가 너무 많았었던 문제 #include using namespace std; int pos_x[4] = {0, 1, 0, -1}; int pos_y[4] = {1, 0, -1, 0}; int check[101][101] = {0,}; int solution(vector maps) { int n = maps.size(); int m = maps[0].size(); int answer = 0; i..

10872번: 팩토리얼 (acmicpc.net) 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 재귀 함수 어려워서 처음부터 공부하려고 푼 문제 #include using namespace std; int doFactorial(int N) { if(N > 1) { N *= doFactorial(N-1); } return N; } int main(void) { int N; cin >> N; if(N == 0) { cout

1238번: 파티 (acmicpc.net) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 역시나 다익스트라로 풀은 문제긴 한데 메모리나 시간초과 날줄 알았는데 맞춘 문제.. #include using namespace std; int answer[1001]; int vertex[1001]; int dij[1001]; int rev_dij[1001]; void do_dij(int N, int X, vector dij) { fill_n(vertex, 1001, 100001); pr..

13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 뻘짓 하다가 시간만 쓴 문제 #include using namespace std; int cost[100001]; int dij[100001]; int main(void) { fill_n(cost, 100001, 100002); fill_n(dij, 100001, 2); vector dij(100001); int N, K; cin >> N >> K; dij[0].push_back..

1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 사용한 문제. 계속 틀려서 고민하다가 어이없게 맞춘 문제인데 어떤 차이가 있는지 모르겠다. #include using namespace std; int cost[1001]; int dij[1001]; int main(void) { fill_n(cost, 1001, 100000001); fill_n(dij, 1001, 100001); // dij : arrive po..

1753번: 최단경로 (acmicpc.net) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘을 사용했다. #include using namespace std; int vertex[20001]; // 정점으로 부터의 길이 int dij[20001]; int INF = 999999; int main(void) { fill_n(dij, 20001, 11); fill_n(vertex, 20001, 999999); vector dij(20001); int V,..

BFS의 응용버전 (BFS와 다이나믹이 합친 느낌이랄까..) 최단 거리를 찾는 알고리즘이다. 하나의 정점에서 모든 점으로 가는 최단 경로로 못 가는 경우에는 무한대로 끝난다. 필기로 정리한 것 또 쓰기가.. ㅎㅎㅎㅎㅎㅎ

1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 초기화 하는 방법을 헷갈려서 헤맨 문제 #include using namespace std; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int check[51][51]; int cab[51][51]; void cabbage(int x, int y) { int pos_x = x; int pos_y = y; queue position; position.push(make_pair(..

1874번: 스택 수열 (acmicpc.net) 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2년 전에 풀었지만 왜인지 계속 시간 초과만 뜨던 문제. 생각보다 해결법은 간단했다. #include using namespace std; int main(void) { int num; int j = 0; int arr[100001] = {0, }; cin >> num; vector answer; stack s; for(int i =..

4949번: 균형잡힌 세상 (acmicpc.net) 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 작은 실수 하나 때문에 고민한 문제 방법은 여는 괄호는 스택에 넣고 닫는 괄호는 스택 top과 비교하여 괄호가 일치하면 pop 다르면 break. #include using namespace std; int main(void) { stack cover; while(1) { bool check = false; while(!cover.empty()) { cover.pop(); } string ..