본문 바로가기
반응형

Algorithm296

[Python] 백준 9461번 - 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 혼자 힘으로 풀었는가? : O 알고리즘 유형 - 수학 - 다이나믹 프로그래밍 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1.. 2022. 11. 12.
[Python] 백준 9375번 - 패션왕 신해빈 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 혼자 힘으로 풀었는가? : X (구글에 검색해봄) 알고리즘 유형 - 수학 - 자료 구조 - 조합론 - 해시를 사용한 집합과 맵 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거.. 2022. 11. 11.
[Python] 백준 2579번 - 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있.. 2022. 11. 10.
[Python][이코테] 최단경로 / 다익스트라 알고리즘(1) 컴퓨터공학과 학부 수준에서 주로 사용할 수 있는 최단 경로 알고리즘은 3가지가 있다. 다익스트라 알고리즘 플로이드 워셜 벨만 포드 이중 다익스트라 알고리즘에 대해서 2번에 걸쳐 공부해보도록 한다. 참고로 최단경로 알고리즘은 앞서 배운 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 여러 노드가 있고, 특정 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘이다. 음의 간선이 없어야 하며, 실제 지도앱에서 길 찾기를 사용할 때 쓰이는 알고리즘이다. 방법은 다음과 같다. 출발 노드를 정한다. 최단 거리 테이블을 초기화 한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 .. 2022. 11. 9.
반응형

티스토리툴바