지뢰찾기 게임에서 지뢰의 최대 개수를 찾는 알고리즘

9082번: 지뢰찾기 2*n 배열이 주어진다. 첫번째 행은 숫자들이 쓰여있는데 그 블록 주위에 지뢰가 몇개 있는지를 나타낸다. 두번째 행은 지뢰가 숨겨져 있는 행인데, *, #으로만 주어진다. *은 지뢰이다. 예를 들어 11122####*로 주어진다면 첫번째 #은 바로 위에 1이 쓰여있고, 우측 대각선 상단에 1이 쓰여있으므로 지뢰가 있을 수 있다. 11122*###* 그리고 4번째 #에는 왼쪽 대각선 상단에 1, 바로 위 2, 우측 대각선 상단에 2가 쓰여있는 것으로 보아 지뢰가 있을 수 있다 11122*##** 이때 *을 포함해서 숨겨진 지뢰의 최대 개수를 구한다. ---------------------------------------------------------------------------..

• format_list_bulleted 애드 혹 알고리즘
• · 2025. 4. 16.
• textsms

코딩테스트 복기 - 당장 필요한 값을 구하지 않고 나중에 필요할 때 값을 구하는 테크닉2

1. 문제 n명의 아이는 연속 A[i]일 이내 칭찬을 듣지 못하면 기분이 안좋아진다. (i = 1,2,3,...,n) 선생님이 1일부터 m일까지 매일 1명의 아이 B[i]번 아이에게 칭찬을 해준다. (i = 1,2,...,m) 이미 기분이 안좋아진 아이에게 칭찬을 해줘도 아이는 기분이 좋아지지 않는다. 1일부터 m일까지 각 날마다 기분이 좋은 아이의 수를 구하고자 한다. 0일차에는 모든 아이에게 칭찬을 해줘서 기분이 좋은 상태라고 가정한다. 예를 들어 4명의 아이는 2일, 3일, 1일, 2일 이내에 칭찬을 들어야한다. 선생님이 6일 동안 3번, 1번, 2번, 1번, 4번, 1번 아이에게 칭찬을 해줬다. 1일차에는 3번 아이에게 칭찬을 해줬다. 2일차에는 1번 아이에게 칭찬을 해줬는데, 2일 이내에 칭찬을..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 3. 26.
• textsms

ABC 339 D번 복기 - 4차원 visited 배열 BFS 백트래킹

1. 문제 D - Synchronized Players (atcoder.jp) D - Synchronized Players AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 하라는대로 구현하면 된다 두 플레이어 P가 움직이는데 두 플레이어는 같은 방향으로 움직이게 되어있다. 또한 한 플레이어가 해당 방향으로 움직일수 없더라도 다른 플레이어가 움직일 수 있다면 움직이는 경우로 생각한다 그래서 먼저 두 플레이어의 위치를 찾고 BFS를 수행하는 전형적인 형태 n = int(stdin.readline()) maps = ..

• format_list_bulleted Atcoder
• · 2024. 2. 5.
• textsms

생각해서 브루트포스 탐색 범위를 줄여야하는 경우1 (장난감 강아지)

1. 문제 31287번: 장난감 강아지 (acmicpc.net) 31287번: 장난감 강아지 U, D, L, R로 이루어진 길이 $N$의 문자열 $S$가 주어진다. 문자열 $S$를 $K$번 이어 붙인 문자열을 $T$라고 하자. 장난감 강아지 타카하시는 2차원 좌표평면의 원점에서 시작해서 $T$에 적힌 문자를 하 www.acmicpc.net 2. 풀이 의외로 생각을 요구해서 배울 점이 있는 문제 위,아래,왼쪽,오른쪽으로 강아지가 움직이는데.. 문제는 길이 2000인 문자열 S를 최대 $10^{9}$번 반복시켜서 2000*1000000000번 강아지가 움직일 수 있다 이때 원점에서 움직이는데 다시 원점으로 돌아올 수 있는지 확인해야하는 문제 2000*1000000000번을 1초안에 다 해볼수는 없을 것 근데..

• format_list_bulleted 브루트포스
• · 2024. 2. 3.
• textsms

문자열 정렬할 때 실수하기 쉬운부분 복기하기 -줄서기-

1. 문제 17178번: 줄서기 (acmicpc.net) 17178번: 줄서기 아이즈원의 팬인 시온이는 드디어 티켓팅에 성공하여 콘서트를 갔다. 콘서트장에 일찍 도착한 시온이는 기대하며 입장을 위해 줄을 섰다. 하지만 아이즈원의 인기대로 시온이를 포함한 많은 www.acmicpc.net 2. 풀이 문제를 읽어보면서 구조를 잘 생각해보면.. n개의 줄에 다섯명씩 있는데 앞 사람부터 입구에 입장을 할건데 티켓 순서대로 입장을 수행한다 근데 티켓 순서는 알파벳이 사전 순서대로, 그리고 숫자가 작은 순서대로가 먼저 오는것이다 입장을 하는데 내 순서가 아니면 대기줄에서 들어갈 순서가 맞는 사람인지 검사해서 들어갈 사람이면 보내주고 그래도 들어갈 사람이 없으면 현재 대기줄이 아닌 사람은 대기공간에 들어가야할 것이다..

• format_list_bulleted 구현,시뮬레이션
• · 2023. 1. 29.
• textsms

3차원 BFS에서 조금은 섬세한 디테일 -공주님을 구해라!-

1. 문제 17836번: 공주님을 구해라! (acmicpc.net) 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net (1,1)에서 용사가 (N,M)에 있는 공주님을 구하고자 움직일 수 있는 최단 시간을 구하는 프로그램을 작성 맵에 반드시 하나가 있는 전설의 명검 그람을 획득하였으면 제한 없이 벽을 부수고 이동할 수 있다 2. 풀이 분명 쉬운 문제지만... 너무 쉽게 생각하면 틀리기 쉽다고 해야하나.. 잘못된 생각 >> 그람이 반드시 하나가 있다면, 그람을 획득하고 이동해야 최단시간? >> 하지만..

• format_list_bulleted DFS BFS 정복기
• · 2022. 11. 13.
• textsms