알고리즘 16

[삼성SW테스트 준비] 3. 큐, 스택, 덱

학습자료: 알파카고수님의 블로그(https://m.blog.naver.com/wpghks7/221584442182) [파이썬으로 시작하는 삼성 SW역량테스트] - 3. 큐, 스택, 덱 이번에는 큐(Queue)와 스택(Stack) 그리고 덱(Deque)에 대해서 간단한 개념과, 큐와 스택, 덱 사용법에 ... blog.naver.com 1. 큐(queue) 먼저 들어온 데이터가 먼저 나가는 자료 구조(FIFO) 큐에서 주로 사용하는 연산 4가지 1. push : 큐의 가장 마지막에 데이터를 넣음 2. pop: 큐의 가장 앞의 데이터를 제거함. 3. front : 큐의 가장 앞의 값을 확인하는 연산 4. empty: 큐가 비어있는지 확인하는 연산 큐를 구현하기 위해 파이썬 상의 queue 모듈을 사용하면 된..

[알고리즘 공부] 3. 완전 탐색(brute force)

참고 : 완전 탐색(Brute-force Search) 모든 문제를 푸는 데 있어서 가장 쉽고 간단한 방법부터 짚고 넘어가 봅시다. 완전탐색, 브루트포스(Brute... blog.naver.com 완전 탐색(Brute force)는 가능한 경우를 모두 탐색하는 것이다. 틀릴 가능성은 적지만, 시간이 최대로 든다. 완전 탐색 시간을 줄이기 위해 정렬과 함께 사용하는 경우가 있다. SW 검정 시험 시, 우선 완전 탐색으로 접근한 후 성능 개선을 위해 다른 알고리즘을 사용하는 방식이 바람직하다. 연관 문제: SWEA- 5203. 베이비진 게임 백준 - 단계별 풀기 (https://www.acmicpc.net/step/22) 브루트 포스 단계 체스판을 만드는 모든 경우를 시도하여 최적의 방법을 찾는 문제 www..

[백준]11729. 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 이 문제도 옮긴 횟수 K의 규칙성은 알겠는데, 이동하는 것을 출력하는 부분에서 막혀 한참 고민하다 블로그를 찾아보았다. 저번에 별찍기 문제에서도 도움을 받은 분이었는데, 하노이 탑이 왜 재귀 함수를 사용해서 풀어야 하는 문제인지 단계별로 그림과 함께 설명해주셔서 이해하기 쉬웠다.(https://mgyo.tistory.com/185) '하노이의 탑' 이해하기 (feat. 재귀 함수) 들어가며 하노이의 탑 문제 소개 문제 정의 아이디어 얻기 아이디어..

[백준] 2447. 별 찍기 - 10

2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 이번 문제는 정말 어려웠다...! 한참을 고민해도 답을 찾지 못해서, 푸신 분들의 블로그를 찾다가 재귀를 활용해 굉장히 간단하게 구현하신데다 설명도 이해하기 쉽게 써주신 분의 블로그를 참조해 문제를 풀 수 있었다!(https://mgyo.tistory.com/183) [백준] 2447번 별찍기 문제 재귀 함수 이용해서 풀기 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 ..

[백준] 17478. 재귀함수가 뭔가요?

17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 풀이 처음 봤을 때는 '이게 뭐람?' 싶었지만 출력 예시를 잘 뜯어보면 재귀를 사용해서 풀 수 있는 쉬운 문제! 앞의 '____'(----가 아니다! 처음에 ----인 줄 알고 이걸로 풀었더니 틀렸었다.) 의 개수가 몇 개씩 늘어나는지, 어떤 문장이 몇번 반복되고 있는지를 체크해보며 풀면 된다. #17478 재귀함수가 뭔가요? def recursion(N, lines): print(lines + '\"재귀함수가 뭔가요?\"') if N > 0: print(lin..

[백준] 4948. 베르트랑 공준

4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 처음에 이렇게 풀었는데 시간 초과가 났다 # 4948 베르트랑 공준 import math def isPrime(n): cnt = 0 for num in range(n + 1, 2 * n + 1): sq = int(math.sqrt(num)) flag = False for i in range(2, sq+1): if num % i == 0: flag = True break if flag is True: continue else: cnt += 1 return ..

[백준] 11653. 소인수분해

11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 원리는 N을 나누어 떨어지게 하는 수가 소수인지 여부를 판별하고, 소수이면 해당 수를 출력한 뒤, N에는 해당 소수로 나눈 몫을 저장해 N이 1이 될 때까지 반복문을 돌리며 나누는 소수를 출력하도록 했다. 하지만 내 생각보다 시간이 많이 걸렸다. 제곱근을 안쓰고 2부터 num까지 수로 모두 num을 나눠서 소수를 판별했기 때문일 것이다. # 11653 소인수분해 (2192ms) N = int(input()) cnt = 0 while N > 1: for num in range(2, N+1): flag = False if N % num == 0: for z in range(2, num)..

[백준] 2581. 소수

2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 이것도 2부터 num까지 num을 나누어 소수인지 여부를 판별했다(매우 비효율적인 방법이다. 테스트케이스가 많은 예시일 때 시간초과 나기 쉽다.) 소수의 합과 소수 중 최솟값은 파이썬 내장함수(sum()함수, min()함수)를 이용했다. 시간은 588ms, 메모리는 30840KB가 나왔다. # 2581 소수 M = int(input()) N = int(input()) arr = [] for num in range(M, N+1): flag = False if num == 1..

[백준] 1978. 소수 찾기

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net flag를 사용해서 주어진 숫자들이 소수인지 여부를 확인하면 되는 문제였다. 테스트케이스가 많지 않아서 그냥 2부터 a까지 모든 숫자들로 다 나눠보아도 시간이 그렇게 많이 들지 않았다. (하지만 뒤로 갈수록 테스트 케이스가 많아져서 이 방법대로 풀 수는 없었다. 그래서 제곱근이나 에라토스테네스의 체를 찾아보고 적용해야만 했다.) # 1978 소수 찾기 N = int(input()) arr = list(map(int, input().split())) cnt = 0 for a in arr: flag = False if a == 1: ..

[백준] 4673. 셀프 넘버

4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net '생성자가 없는 셀프 함수를 찾아라'가 문제였기 때문에, 1부터 10000까지 숫자 중 생성자가 있는 수를 찾아서 중복을 허용하지 않는 set 자료형에 넣어두고, 다시 반복문을 돌리며 1부터 10000까지 숫자 중 해당 set에 포함되지 않은 숫자를 찾는 방법으로 풀었다. 평소라면 자리수를 세기 위해 파이썬 내장 함수 str()을 이용해 숫자를 문자로 바꿔서 했을 테지만, 왠지 수학으로 접근해서 푸는 방법이 있을..