본문 바로가기

분류 전체보기

[백준 2206번] 벽 부수고 이동하기 C++ 2021. 3. 19. www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 진짜... 고생 많이 한 문제입니다. 사실 이런 벽을 뚫고 미로찾기 하는 문제는 접해본적이 없을뿐더러... 어떻게 문제를 풀어야하나 고민을 엄청한 문제였습니다 결국 풀게된 컨셉은 BFS의 매개변수로 [ 벽뚫 여부 카운트 한 값(1=뚫은적있음 , 0 =아직 뚫어본적없음) / x좌표 / y좌표] bfs 탐색을 하다 벽을 만났을경우 벽을 뚫어본 경험이 있으면 continue; 아직 벽을 뚫어..
[백준 3055번] 탈출 C++ 2021. 3. 18. www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net foameraserblue.tistory.com/8 [백준 5427번] 불 C++ www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 foameraserblue.tistory.com 5427번 불 이랑 완전히 똑같은 문제였습니다. 해설이 완전 동일하기..
[백준 5427번] 불 C++ 2021. 3. 18. www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 문제를 딱 보고 아 이건 무조건 bfs 문제다 라고 판단했는데 한번에 두 가지의 주체를 움직이는 bfs문제에 대한 경험이 없었어서 좀 고생했습니다. 불이 먼저 움직이고 불이 움직인자리를 visit 처리 한 후 상근이가 움직여서 불이 닿은 자리는 상근이가 아예 가지 못 하게 구성했습니다. 불같은경우 초기에 한개만 존재하는게 아니라 다수의 위치에서 불이 존재할 수 있기 때문에 '*' 을 입력 받을때 미리 큐에다가 위치정보를 저..
[백준 2468번] 안전 영역 C++ 2021. 3. 18. www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 정석적인 DFS 문제였습니다. 완전탐색을 위해 시간복잡도를 고렸는데 그래봤자 최대 N 이 100이기때문에 완전탐색이 가능했습니다. 제가 전역변수에 dx, dy라고 적은 위,아래,왼쪽,오른쪽 이동법은 많이 쓰이는 방법이니 패스하구.. 비가 내린 수위를 처음부터 끝까지 완전탐색 하며 매 수위마다 나온 안전지대의 갯수를 매번 최대값 도출 함수 max를 이용해서 갱신해줬습니다. 최후의 수위인 99까지 돌았을때 나온 resul..
[백준 11403번] 경로찾기 C++ 2021. 3. 17. www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net i번째 숫자가 갈 수 있는 모든 목적지를 출력해주면 되는 문제였습니다. (i -> k) 가 가능하고 (k -> j) 가 가능하다면 (i -> j )가 가능함을 출력하면 되는 문제였습니다. i -> k -> j 지금까지 풀었던 dfs와 많이 달랐고 나중에 찾아보니 이런 문제를위한 알고리즘이 있는데 제가 아는 범위는 아니기때문에 dfs를 사용했습니다. 모든 시작점 i 를 대상으로 깊이 우선 탐색으로 깊~게 탐색한 후에 갈 수 있는 모든 목적지를 visit=..
[프로그래머스 LV 2] 스킬트리 C++ 2021. 3. 17. programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 처음에 큐 자료구조를 이용해서 문제를 풀었습니다. skill 에 있는 순서대로 스킬을 배울 수 있기때문에 "순서대로" 라는 마인드로 큐를 사용했는데.. 3중 for문이 나오면서 풀이가 점점 나락으로 빠졌습니다. 그래서 대안을 찾은게 해쉬인데 key에 배울 수 있는 스킬, value 에 그 스킬의 순서(입출력 예에서 1번째로 배우는 C의 경우 1번을 부여) 를 부여했습니다. 현재의 power(배울 수 있는 스킬의 value 값) 을 가지고 스킬을 배울 수 있으면 power++ 해서 다음 스킬도 배울 수 있게 값을 올려주고 혹시 배울 수 없는 스킬이 나올경우 b..
[백준 1182번] 부분수열의 합 C++ 2021. 3. 16. www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 프로그래머스에서 DFS관련 문제를 푸는데 뭔가 진행 후 다시 돌아왔을때를 가정해서 카운트를 해야 될 것 같은 문제를 봤었습니다 결국 못 풀었고 과연 이러한 문제는 어떻게 풀어야 하나 찾던 중 백트래킹 이라는 알고리즘을 발견했습니다. 아직 완벽히 이해가 되진 않았지만 주석에 보이는 그대로 미포함, 포함 상태를 각각 탐색한 후 포함상태에서 다시 미포함 상태로 바꿔주는게 메인 아이..
[백준 1018번]체스판 다시 칠하기 C++ 2021. 3. 16. www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 완전탐색으로 8 X 8 로 떼어낼 수 있는 부분을 전부 떼어내서 바꾸는 횟수를 전부 다 구했습니다 주의할점은 왼쪽 위가 W로 시작했더라도 1) 왼쪽 위가 그대로 W인 체로 바꿔지는 칸의 숫자 세기 2) 왼쪽 위를 B로 바꾼 후 바꿔지는 칸의 숫자 세기 이렇게 접근을 해야되는점이었습니다. 처음에 진짜 무식한 방법으로 완전탐색을 돌리니 시간초과가 나와서 다른 분의 풀이를 참고했습니다. 풀이를 보니 각 칸의 ..
[백준 2503번] 숫자 야구 C++ 2021. 3. 16. www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 완전 탐색 문제로 받은 문제인데 처음에 좀 막막했다. 문제를 푼 방법은 우선 bool = arr[ i ] 에서 i를 123~999의 숫자로 설정해서 모두 가능성이 있는 답이라고 가정(true로 저장) 그 후 완전 탐색을 통해 안 되는 숫자( i )들은 false로 바꿔준 후 마지막까지 true 인 배열의 갯수를 세서 정답을 도출했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..

티스토리툴바