본문 바로가기

Programming399

백준 1981 배열에서 이동 정답 참조 1. 기본 dfs 하면 시간초과가 납니다. 2. 그러므로 다른 방법을 찾아야 하는데, 배열의 각 수가 0~200 사이라는 사실을 알아채고이분탐색과 bfs 를 사용합니다. 3. 방법은 먼저 배열 내에 가장 작은 수와, 가장 큰수를 찾습니다.이것을 이분 탐색하면서 범위를 줄여 나가도록 합니다. 예제를 통해서 보면 0~8 을 잘른 4로 시작합니다.그런데 여기서 큰 for 문 하나를 작성해야 하는데, 이는 가장 작은 수부터, 왜 가장 큰 수까지 조사를 하는 것이지? 가장 작은 수부터, 가장 큰수 - 범위 만큼 l 이 1씩 증가합니다. 이 엘 변수를 사용해서 맵을 구성해줍니다. 갈 수 있는 길과 갈 수 없는 길을 구분합니다. 그리고 bfs 를 통해서 정리된 맵에서 0을 따라서 끝까지 갈 수 있는지 없는지를 판단하.. 2018. 3. 23.
이진 탐색 알고리즘 C++ 1. 이진 탐색을 하기 위해서 필요한 것, 인덱스, 키, 그리고 찾았다 안찾았다. 이런 변수가 필요합니다.정렬이 되어 있어야 합니다. 헤드와 미드가 있고, 미드의 인덱스 데이터가 그 안에 있으면 그 안에 없으면 각각 미드를 수정합니다. 그리고 데이터가 미드와 같으면 키를 출력하면 됩니다. 오께이. 그리고 찾으면 break 를 하도록 합니다. 이전에 배열에서 이동하기 문제를 풀어보도록 하겠습니다. 이것을 응용 하면 되겠습니다. #include using namespace std;void main() {int data[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14 };int n = 14;int index = -1;int key;cin >> key; int head = 0;int tai.. 2018. 3. 23.
백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 문제 파악하기. 문제를 정확하게 읽고, 풀이 할 수 있는 다른 방법이 있는지 확인 해보기.그럼 일단 스스로 이분 탐색을 구현해보도록 하겠습니다. 다음에 적용하기 위해서 1. 이분 탐색2. bfs 돌려서 도달 가능한지 확인 해보기. 2018. 3. 23.
백준 2169 로봇 조종하기 디피문제 정답 참조 맵, 디피맵이 있습니다. 일단 맵을 저장해두고, 라인도 하나 저장해두는데, 라인 0에는 라인1에는 무엇을 저장하는가요. 토탈은 변수가 사용안됩니다. 먼저 왼쪽, 오른쪽 위에서 아래로 내려오는 3가지 방향이 있으므로, 이 3가지 내려오는 방향 중에 가장 큰 것을 저장해 나가면 됩니다. 1. 첫줄은 오른쪽으로만 저장해 나갈 수 있으므로, 저장해둡니다.2. 그 다음에 2행부터는 일단 라인 0,1 에 위에서 내려오는 값들을 저장해 둡니다.3. 위, 왼 값을 비교해서 큰 값을 라인 0에 저장을 합니다.4. 위, 오 값을 비교해서 큰 값을 라인 1에 저장을 합니다.5. 라인 0과 1을 비교해서 큰 값을 프리맵에 저장을 하면 됩니다. 마지막 도달하는 점의 값을 출력하면 됩니다. 일단 이렇게 알아두고 넘아가도록 합니다.. 2018. 3. 23.
백준 1018 체스판 다시 칠하기 1. 입력 받는 함수2. 입력받고 8*8 만 검사하는 함수3. 몇개의 수정이 필요한지 검사하는 함수를 만듭니다. 여기서 3번 함수인 검사하는 함수에서, 아이디어는 맵의 인덱스의 합이 짝수인지 홀수인지를 검사하여서 원래 체스판의 색이 아니면 modCnt++ 을 하였습니다. 잘라내는 것에서 지난번에 디스플레이에서 불량 화소가 얼마나 나오는지를 알아내는 문제에서 짜 본 적이 있기에 시간을 벌고, 자신감 있게 해결할 수 있었습니다. 풀이 시간 30분 입니다. /*2001 체스판 다시 칠하기 시작.검은색, 흰색, 8 곱 8 체스판으로 만들고 싶다.잘라낸 후에 몇 개의 정사각형을 다시 칠하기. 칠해야 하는 보드의 최솟값을 구하는 프로그램을 작성하세요.체스판은 2 종류 입니다. 1. 입력 받는 함수2. 입력받고, 8.. 2018. 3. 22.
백준 3085 사탕 게임 처음 설계를 할때, 명확하고, 이것이 제대로 돌아가는지, 예외는 없는지까지 고려해야 합니다. 이 문제를 푸는 방법으로는 1. 인접한 사탕을 선택하고, swap 하는 함수2. swap 을 한 후에 가로로, 세로로 연속된 사탕이 몇개 있는지 검사하는 함수 이렇게 2개의 함수로 나누어서 풀이하면 됩니다. /*1908 사탕게임1. 사탕을 교환하는 함수 -> 하나씩 이동하는데, 일단 가로로 인접한 것 2개를 교환, 하는 i,j 그리고 i,j를 이동하는데 아래랑 교환하는 것 이렇게 짜도록 하겠습니다. 조사가 끝나면 다시 i,j 를 그대로 변경해주도록 하겠습니다. 2. 교환한 맵에서 가로, 세로로 같은 것이 가장 긴 맵 찾으면 됩니다. bfs 가 아니라, for 문으로 풀면 되겠습니다. */ #include #inc.. 2018. 3. 22.
백준 1726 로봇 정답 참조 1. 1,2,3회에 걸쳐서 같은 방향으로 전진할 수 있는가? 갈 수 있다면 그 방향에 큐를 넣고 그 방향에 대해서 비지트 함수에 넣어 둡니다. 2. 현재 자리에서 턴한 것들에 대해서 큐에 넣어 둡니다. 같은 방향이면 큐에 넣지 않는 다는 것을 알겠는데반대방향에 대해서도 큐에 넣지 않는 이유는 무엇인가요? 예를 들어, 현재 dir = 1 이 어서 동쪽을 바라보고 있는데,i = 1 이어서 동쪽에 대한 것은 안넣습니다. 그런데 opp(1) = 2 입니다.i = 2 일때도 넣지 않습니다.그 이유는 무엇인가요? 아 아래 큐에 넣을때 cnt+1 이 들어가기 때문입니다.저 조건을 없애고, opp 라면 2를 들어가는 코드를 짜보도록 하겠습니다. 오께이 정답 맞습니다. 여기서 굉장히 특이한 점은 visit 가 3차원이라.. 2018. 3. 21.
리팩토링 나쁜 디자인의 코드를 좋은 디자인으로 바꾸는 방법 리팩토링이란 무엇인가요리팩토링은 외부동작을 바꾸지 않으면서 내부 구조를 개선하는 방법으로, 소프트웨어 시스템을 변경하는 프로세스입니다. 리팩토링시 중요한 점은소프트웨어를 보다 이해하기 쉽고, 수정하기 쉽도록 만드는 것이며, 겉으로 보이는 소프트웨어의 기능을 변경하지 않는 것입니다. 따라서, 리팩토링을 할 때는 기능을 추가해서는 안되고, 단지 코드의 구조에만 신경 써야 합니다. 프로그램의 가치를 높이는 것입니다. 2. 왜 해야 하는가?소프트웨어의 디자인을 개선시킵니다. 정기적인 리팩토링은 코드가 디자인을 유지하도록 도와줍니다.소프트웨어를 더 이해하기 쉽게 만듭니다. 버그를 찾도록 도와줍니다. 3. 언제 해야 하는가?리팩토링 자체를 목적으로 삼는 것이 아니라.. 2018. 3. 21.
백준 3055 탈출 1. 이전 불 문제와 똑같습니다. 단순하게 끝나는 지점이 존재하는 것만 다릅니다. 불 문제와 같이 큐에 먼저 물을 넣고 마지막에 스타트를 넣습니다. 그리고 타입과 시간을 저장하는 변수를 같이 큐에 넣습니다. 그리고 큐를 돌리기 시작합니다. 큐를 돌리면서 물을 넘쳐나고 고슴도치는 이동합니다. 이동할 수 있는 곳으로, 그리고 다시 물음 넘치고 고슴도치는 이동할 수 있는 곳으로 이동합니다. 검사는 마지막에 도착점 옆에 동서 남북 중에 한 곳에 고슴도치가 위치하고 있다면 시간+1 을 해서 종료를 시키도록 합니다. 2018. 3. 21.
백준 5427 불 정답 참고 불, 5427번 문제. 상근이 빈 공간과 벽으로 건물에 갇혀 있습니다. 여기서 처음에 큐를 돌때에, 단순하게 처음에 다 넣고 나서 마지막에 상근이를 이동시키면 됩니다. 1. 문제 그대로 코딩하는 것이 필요합니다.분할 하는 것도 필요합니다. 어떻게 하는 것이 좋을지 생각을 합니다.문제가 꼬이지 않도록 구현하는 것이 가장 좋습니다. 이 문제에서는 불이 나가고 상근이가 움직이고, 이런식으로 표현하면 되고,큐에 x,y 뿐만 아니라 sec 와 type 을 넣어서 체크하고 있습니다.초마다 점진적으로 움직이는 것은 bfs 를 사용하면 됩니다. 처음 사용한 방법도 틀리지는 않지만, 따로 구현하게 되면 디버깅하는 것이 쉽지 않습니다. 초에 따라서 변하는 것이기 때문에, 초에 따라서 변화가 모두 완성되도록 구현합니다. 탈.. 2018. 3. 21.

티스토리툴바