2020년 추석 이후 html, css 등을 가볍게 공부하고, 11월 경 django 공부를 시작했습니다. 저는 비전공자로써 막연하게 시작했습니다. 알고리즘, 자료구조 등 이론적인 공부 또한 중요하지만, 실질적으로 어떤 성과를 낼 수 있는 개발을 하고 싶었습니다. 이번 코로나 사태로 인해 어디 참여하여 배울 기회도 적고, 기존에 암호학을 공부했던 이유도 있던 터라 동아리, 인강 등을 접하기에는 타이밍이 아쉬웠습니다. 그래서 백엔드 개발자로 일하고 있는 친구의 도움을 받아 파이썬, C, C++ 정도만 할 줄 아는 저에게 django를 추천해줬습니다. django는 공식 사이트 또한 잘 되어있고, 많은 서비스를 제공하기에 처음 배우기에는 괜찮을 거라 하였고, 그 친구 또한 처음에 django로 시작하였다고 ..
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 지난 주에 교내 알고리즘 대회에서 탈탈 털려서 (구현은 대체적으로 해냈지만 테스트 케이스를 통과 못해서 상은 받지 못했다....) 기본 문제를 하나 풀어보았습니다. 간단한 그래프 문제입니다. 방향 그래프에서 모든 정점에서 모든 정점으로 가는 경로의 유무 (최단 경로X) 만 판단하면 되는 간단한 문제입니다. 최단 경로가 아닌 경로의 유무만 알면되기에 다양한 방법이 있지만, 플로이드 와샬 알고리즘을 이용하여 풀었습니다. 플로이드 와샬 알고리즘이란 가중그래프..
www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 5000자리 이하의 암호문이 주여졌을 때, 가능한 경우가 얼마인지 구하는 문제이다. (modulo 1000,000) 문제에서 A:1 ~Z:26으로 대응되게하였으므로 앞자리가 0이면 암호가 성립되지 않는다. 또한, 70 과 같은 경우는 앞자리가 0이 아니지만, 7 다음으로 0인 케이스가 존재하기 때문에 이러한 경우도 안 된다. 되는 경우는 다음과 같다. 해당 자리수에 가능한 수를 dp배열을 이용해 표기하면 점화식은 다음과 같다. ..
www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 케빈 베이컨의 6단계 법칙이라는 유명한 법칙이다. 세상 모든 사람은 6단계 안으로 만날 수 있다는 것이다. 문제는 간단하다. 사람들이 숫자로 주어지고, 사람들의 관계가 주어졌을 때 케빈 베이컨 수가 가장 적은 사람을 고르는 문제이다. 케빈 베이컨 수는 사람들 사이의 최소 링크 수의 합이다. 예를 들어, 사람들 사이의 관계가 (1,3), (1,4), (4,5), (..
백준 / BOJ / 1764 듣보잡 C++
www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 거친 제목의 문제 이름에 이끌려 들어가보았지만, 쉬운 문제였습니다. (그렇지만 틀렸었다.) 듣도 못한 사람을 listen 벡터에 넣었습니다. 처음에는 listen 벡터 외에 see 벡터를 추가하여 보도 못한 사람들의 벡터를 만들어 이분 탐색을 진행하였지만, 시간 초과가 났습니다. (시간 초과가 이것 때문은 아니고, 처음에는 이분 탐색 알고리즘을 직접 구현했었지만, 시간초과나서 그냥 algorithm 라이브러리..