전체 글168 [백준] 2493번 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 이제는 방식을 외우긴 했는데 코드짜면서 깊게 생각하다보니 또 헷갈려서 포스팅한다. 언제쯤 익숙하게 외우려나... 휴... stack을 써야하는 이유 모든 탑에 대해서 높이를 입력받은 i번째의 탑을 기준으로 앞쪽으로 이동하며 더 높은 탑을 찾아도 되지만, O(N^2)의 시간복잡도를 가지게 된다. 하지만 이를 stack을 통해 구현할 경우, 탐색의 경우의 수를 비약적으로 줄여 시간에서 큰 이득을 볼 수 있다. 변.. 2021. 3. 17. [백준] 1629번 곱셈 www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 구현 자체는 어렵지 않은데 방식을 모르면 쉽게 풀 수 없는 문제 같다. 여러 번 풀면서 방식을 익혀놓으면 다른 문제 풀 때 사고에 도움이 될 것 같다. 알고리즘 방식 #include #include #include #include #include #include #include #include #include using namespace std; long long pow(long long a, long long b, long long c) { if (b == 1) return.. 2021. 3. 17. [백준] 9663번 N-Queen www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1793번 풀다가 세번째 풀어도 못푸는 나를 보고 자괴감에 빠져.... 오늘은 이걸로 포스팅하기로 했다. 내일 아침 자력으로 풀어내면 1793을 내일 포스팅하겠다. 변수 isused1, isused2, isused3 - x = i 일때, 각각 체스판의 가로영역, 대각선영역, 반대대각선영역의 사용 여부를 나타냄 cnt - 퀸의 개수 n - 입력 값 N 알고리즘 방식 백트래킹을 통해 구현했다. 간단히 설명하면 cur = x 좌표,.. 2021. 3. 16. [백준] 1463번 1로 만들기 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net BFS를 통해 구현했다. 처음에 1에서 n을 찾는 방식으로 구현했는데 n에서 1을 찾는 방식에 비해 메모리와 시간이 커서 고민을 많이했다. 결과론적으로 전자는 n 이상의 범위까지 탐색을 시도하지만 후자는 1로 수렴한다는 느낌인 것 같다. (곰곰히 생각해보면 곱하기와 나누기의 차이인 것 같다. 곱셈을 통한 BFS를 하면 q에 들어가는 데이터 하나하나 사이의 값들이 커져서 채워져 있는 board의 중복을 통한 소거의 빈도가 줄어 든다. 반대로 나눗셈을 통한 BFS는 q에 들어가는 데이터 하나하나 사이의 값들이 작아져 채워져 있는.. 2021. 3. 16. 3월 셋째주 3/16 화 백준 하나 풀어서 포스팅하고 자소서 마지막 마무리지어야겠다. 오늘은 오전에 1개 저녁에 1개 포스팅 해야겠다 3/17 수 BFS, 재귀 파트 다시 다 풀어보려고 한다. 시간이 조금 부족할 것 같기도 한데 해봐야겠다. 1799번은 오늘도 제대로 못해서 내일 아침에 다시풀고 포스팅하기로... //2206 - 느낌적으로 이해되긴하는데 직관적으로 이해가 안되서 포스팅을 임시저장 해놨다. 처음벽을 부수기 전까지 벽을 부쉈을때 사용하는 vis[x][y][1]배열에는 0만 있기 때문에 원점으로 다시 돌아가는 부분을 없애면 최적화 될 것 같아서 없앴는데 메모리와 시간에서 차이가 나지 않는다. 미미한 차이를 만들어서 그런건지 의미가 없는 건지 잘모르겠다. 3/18 목 요새 최적화에 신경쓰면서 짜기 시작했떠니.. 2021. 3. 16. [백준] 9466번 텀 프로젝트 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 방식이 어떻게 보면 꼼수일 수도 있는 것 같은데 이전과 비교하면 메모리와 시간을 굉장히 많이 단축해서 뿌듯해서 올려본다. 변수 배열 board - n개의 선택된 학생들의 번호가 저장 배열 vis - n명의 학생들에 대해 선택 여부 저장 변수 result - 결과값 (프로젝트 팀에 속하지 못한 학생들의 수) 큐 q - BFS에서 사이클을 확인하는 데 사용됨 알고리즘 방식 * 데이터를 입력받을 때 자기 자신을 가르.. 2021. 3. 13. 이전 1 ··· 24 25 26 27 28 다음
