We propose two efficient algorithms for configurational sampling of systems with rough energy landscape. The first one is a new method for the determination of the multicanonical weight factor. In this method a short replica-exchange simulation is performed and the multicanonical weight factor is obtained by the multiple-histogram reweighting techniques. The second one is a further extension of the first in which a replica-exchange multicanonical simulation is performed with a small number of replicas. These new algorithms are particularly useful for studying the protein folding problem.