본문 바로가기

분류 전체보기

 (386)
[boj] 백준 9466 텀 프로젝트 (c++) - DFS [문제] https://www.acmicpc.net/problem/9466 [풀이] 사이클을 이룰 경우 해당 팀이 만들어진다. 사이클을 이뤄서 팀에 포함된 학생들의 수를 센 후 전체 학생 수에서 빼주면 된다. 여기서 사용된 isFinished 배열은 사이클을 이룰 경우 이미 방문한 정점도 다시 방문할 수 있기 때문에 다시는 방문할 필요가 없는 정점임을 표시해주기 위해 필요하다. (예제에서 4 -> 7 -> 6 -> 4 와 같이) 방문하지 않은 정점들에 대해서만 dfs를 돌려서 최적화해주어야 시간초과가 발생하지 않는다. [코드] #include #include #include #include #include #define INF 987654321 using namespace std; int t; bool ..
[boj] 백준 16235 나무 재테크 (c++) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [풀이] 단순 구현 문제. 다만 처음에 구조체를 사용해서 나무가 죽었는지 여부를 bool로 저장해두고 판단했을 때는 시간 초과가 났다. [코드] #include #include #include #include #define INF 987654321 using namespace std; int n, m, k; int A[11][11]; int land[11][11]; int..
[boj] 백준 2623 음악프로그램 (c++) - 위상정렬 [문제] https://www.acmicpc.net/problem/2623 [풀이] 단순한 위상정렬 문제. [코드] #include #include #include #include #include #include #define INF 987654321 using namespace std; int n, m; vector node[1001]; int in[1001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //위상정렬 cin >> n >> m; for(int i=0; i> cnt; for(int j=0; j> temp[j]; } for(int j=0; j
[boj] 백준 11779 최소비용 구하기 2 (c++) - 다익스트라 [문제] https://www.acmicpc.net/problem/11779 [풀이] 이전 최소비용 구하기 1 과 마찬가지로 다익스트라를 이용해서 푸는 문제이다. 여기에 추가된 것은 최소 경로를 출력하도록 하는 것인데 이를 위해 경로가 갱신될 때 path_arr[] 배열에 어느 도시에서 오는 지를 저장하도록 하였다. + 주의할 점. 배열이나 벡터 초기화 시 아무 생각없이 memset을 사용했었는데 memset의 경우 1바이트 단위로 초기화를 한다고 한다. 따라서 char이나 bool 자료형에 대해 주로 사용하고 int의 경우 0으로만 초기화할 때 사용해야 한다. fill 을 이용하면 데이터형에 관계없이 사용 가능하다. [코드] #include #include #include #include #includ..
[boj] 백준 1516 게임 개발 (c++) - 위상정렬 [문제] https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net [풀이] 건물을 짓는 순서가 있으므로 위상정렬 문제이다. 우선적으로 지어야 하는 건물이 있는 경우 그 중 가장 오래 걸리는 시간 + 현재 건물을 짓는 시간으로 계속 갱신해주어야 한다. [코드] #include #include #include #include #include #define INF 987654321 using namespace std; int n; int durat..
[boj] 백준 2638 치즈 (c++) - BFS [문제] https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [풀이] 치즈는 내부 공기에 의해서는 녹지 않으므로 외부 공기와 내부 공기를 구분해주어야 한다. 문제 조건에서 가장 자리에는 치즈가 놓이지 않는다고 했으므로 (0,0)부터 탐색을 진행하면 외부 공기에 대해서만 치즈에 닿는 면을 증가시켜줄 수 있다. 벽이면 계속 탐색을 진행, 치즈면 닿는 면을 증가시켜준 후, 탐색이 끝나면 녹을 수 있는 치즈를 녹인다. 그 후 다시 bfs를 돌..
[boj] 백준 7579 앱 (c++) - dp [문제] https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net [풀이] dp 문제. 이 문제를 푸는데 헤매었던 부분이 2가지 있었다. 먼저 처음 dp 배열을 메모리 기준으로 만들어서 풀려고 했다. dp[i] = i 바이트의 메모리를 확보하기 위해 필요한 최소 비용으로 둔 후 dp[m] 에 해당하는 값을 출력하고자 했다. 예제는 잘 나왔으나 간과했던 부분은 딱 m 바이트가 아니라 m 바이트 이상의 메모리를 확보하는 경우가 더 최소의 비용이 될 수 있다는 것이..
[boj] 백준 17070 파이프 옮기기 1 (c++) - DFS [문제] https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] DFS 문제로 가로, 세로, 대각선 이동 시 파이프 끝이 차지하는 좌표를 dr, dc 배열에 저장해서 이동을 시켜준다. 이때 추가적으로 고려해주어야 하는 상황은 다음과 같다. 1. 세로로 놓여져있으면 가로 방향으로, 가로로 놓여져있으면 세로 방향으로 이동할 수 없다. 따라서 dir을 추가적으로 전달해줘서 이와 같은 케이스를 막는다. 2. 아래 사진과 같이..

티스토리툴바