반응형 컴퓨터 사이언스/BOJ42 [c++] 백준 #2206 벽 부수고 이동하기 1년 만의 백준 문제 풀기. 시작은 하게 골드4 정도의 만만한 BFS 문제로 골랐다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 일반적인 2차원 BFS 방식으로 다시 차근차근 구현하는데 한 시간 정도 걸렸고, 질문 검색에서 제안하는 디렉션을 읽고.. 최종 답 맞추기까지 1시간 45분 정도 걸렸다. 모든 벽을 다 한 번씩 부수면서 N*M번 BFS를 돌리면 계속 반복 계산하는 경우들 때문에 O(N^4)로 시간초과가 난.. 2022. 3. 2. [c++] 백준 #1011 Fly me to the Alpha Centauri 난이도 순서대로 풀기 리스트에 있어서 풀게 된 문제이다. 어렵지 않았지만, 실버1보다는 조금 더 난이도가 있었겠다 싶은 그런 문제이다. 내가 좋아하는 스타일의 깔끔한 그리디 문제이다. www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제 설명을 짧게 해보자면, x 지점에서 y 지점까지 갈 때 공간이동 장치의 작동횟수를 계산하는 것이다. 공간 이동장치는 맨 처음에는 거리 1만큼을 움직일 수 있고, 작동시킬 때마다 이.. 2021. 2. 7. [c++] 백준 #1201 NMK 재미있는 그리디 문제이다. 2년 전에 손도 못대던 문제를 풀었더니 기분이 좋다. www.acmicpc.net/problem/1201 문제 내용은 1부터 N까지의 수를 한 번씩 이용해서 가장 긴 증가하는 부분 수열의 길이가 M이고, 가장 긴 감소하는 부분 수열의 길이가 K인 수열을 출력한다는 것이다. 숫자를 배열하면서 규칙을 찾아보면, 숫자를 오름차순 해둔 상태에서 M개의 그룹을 만들고, 각각의 그룹을 내림차순하면, 가장 긴 증가하는 부분 수열의 길이를 M으로 만들 수 있다. 그러면, 각각의 그룹 내에 감소하는 부분 수열이 존재하기 때문에, 그룹에 들어가는 원소의 수 중 최댓값이 K가 되게 된다. 따라서, 이 문제는 M개의 그룹에 최대 K개의 원소를 배치하는 문제로 바뀌게 된다. (무언가 굉장히 많이 본 .. 2021. 1. 24. [c++] 백준 #9663 N-Queen 너무 유명한 brute force 문제이고, 2~3년 전 쯤 2차원 행렬로 표시해서 풀다가 구현을 잘못해서 잘 안되니 포기했던 문제를 친구가 풀이방법을 설명해줘서 낼름 듣고 바로 푼 문제이다. 내용은 NxN 체스판 위에 N개의 퀸이 서로 공격할 수 없게(가로, 세로, 대각선 x) 두는 경우의 수를 계산하는 것이다. www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net queen의 가로, 혹은 세로 좌표가 다른 queen과 겹치지 않으면 되기 때문에 굳이 2차원 배열을 만들 필요가.. 2021. 1. 24. 이전 1 2 3 4 ··· 11 다음 반응형