랄뚜기의 코딩일기

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하..

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 ..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라..

https://www.acmicpc.net/problem/24542 24542번: 튜터-튜티 관계의 수 첫째 줄에 튜터-튜티 관계를 정하는 경우의 수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 퓨처테크아케데미(주)는 올해로 4년째 엘리트 알고리즘 SW교육-「헬로알고」라는 브랜드로 국내는 물론 해외 14개국 청소년들을 대상으로 SW교육을 실시하고 있는 교육회사입니다. 또한 중소벤처기업부와 한국교육학술정보원이 선정한 '2021비대면스타트업 교육회사', 동국대학교 'SW코딩역량강화캠프 교육회사' 선정 등 늘 새로운 것에 도전하는 젊은 열정의 에듀테크 회사이기도 합니다. 2022 국내외 온·오프라인 사업의 새로운 도전을 위해 SW교육 지도 및 컨텐츠 연구개발..

https://www.acmicpc.net/problem/24545 24545번: Y 첫째 줄에 트리의 정점 개수를 의미하는 정수 $N$이 주어진다. ($2 \leq N \leq 100\,000$) 둘째 줄부터 $N-1$개 줄에 걸쳐 트리를 이루는 간선의 정보를 나타내는 두 정수 $u$, $v$가 주어진다. 이는 $u$번 정 www.acmicpc.net 문제 Y-트리는 아래 조건을 만족하는 트리이다. 4개 이상의 정점과 인접한 정점은 없다. 인접한 정점의 개수가 3개인 정점은 정확히 하나만 존재한다. 인접한 정점이 하나뿐인 정점은 정확히 세 개 존재한다. Y-트리의 크기는 해당 Y-트리를 이루는 정점의 개수와 같다. 1, 2, … N까지의 번호가 하나씩 매겨진 정점 N개로 이루어진 트리가 주어진다. 주어..

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

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/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 전형적인 dfs 문제이다. 모든 점을 인자로 넣어 dfs를 돌면서 한칸 옮겨갈 때 마다 cnt에 1을 더해주고 cnt가 5일 경우를 찾으면 dfs를 멈췄다. #include #include #include using namespace std; int N,M; vector v[2001]; bool flag=false; bool check[2001]; void dfs(int now,int cnt){ if(flag) return; if(cnt==5){ flag=true; return; } check[now]..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제를 풀면서 bfs에 대해서 한번 더 배우게 된 것 같다. 알고리즘 1. 전체 반복문을 돌면서 영역에 포함되지 않은 0을 만난다면 bfs를 돌리며 color값을 입력한다. 2. bfs를 돌면서 방문한 0의 좌표를 저장하고 bfs가 끝났으면 해당 영역의 크기를 저장한 좌표에 저장해준다. 3. 다시 전체 반복문을 돌면서 1을 만날 경우 그 칸과 모두 인접한 0에 저장된 영역..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 처음에는 뚫고 지나온 벽의 개수를 bfs를 돌면서 저장했다가 개수가 K가 될 경우 벽을 만나면 지나치지 못하게 식을 세웠다. 이렇게 세우니 벽을 나중에 뚫는 경우가 더 최소인 경우가 존재하여 틀렸습니다가 떴다. 그래서 bfs를 돌 때, 방문을 했어도 이번에 방문하는 거리가 최소라면 push가 되게 했는데 이래도 오류가 났다... 솔직히 어떤 반례가 존재하는지 잘..