본문 바로가기

Algorithms63

백준 24416. 알고리즘 수업 - 피보나치 수 1 http://acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 동적 프로그래밍 문제. 처음 접해봤는데, 재귀보다 호출 횟수가 현저히 적어서 신선했다. 문제는 간단해서 주어진 수도 코드를 구현하면 된다. n = int(input()) count_1 = 0 count_2 = 0 def fib_r(n): global count_1 if n == 1 or n == 2: count_1 += 1 return 1 return fib_r(n-1) + fib_r(n-2.. 2022. 6. 22.
백준 14889. 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 개인적으로 굉장히 까다로웠던 문제. 한 팀이 이루어질 수 있는 모든 경우의 수를 구해서, 팀에 속한 i,j와 그렇지 못한 i,j를 분류해서 처리했더니 답은 맞게 나왔으나 시간 초과가 떴다. 그래서 리스트에 팀원의 인덱스를 넣는 게 아닌, 이미 고정된 크기의 배열에서 TF를 이용해 분류하는 방법을 선택해봤다. 그리고 TF를 이용해서 백트래킹을 하려니까 반복문에서 모든 값을 집어넣을 수 없어서, idx 변수를 따로 주고 .. 2022. 6. 21.
백준 14888. 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 삼성 SW 역량 테스트 기출문제라 해서 설레는 마음으로 풀어본 문제 ! 생각보다 까다로웠던 부분이 있었다. 첫째로 C++14 버전 음수 나누기를 따라서, 결과가 (양수 값 // 분모) * -1 식으로 나와야 한다는 점. 파이썬으로 실험해본 결과 그냥 (음수 // -분모) * -1 로 처리하는 것 같은데, 어쨌든 달라서 다시 계산해줘야 했다. .. 2022. 6. 20.
백준 2580. 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 괴랄해 보여서 쫄리지만 생각보다는, '생각보다는' 쉬운 문제. 그래도 아직 어렵긴 하다. 기본적인 dfs에서 N-Queens와 다르게 꼼짝없이 이중 리스트를 사용해야 하는데, 이에 따라 검사하는 방법도 가로, 세로, 스도쿠의 3*3 작은 사각형을 검사해줘야 한다. 개인적으로 사각형 검사 부분이 가장 까다로웠던 것 같다. 기본적인 아이디어는 다음과 같다. 1. 기존 dfs와는 조금 다르게, 빈 공간.. 2022. 6. 20.

티스토리툴바