I started at around the same time -- Red Hat Linux 4 era. Yum didn't exist yet. I was also quite new to Linux, but I'm reasonably sure there really wasn't something that would do dependency resolution for you. You either had to find an RPM that had the right version, or you had to find a tarball somewhere and run configure and make yourself.
