랄뚜기의 코딩일기

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 처음에는 dfs로 풀지 않고 반복문을 돌렸다. 열을 먼저 탐색하면서 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래를 방문할 수 있는지 없는지 확인하고 방문할 수 있다면 check표시를 해주고 check표시가 된 경우에만 탐색을 할 수 있도록 구현하였는데 틀렸다. 반례가 있는거 같은데 못찾겠어서 그냥 모든 열 마다 dfs를 돌렸다. dfs를 돌릴 때 한 번 방문한 점은 다시 방문할 필요가 없다는 것을 주의해야 한..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net mst를 구하는 문제이다. 나는 disjoint_set을 이용한 kruskal 알고리즘으로 풀었다. #include #include #include #include #include #include #include #include #include #include #define INF 1000000000 #define endl '\n' #define ll long long using namespace std; vector v; int N,M,ans=0; int parent[1001]; bo..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net bfs로 풀까 고민하였지만 아무리 봐도 dfs가 구현이 쉬울거 같아서 dfs로 구현하였다. 문제는 시간초과였는데 다행히 그래프의 크기도 작고, 중복되는 알파벳은 접근하지 못한다는 조건도 있어서 많은 경우의 수가 제거되어 제 시간 안에 돌아갔다. #include #include #include #include #include #include #include #include #include #..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 오늘도 어김없이 문제를 제대로 읽지 않아 시간을 버렸다. 답이 3 초과인 경우를 배제해줬어야 했는데... 잘 읽어야겠다 ㅋㅋ 답이 3 초과인 경우를 배제해줬더니 시간초과가 떴다. 재귀를 돌 때 중복되는 경우가 발생하여 idx를 인자로 줘서 경우의 수를 줄여주었다. #include #include #include #include #include #include #include #include #i..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 저번 학기 알고리즘 설계 분석에서 배운 행렬 곱의 최소화 문제와 같은 알고리즘이다. 막상 수업시간에 이해를 하지 못했는데 이번에 다시 문제를 보면서 제대로 이해했다. 이 문제를 풀기 위해서는 위와 같은 방식으로 반복문을 돌 줄 알아야 한다. 위 처럼 반복문을 돌기 위한 코드는 다음과 같다. for(int j=1;j>K; for(int i=1;i>K_[i]; sum_[i]=sum_[i-1]..

https://www.acmicpc.net/status?user_id=yhkim8917&problem_id=2109&from_mine=1 채점 현황 www.acmicpc.net 옛날에 무작정 그리디로 풀었는데 엄청 틀리고 반례는 알게 되었지만 해결하지 못한 문제이다. 저번 학기에 알고리즘 설계와 분석 시간에 해당 문제를 배워서 수월하게 풀 수 있었다. 알설분 시간에는 disjoint set을 구현하여 풀었지만 해당 문제는 d의 값이 최대 10000밖에 되지 않기 때문에 그냥 크기 10000짜리 배열을 선언하여 풀었다. 일단 p와 d값 벡터에 저장 후에 벡터를 p를 기준으로 내림차순 정렬을 한다. 그리고 벡터를 반복문을 돌면서 벡터의 d값에 최대한 가까운 j번째에 p값을 저장해주면 된다. #include ..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 사용가능한 메모리가 4MB라는 것을 주의해야 한다. 나는 평소 dp처럼 모든 값을 받고 연산하는 것이 아니라 메모리를 줄이기 위해 값을 받을 때마다 연산하도록 구현하였다. max_배열과 min_배열을 이용하였는데 max_에는 현재까지 내려가는 비용의 최댓값을, min_배열에는 현재까지 내려가는 비용의 최솟값을 저장해 주었다. #include #include #include #include #include #in..

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 처음에는 그냥 타자의 순서를 정하는 게 메인인 문제인 줄 알았는데, 그건 기본이고 야구의 득점 시스템을 구현하는 것이 메인이었다. 타자 순서는 그냥 재귀와 반복문을 통해서 구현하였다. 야구의 득점 시스템은 크기가 3인 base라는 bool 순열을 이용하여 base에 사람이 있는지 없는지를 나타내 구현하였다. 안타를 쳤을 경우를 구현하는 것이 어려웠다. 수학적으로 간단히 구현이 가능할 줄 알았는데 경우의..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 책을 옮길 때 책이 0에 위치하므로, 양수와 음수 중 한 부분을 끝내고 다음에 다른 부분을 끝내는 것이 효율적이기 때문에 책의 위치를 양수부분과 음수 부분으로 나누어서 저장하였다. 양수 부분이든 음수 부분이든 그 절댓값(거리)이 가장 큰 곳을 방문할 때가 M권의 책 중 가장 마지막 책을 옮길 때여야지 이동거리를 최소화 할 수 있다. 따라서 처음에는 M권의 책을 모두 들고가는 것이 아니라 해당 부분(양수..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 처음 이 문제를 풀 때, priority queue를 이용하여 풀었는데 시간초과가 떴다. 이 문제는 삽입과 삭제가 여러 번 일어나는 문제인데, priority queue를 이용하면 삽입, 삭제가 일어날 때마다 O(logN)의 시간이 필요하게 된다. 잘 생각해보면 처음 문제에서 값을 주어질 때를 제외하고는 반복문이 돌 때 배열에 값들이 작은 값에서 큰 값으로 입력된다. 따라서 처음에..