본문 바로가기

CS Study/algorithm

 (23)
구현 문제풀이 1. 문자열 집합 ( 백준 14425번 ) 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 직접 작성한 코드) n,m=map(int,input().split()) array=[] array2=[] count=0 for i in range(n): nn=input() array.append(nn) for i in range(m): mm=input() if mm not in array: continue else: count+=1 print(count) 2. 그룹 단어 체커 (백준 13..
다이나믹 프로그래밍 문제 풀이 1. 피보나치 함수( 백준 1003번 ) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 참고 코드) n=int(input()) def fibo(x): if(x==0): return 0 if x==1 or x==2: return 1 if d[x] != 0: return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x] for i in range(n): d=[0]*42 a=int(input()) if(a==0): print(1,end=' ') else: print(fibo(a-1), end=' ') print(fibo(a)) ➡️ 처음에는 재귀를 이용하서 피보나치 수열을 구현..
이진 탐색 문제풀이 1. 수 찾기 (백준 1920 번) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 직접 작성한 코드) n=int(input()) array=list(map(int, input().split())) m=int(input()) targetlist=list(map(int,input().split())) array.sort() def binary_search(array, target,start,end): if start > end: return None mid =(s..
기타 문제풀이 1. 괄호 (백준 9012번) 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 직접 작성한 코드) n=int(input()) for i in range(n): count1=0 count2=0 a=input() result='YES' for j in a: if j=='(': count1+=1 else: count2+=1 if (count2>count1): result='NO' if(count1!=count2): result='NO' print(result) 2. 제로 (백준 107..
DFS & BFS 문제 풀이 1. DFS와 BFS (백준 1260번) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2. 스택 (백준 10828번) 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 직접 작성한 코드) n=int(input()) stack=[] for i in range(n..
정렬 알고리즘 (문제 풀이) 1. 단어 정렬 (백준 1181번) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 참고 답안) n=int(input()) array=[] for i in range(n): array.append(input()) set_list=set(array) new_array=list(set_list) new_array.sort() new_array.sort(key=len) for i in range(len(new_array)): print(n..
그리디 알고리즘 (문제 풀이) 1. 설탕 배달 (백준 2839번) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 직접 작성한 코드) n=int(input()) count=0 k=n five= k//5 k=k%5 three=k//3 k=k%3 while True: if k==0: print(five+three) break elif five 0: n -= 3 p += 1 if n % 5 == 0: p += n // 5 print(p) break elif n == 1 or n == 2: ..
최단 경로 알고리즘 최단 경로 알고리즘이란? - 가장 짧은 경로를 찾는 알고리즘 - 지점은 그래프에서 노드로 표현, 지점 간 연결된 도로는 그래프에서 간선으로 표현 문제 상황 1) 한 지점에서 다른 한 지점까지의 최단 경로 2) 한 지점에서 다른 모든 지점까지의 최단 경로 3) 모든 지점에서 다른 모든 지점까지의 최단 경로 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. - 음의 간선이 없을 때 정상적 동작 - 그리디 알고리즘으로 분류된다. (매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.) - 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다. 다익스트라 알고리즘의 동작 과정 1) 출발 노드를 설정한다. 2) 최단..

티스토리툴바