본문 바로가기

알고리즘19

[Programmers] 신규 아이디 추천 - python 프로그래머스의 신규 아이디 추천 문제입니다. 주어진 문자열을 아래 형식에 맞게 바꾸는 문제입니다. 정규식을 활용해 풀었습니다. 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다. 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 ne.. 2022. 6. 28.
[BOJ] 1003 피보나치 함수 - python 1003번: 피보나치 함수 (acmicpc.net) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 일반적인 피보나치 수열 문제의 간단한 변형 문제라고 생각된다. 피보나치 함수에서 0 혹은 1까지 방문하는 횟수를 세는 문제이다. 처음에는 평소와 같이 재귀를 이용하여 풀었더니 시간 초과가 발생하였다. 각 숫자 별로 0과 1의 수를 리스트 형태로 전부 저장한 뒤, 값을 꺼내왔다. import sys T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readline()) dp = [[0,0] for i in range(N+1)] if N ==.. 2022. 4. 29.
[BOJ] 10844 쉬운 계단 수 - python 10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 계단 수는 23, 454처럼 각 자리수가 1씩 차이나는 수를 말한다. 10844 쉬운 계단 수는 N이라는 입력을 받았을 때, N 자리 계단수의 총 개수를 출력하는 문제였다. DP 문제였는데, 점화식을 세우는 부분이 조금 어려웠다. N==1, 한 자리 수라면, 1,2,3,4,5,6,7,8,9 총 9개의 계단 수를 갖는다. N==2, 두 자리 수라면, 10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98 총 17개의 계단 수를 갖는다. 4자리 수의 마지막이 7로 끝나는 계단 수의 경우의 수를.. 2022. 4. 27.
[BOJ] 18352 특정 거리의 도시 찾기 - python 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 시작 노드로부터 일정한 거리의 노드를 찾는 문제이다. 거리를 저장하는 부분에서 많은 시간이 걸렸다. 처음엔 방문 여부를 저장하는 visited와 거리를 저장하는 distance list를 따로 사용하였는데, 코드를 좀 더 간결하게 만들기 위해 visited_dis 하나로 통합하였다. 처음 제출에서는 리스트 형태의 큐를 사용하였더니.. 2022. 3. 30.

티스토리툴바