Problem Solving 썸네일형 리스트형 BOJ 11559 - Puyo Puyo 문제 링크(Link)https://www.acmicpc.net/problem/11559 문제 해결(Solution) 1. 기본적인 BFS or DFS와 구현을 물어보는 문제. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 몇 번 블럭이 삭제되는 지를 물어보는 문제가 아니고 몇 번 연쇄되는 지를 물어보는 문제임을 숙지해야한다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2174 - 로봇 시뮬레이션 문제 링크(Link)https://www.acmicpc.net/problem/2174 문제 해결(Solution) 1. 기본적인 구현 가능 여부를 물어보는 문제. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. iteration 과정에서 갱신시켜주는 코드를 잊으면 안된다. 2. IT 기업 입사 시험에서(코딩테스트를 요구하는 기업) 기본적으로 요구하는 문제 수준이다. 반드시 풀어봐야한다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1074 - Z 문제 링크(Link)https://www.acmicpc.net/problem/1074 문제 해결(Solution) 1. 기본적인 분할 정복(Divide & Conquer)에 대해 물어보는 질문이다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 재귀(Recursive)를 사용하는 방법에 대해서 익숙해지는 연습문제다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 12849 - 본대 산책 문제 링크(Link)https://www.acmicpc.net/problem/12849 문제 해결 (Solution) 1. dp[i][j] = i 건물에서 j분 일 때의 경우의 수. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 출발 지점과 도착 지점 모두 "정보과학관"이다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 6549 - 히스토그램에서 가장 큰 직사각형 문제 링크(Link)https://www.acmicpc.net/problem/6549 문제 해결 (Solution) 1. 여러가지 풀이 방법이 있지만, 분할 정복(divide & conquer)과 구간 트리(segment tree)를 이용해서 문제를 해결. 2. 가장 큰 직사각형은 일정한 구간 내에서 가장 낮은 높이에 의해 결정된다. 3. tree[node] = 일정한 구간 (i, j)에서의 가장 낮은 높이의 인덱스. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 2로 나누고 곱하는 과정을 쉬프트 연산을 이용하면 조금 더 빠르게 해결할 수 있다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1761 - 정점들의 거리 문제 링크(Link)https://www.acmicpc.net/problem/1761 문제 해결 (Solution) 1. 문제에서 주어지는 그래프가 트리(Tree)임을 알고있다. 2. 트리에서 두 정점의 거리를 일반적인 방법으로 구하기 위해선 시간복잡도 O(N)이 소요된다. 쿼리의 개수를 고려하면 전체 시간복잡도는 O(NM)이 소요된다. 즉, 400,000,000(4억) 이므로 시간 초과에서 자유로울 수 없다. 3. dp를 이용한 LCA(최소 공통 조상) 알고리즘을 이용하면 O(logN)만에 두 정점의 거리를 구할 수 있다.(트리에서만...) 4. dp[i][j] = 정점 i에서의 2^j 번째 조상. 5. dist (dist[i] = 루트에서 부터 정점 i 까지의 거리) 라는 배열을 활용해서 두 정점사이.. 더보기 BOJ 5721 - 사탕 줍기 대회 문제 링크(Link)https://www.acmicpc.net/problem/5721 문제 해결 (Solution) 1. i번 째 행은 i+2행과는 아무 상관이 없다. i행의 열 중에서 서로 인접하지만 않으면 된다. 2. 1의 조건을 만족시키는 DP table을 생각해보면, 행에 대한 DP와 열에 대한 DP를 따로 만들어 해결하는 게 편함. 3. dp1[i] = i행에서의 최대값. dp2[j] = i행에서 열들을 선택했을 때의 가장 큰 값. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 처음엔 행과 열을 따로 생각할 수 있다는 생각을 하기 어렵다. 이런 유형이 있다는 것을 알아야한다. 2. 행과 열의 크기가 주어지지 않으므로, 그냥 1차원 배열로 생각하고 인덱스를 잘 다.. 더보기 BOJ 11578 - 팀원 모집 문제 링크https://www.acmicpc.net/problem/11578 문제 해결 1. N(사람의 수)와 M(문제의 수)가 최대 10이므로 비트마스크 DP를 사용해서 문제 해결. 2. dp[a][b] = a만큼의 사람이 b만큼 문제를 풀었을 때의 최소 사람. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2411 - 아이템 먹기 문제 링크https://www.acmicpc.net/problem/2411 문제 해결 1. 아이템을 모두 먹고 (1, 1)에서 (N, M)까지 이동하는 경우의 수를 구하는 문제. DP로 문제 해결. 2. dp[i][j][k] = (i-1, j-1)에서 k개의 아이템을 가지고 있을 때, 위의 1번을 만족하는 경우의 수. 주의할 점 || 생각해볼 점 1. 위치를 나타낼 때, 왼쪽 아래를 (1, 1)로 지정한다. 행을 뒤집어서 생각하면 수월하게 문제를 해결할 수 있다. 이 때, 움직일 수 있는 방향이 {오른쪽, 위} 에서 {오른쪽, 아래}로 바뀐다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 14729 - 칠무해 문제 링크https://www.acmicpc.net/problem/14729 문제 해결 1. 7개까지 vector로 입력 받아서 정렬한다. 2. 그 이후에는 lower_bound를 통해서 vector에 삽입할 지 결정한다. 3. 만약 iterator가 7보다 작다면(vector안에 들어오는 범위의 값이라면), 그 자리에 삽입하고 나머지는 뒤로 밀어낸다. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 2 3 4 5 ··· 9 다음