When writing the paper about completed experiments, should you cite work you hadn't read before? I (try to) do research in Computer Science/Deep Learning. I recently did some work developing a novel idea and am writing a paper on it. I have only written one paper before, and I'm currently being paralysed by the related works section.

It seems impossible for me to have a thorough understanding of everything that is related. When I started the work, I was working from the understanding I had at the time. The vast majority of the influence on my work was only from ~4 other papers, and what I took from them as background in the area. 

In doing the work, I have come to understand other work and the context much better (I find that working on a problem, and attempting to explain my work, demystifies a lot of statements in other people's papers). Now, reading other papers on other related work is more plausible for me. I'm realising that I've made some assumptions based on those core papers, and want to find citations for them.

This appears backwards to how it's supposed to work; the papers that I would cite in this manner I hadn't read or understood before I started working. So, my main question is: is it illegitimate to cite several papers you hadn't read before completing the majority of the experiments?

Follow up questions are: Is it normal to only have a few main influences, and many lesser influences? (Computer-science-specific) How much of a paper's theory/background is worked out after making it work? Is it my fault if I haven't come across some important related idea, or is it generally accepted that you might miss something?
An important realization I had while writing the first few papers of my career is that a paper/thesis/any kind of publication should not be a recollection of your path through this research. You will have made many experiments as part of the research that need not actually appear in the paper because they're not important for what you're trying to show.

Instead, a publication is a way for you to explain insights you have gained during this research. In which order you came to these insights, in which you read other papers, or in which you did experiments is -- generally -- not important for the telling of the story. 

So, regarding the original question whether one should cite a paper one hadn't read before the research started: it can't be answered with yes/no. Whether a paper should be cited (as asked in the title) has nothing to do with when one read the paper. It has everything to do with whether you think it's a useful reference for readers to have. In the body of the question, there is a variant: whether it's "legitimate", and there the answer clearly is "yes". In particular, we add references to papers all the time that were pointed out by reviewers -- long after the research was concluded for the most part.