프로그래밍/문제풀이(boj)
1. 문제링크https://www.acmicpc.net/problem/10814 2. 문제해설이 문제는 n명의 사람이 주어지는데, 이 사람들을 먼저 나이순으로, 그리고 먼저 들어온 순으로 정렬 하는 문제이다.이 문제는 여러가지 방법으로 풀 수 있다. vector를 사용해 입력 순서대로 정리1. string을 받는 vector 배열에 나이에 해당하는 인덱스에 push_back을 해준다.2. 배열을 돌면서 출력해준다.ps) vector말고 FIFO인 자료구조이면 뭐든 괜찮다. 핵심은 먼저 들어간 것이 먼저 나오는 데에 있다. 이 풀이의 시간복잡도는 O(N) 이다. count_sort를 이용한 풀이1. 입력받은 사람들의 나이를 cnt배열에 카운팅한다.2. cnt 배열의 누적합을 구한다.3. 각 배열의 누적합의..
1. 문제 링크https://www.acmicpc.net/problem/10828 2. 해설이 문제는 간단하게 Stack을 구현하는 문제이다.스택에 대한 설명은 http://compasstree934.tistory.com/7?category=676159 에 있다.스택에서 push, pop, size, empty, top 이 5가지 메소드들을 구현하는 문제이다. 필자는 두 가지 방법으로 풀었다. 하나는 배열을 이용한 풀이, 또 하나는 linked list를 이용한 풀이.둘의 차이와 장단점은 설명 링크에 적어놓았다. 배열을 사용해서 구현1. stack이라는 배열과 stack_size라는 정수 변수를 선언한다.2. 0-베이스를 사용할 것이므로 stack_size는 0으로 초기화한다.3. push는 stack_..
1. 문제 링크https://www.acmicpc.net/problem/9012 2. 해설이 문제는 여러가지 방법으로 풀이가 가능하다. stack을 사용할 수도 있고, 그냥 for문으로 문자열을 돌면서 개수를 세면서 확인이 가능하다.둘 다 O(N)만에 해결이 가능한 방법이다. stack을 사용한 풀이1. 입력받은 문자열을 전부 확인하면서 '(' 라면 stack에 push한다.2. ')' 라면 stack이 비어있는지 확인해서 비어있다면 올바르지 않다고 판단한다.3. 비어있지 않다면 stack의 top에 '(' 가 있는지 확인하고, 있다면 '('를 pop한다.4. 전부 확인 하고 stack이 비어있다면 올바른 괄호, 아니면 올바르지 않은 괄호임을 알 수 있다. 개수를 세면서 확인하는 풀이1. 입력받은 문자열..
1. 문제링크https://www.acmicpc.net/problem/7576 2.해설이 문제는 전형적인 BFS문제이다. 문제 풀이 순서는 이러하다.1. 시작점을 찾는다.2. BFS로 가능한 만큼 토마토를 다 익힌다.3. 다 익었는지 확인 하고 다 익었다면 구한 cnt를 ans에 대입하고 출력한다. 시간복잡도는 BFS의 시간복잡도인 O(VE) 이고 이 문제에서는 O(n^2) 이다. 3. 소스코드 #include #include #include using namespace std; #define MAXNUM 1010 struct point{ int x, y; }; bool isRipe(int n, int m, int tomato[][MAXNUM]); int main(){ int n, m, ans=-1, c..
