백준 문제풀이/etc
-
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
-
SWEA 4013 : [모의 SW 역량테스트] 특이한 자석백준 문제풀이/etc 2020. 6. 6. 16:29
문제 문제 풀어보기 풀이 먼저 4개의 톱니바퀴를 어떤방향으로 돌릴것인지 배열에 결정해준다. 배열을 돌면서 톱니바퀴를 돌려준다. 한비트 쉬프트하며 정답에 더해준다. 코드 #include #include #include #include #include using namespace std; //#define safe(x,y) x>=n || x v(4, vector(8, 0)); // 회전방향 결정 void go(vector& dir, int index) { int tmp = index; // 왼쪽 톱니바퀴 while (tmp--) { if (v[tmp][2] != v[tmp + 1][6]) { dir[tmp] = -dir[tmp + 1]; } else break; } tmp = index; // 오른쪽 톱니바..
-
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 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 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초 일때 박..
-
[C++] 카카오 코딩테스트 < 길 찾기 게임 > 문제풀이백준 문제풀이/etc 2020. 2. 9. 16:30
풀이 바로 본론으로 갑시다. 여기로 가시면 문제를 풀어보실 수 있습니다. 문제를 읽어보니 전무로 승진한 라이언이 사원들을 위해서 무언가 엄청 분석하고 있습니다. 하지만, 문제에서 요구하는 것은 간단합니다. 기본적인 트리를 구현하고 전위순회와 후위 순회를 수행해라. 트리 구현이 필수적인 경우엔 반드시 필요한 요소만을 구현할 필요가 있습니다. 기본적으로 자료구조에서 배운 트리는 Value 값만을 갖고 왼쪽 자식, 오른쪽 자식을 구별합니다. 저는 이 문제를 해결하기 위해 TreeNode 의 멤버 변수로 x, y, value 를 사용했습니다. y 는 상대적인 depth 를 의미합니다. x 는 크기를 비교하는 key 값이 됩니다. value는 실질적으로 답이 되는 값입니다. Tree 의 구현은 자료구조 개념과 같..
-
[재귀] BOJ 9095 : 1, 2, 3 더하기백준 문제풀이/etc 2019. 10. 14. 00:50
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 풀이 요즘 재귀 함수를 구현하는 법을 많이 연습 중입니다. 브루트 포스 문제들을 해결할 때 재귀 함수가 많은 도움이 되기 때문입니다. 이 문제는 재귀를 처음 접할 때 좋을 것..