Memcache is a caching daemon storing all types of data you push into it.
XCACHE/APC (well beside the fact you can cache items with both, though i believe there are some limits here) are meant to optimize and compile your runtime code. So first request is compiled, and in second request, the code is served already compiled which means less execution time and memory usage .
So, you would use them both, actually you would use XCACHE which is proven to be more robust than APC in my findings (and also, if in the future you decide to drop apache for lighttpd then using already xcache will be better) for opcode caching and use memcache to store your database calls or partials, or whatever portion of the code takes more time to execute than it should .
To use Memcached with yii you want to look at the CMemCache component.
Whether you’ll benefit from Memcached depends on whether you’ve got expensive/slow performing database queries and highly complex processing tasks which need caching. Generally it’s better NOT to use additional caching until you need it. Adding caching upfront adds complexity and can hide underlying performance problems.
On a server with with 512MB the memory is used by the OS (linux, Windows etc) and any other processes like MySql, APC and Memcached. How much money you give MySql vs Memcached depends on your particular needs. A properly tuned MySql database has good query caching - it doesn’t perform as well as Memcached but there’s no management overhead or additional complexity and for a lot of sites the difference in performance doesn’t make much difference.
Using shared hosting is a great way of focusing on performance. Using yii is a good start, it’s got a low memory footprint. The next thing to look at is tuning your web server before you worry about caching. If you go with a standard Apache setup it uses a lot of the memory on a 512MB machine - personally I’d recommend using nginx and php-fpm or alternatively something like Apache with MPM worker configuration. That will reduce the memory usage of the web server which ultimately frees up memory for either MySql or Memcached.
Finally always use APC or some kind of PHP accelerator. It makes a massive different to performance. I personally use APC with Apache on a major Drupal site and for all my “minor” yii sites that use nginx. I’ve had no problems with it in either configuration.