구현 검색 결과

해당 글 26건
소코반 구현해 보기 : 맵 상태를 쪼개면 답이 보인다.

구현 8번째 시간입니다. 실전 문제 하나를 풀면서, 여러 가지 기법들을 다뤄보겠습니다. 소코반 게임은 캐릭터와 박스가 있습니다. 이 박스들을 적절히 목표 지점에 이동시켜야 하는 게임입니다. 아. 옛날에 많이 있었던 게임 중 하나입니다. 그냥, 우리는 캐릭터를 명령에 맞게 이동시킨 다음에 맵의 상태를 출력하는 것이 목표라면 목표라고 할 수 있겠네요. 그런데, 맵의 상태를 보니까, 목표 지점에 있는 ~가 눈에 보입니다. 즉, 목표 지점이면서 박스가 있는 곳이라던지, 목표 지점이면서 캐릭터가 있는 곳이라던지. 즉, A and B 조건이 눈에 밟힙니다. 이렇게 되어버리면 경우의 수를 처리해야 할 것이 상당히 많아집니다. 이것을 적절히 분해를 해서 처리를 하는 방법을 고민해 봅시다. 물론, 제 코드를 조금 더 응..
구현 2019. 12. 9. 20:29
bit 연산 : on/off 상태가 20개 언저리면 고려해 보자

구현 카데고리 7번째 글입니다. 오늘은 상태를 어떻게 나타내는지에 대한 이야기를 해 보도록 하겠습니다. 켜졌다와 꺼졌다. 이것은 각각 1과 0으로 표현이 가능합니다. 울타리가 있다. 울타리가 없다. 또한 1과 0으로 표현이 가능합니다. 즉, 어떠한 상태가 2개만 있을 때, 우리는 bit operation을 이용할 수 있습니다. 이걸 어떻게 써야 할까요? 예제를 다소 어려운 문제로 잡아보겠습니다. 백준 1200번, BOI 2008 #5번 문제인 기상 예측 문제를 봅시다. 이 문제는 가로선 n개와 세로선 m개로 영역을 적절히 나눌 때, 부분합의 최대를 최소로 하는 문제입니다. 예를 들어, 2 by 3짜리 영역에, 가로선 1개, 세로선 1개를 그을 수 있다고 해 봅시다. 그러면 이렇게 그을 수 있습니다. 이 ..
구현 2019. 11. 10. 19:11
모듈화 : 함수 하나 잘 만들면 구현이 쉽다.

안녕하세요. chogahui05입니다. 함수 잘 만드는 거. 상당히 중요합니다. 구현을 잘 하기 위해서는 모듈화가 중요합니다. 기능을 어떻게 잘 함수로 뺄 지가 중요합니다. 우리가 쉽게 생각할 수 있는 strlen이나, strcat을 생각해 봅시다. 만약에 그 기능들이 모두 main 함수 안에 구현이 되어 있다면 어떨까요? 생각만 해도 끔찍할 겁니다. 물론 1~2줄밖에 되지 않겠지만요. 그러면 문제를 보고 기능을 어떻게 잘게 나누느냐가 중요하다는 것인데요. 오늘은, 백준 문제들 중에서, 어떻게 기능을 나눌 수 있는지만 간단하게 연습해 보도록 하겠습니다. 강의용 예제 코드는 제 github의 BOJ 폴더의 17495_example.cpp입니다. 당연하게도 4444 문제를 찍기 위해서 급하게 작성된 코드이기..
구현 2019. 10. 25. 19:01
배열 회전 알고리즘 : 읽는 방법만 생각하면 어렵지 않아요.

배열 회전 알고리즘은, 구현 문제에서 심심찮게 보이는 문제 중에 하나입니다. 우리는 n by n 배열을 시계, 그리고 반시계 방향으로 temp array를 쓰고 회전하는 방법을 배워보도록 하겠습니다. 물론, 면접에서는 n by n짜리를 안 쓰고 돌리는 방법을 물어볼 수도 있습니다. 이에 대한 방법은, 과제로 드리겠습니다. 배열이 있습니다. 이것을 시계 방향으로 90도 회전시키면 어떻게 그려질까요? 요렇게 그려집니다. 그런가요? 그러면 우리는 첫 번째 줄부터 특징을 잡아야 하는데요. 1번째 줄에는, [..][0]이 들어갔다는 것을 알 수 있습니다. 2번째 줄에는 [..][1]이, 3번째 줄에는 [..][2]가 들어갔다는 것을 알 수 있어요. 이제 0열부터 2열까지 열별로 볼까요? 그러면, 0열은 [2][...
구현 2019. 10. 7. 15:43