문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 백트래킹을 이용해서 해결했다. import sys def backtracking(): if len(password)==L: cnt=0 for i in vowel: # 모음의 수 확인 cnt+=password.count(i) if cnt>0 and L-cnt>1: print("".join(map(str,password))) return for i in word: if i not in passw..

문제 https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 풀이 n을 1,2,3으로 만드는 방법의 수를 저장할 DP 테이블 d를 정의하여 문제를 해결했다. 먼저 1만으로 n을 만드는 방법의 수는 모두 1개이다. [ex) 6 -> 111111] 2가 추가되었다고 생각하면 n을 1과 2로 만드는 방법의 수는 1(1로만 만드는 경우의 수) + (n-2) 이다. [ex) 6 ->111111, 1..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 DFS와 BFS를 이용해서 풀 수 있다. 부모노드 결국 탐색했던 이전노드의 값이다! 탐색을 진행하면서 방문하지 않은 노드를 방문시 visited 리스트에 부모 노드의 값을 업데이트 한다. sol1) BFS import sys from collections import deque def BFS(Graph,start,visited): queue=deque([start]) visited[start]=1 while queue: V = queue.poplef..

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 처음에 insert를 사용하니 시간초과가 발생했다. import sys input_string=list(sys.stdin.readline().strip()) cursor=len(input_string) N=int(sys.stdin.readline()) for _ in range(N): command=sys.stdin.readline().strip() if 'P' in command: ne..

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 우선순위큐를 이용하여 구현 우선순위큐에서 절댓값으로 우선순위를 지정해서 사용함 (우선순위 지정하여 put : queue.put((우선순위, value))) import sys from queue import PriorityQueue N = int(sys.stdin.readline()) queue= PriorityQueue() for _ in range(N): n=i..

문제 https://www.acmicpc.net/problem/1158 풀이 Sol1 : 리스트 이용 N,K =map(int,input().split(' ')) people_list=[i for i in range(1,N+1)] result=[] index = 1 i=0 while len(people_list)>0: #list의 원소가 남아있을때까지 반복 if i>=len(people_list): i=0 if index%K==0 : result.append(people_list[i]) people_list.pop(i) #K번째 사람 pop else: i+=1 index += 1 print("") - list에 원소를 저장하고 원소 이동할때마다 index를 하나씩 증가함 index가 K의 배수일 경우 po..