boj
-
BOJ 10828 : 스택백준 문제풀이/etc 2020. 7. 9. 00:01
문제 문제 풀어보기 풀이 종종 면접 문제로 나오는 유형이네요. 면접에서는 보통 배열로 구현하라고 합니다. 그러면 벡터의 기본 함수를 사용 할 수 없어서 조금 복잡해지겠네요. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); vector v; int t; cin >> t; int x; string s; while (t--) { cin >> s; if (s == "push") cin >> x; if (s == "push") v.push_back(x); else if (s == "pop") { if (v.empty() == true) { cout
-
BOJ 1406 : 에디터백준 문제풀이/etc 2020. 6. 5. 12:31
문제 문제 풀어보기 풀이 사실 String 으로도 엄청 간단하게 구현이 가능합니다. 그런데 삽입,삭제가 너무 많아서 시간 초과가 나네요. 그래서 삽입,삭제가 유용한 리스트를 사용합니다. 대부분 벡터랑 비슷한데 리스트는 Iterator 를 기반으로 움직입니다. 그래서 삭제하는 과정에서 해당 cursor 위치의 노드를 삭제하면 그다음 Iterator 의 정보를 받아와야 합니다. cursor = list.erase(cursor) 이런 느낌이 되겠죠. erase 는 삭제 후 다음 노드의 Iterator를 반환해줍니다. 코드 #include #include #include #include #include using namespace std; #define safe(x,y) x>=8 || x> s >> n; lis..
-
BOJ 14225 : 부분수열의 합백준 문제풀이/BRUTE FORCE 2020. 6. 5. 00:30
문제 문제 풀어보기 풀이 완전 탐색을 하는데 중복되는 계산을 줄여주는 방법을 선택합시다. 재귀 문을 보면 그냥 포문 돌면서 하나씩 다 더해보는 겁니다. 그런데 저기서 st 인자를 없애고 모두 처음부터 본다면 어마어마한 중복이 발생합니다. 예를 들어 1, 2, 3, 4의 인자가 있다면 st 인자없이 모두 처음부터 탐색을 하는 경우 이러한 순서로 탐색할 겁니다. 하지만 현재 선택한 인덱스보다 작은 인덱스를 선택하는 경우는 모두 중복 수열이 됩니다. 따라서 st 인자를 사용해서 이전 인덱스는 넘어가게 해 줍시다. 코드 #include #include #include #include #include #include using namespace std; #define safe(x,y) x>=8 || x
-
BOJ 9663 : N-Queen백준 문제풀이/etc 2020. 5. 19. 12:50
문제 문제 풀어보기 풀이 퀸을 먼저 배치하고 가능한 경우인지 판단하는 알고리즘을 하면 시간 초과로 문제를 풀 수 없었습니다. 그래서 다른 분의 블로그를 참조해서 백트래킹을 사용했습니다. 간단히 설명하자면 퀸을 하나 넣고 퀸의 이동반경을 모두 덱에 넣습니다. 퀸이 들어갈수 있는 곳에 넣으면서 계속 덱에 넣다 보면 퀸의 수가 N 개 이면서 덱의 사이즈가 N * N 이 되는 경우가 생깁니다. 바로 이경우가 퀸을 N 개 위치시킨 경우가 됩니다. 코드 #include #include #include #define safe(x,y) x>=0&&x=0&&y < n using namespace std; int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,-1,..
-
BOJ 13023 : ABCDE백준 문제풀이/GRAPH 2020. 5. 15. 17:59
문제 문제 풀어보기 풀이 문제를 이해하는데 좀 오래 걸렸네요... 이 문제는 A -> B -> C -> D 처럼 친구의 친구의 꼬리를 4번 무는 경우를 찾는 겁니다. 그래서 DFS 를 사용해서 깊이가 4가 되는 경우를 찾으면 됩니다. 코드 #include #include #define max 2000 using namespace std; bool check[max + 1]; vector v[max + 1]; // max+1 개의 벡터 생성 int n, m; void dfs(int st, int index) { check[st] = true; // 깊이가 4인경우 종료 if (index == 4) { cout n >> m; for (int i = 0; i >..
-
BOJ 11727 : 2xn 타일링 2백준 문제풀이/Dynamic Programming 2020. 5. 15. 17:51
문제 문제 풀어보기 풀이 이거 하나만 확인하세요 !! 경우의 수를 계산하는 모든 과정에서 모듈러 연산을 하셨나요 ? ㅎㅎ 코드 #include #include using namespace std; int d[1001][3]; #define mod 10007 int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; d[1][1] = 1; d[2][0] = d[2][1] = d[2][2] = 1; for (int i = 3; i
-
BOJ 17140 : 이차원 배열과 연산백준 문제풀이/etc 2020. 5. 10. 22:17
문제 문제 풀어보기 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 저는 R 연산을 구현하고 C 연산에 복붙하고 행과 열만 바꿔서 풀었습니다. 처음엔 계산된 값을 어떻게 삽입을 할지 고민을 많이 했는데, 그냥 하드코딩으로 집어 넣어줘도 시간은 초과되지 않았습니다. 코드 #include #include #include #include #include #include using namespace std; int n = 3; int m = 3; vector arr(105, vect..
-
BOJ 17143 : 낚시왕백준 문제풀이/etc 2020. 5. 4. 18:28
문제 문제 풀어보기 풀이 최근에 출제되는 삼성 기출문제는 거의 80% 가 시뮬레이션 문제입니다. 시뮬레이션은 순차적으로 진행되는 프로그램을 그대~로 구현하는 문제입니다. 이러한 문제들은 복잡한 알고리즘을 요구하지 않기 때문에 빠른 이해력과 정확한 설계만 한다면 대부분 푸실 수 있는 문제들입니다. 하지만 시뮬레이션에선 항상 시간 초과의 늪에 빠지게 됩니다. 이문제도 그랬는데요. 그러한 시간초과를 해결하는 방법이 바로 모듈러 연산입니다. 예를 들어 봅시다. 철이는 1초마다 숫자를 하나씩 증가하면서 말하고 있는데, 3의 배수일때마다 박수를 친다고 합니다. 그럼 1억초 이후에 철이는 몇 번 박수를 칠까요? 라는 문제를 풀때 저희는 1초 일때 박수를 치는지 안치는지 2초 일때 박수를 치는지 안치는지 3초 일때 박..