[백준] 10026번: 적록색약 문제 풀이 파이썬

문제 링크 풀이 방식 bfs 방식으로 적록색맹이지 않은 사람의 영역 갯수를 구한다. visited 를 초기화한 후에 적록색맹의 영역 갯수를 구한다. 전체 코드...

beakjoon백준BFS골드5BFS

[백준] 9095번: 1, 2, 3 더하기 문제 풀이 파이썬

문제 링크 풀이 방식 정수 4의 경우의 수는 7(1+2+4)이고, 5의 경우의 수는 13(2+4+7)인걸 확인 가능하다. 따라서 정수 N의 경우의 수는 (N-3) + (N-2) + (N-1)의 합으로, 다음과 같은 점화식을 세울 수 있다. 점화식 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] dp[n] = sum(dp[i-3:i]) 전체 코드...

beakjoon백준실버3beakjoon

[백준] 11279번: 최대 힙 문제 풀이 파이썬

문제 링크 풀이 방식 힙큐 자료구조를 사용한다. 최소순으로 정렬되는 힙큐 자료구조를 최대힙으로 바꿔준다. 힙큐 자료구조에 정수값과 정수값의 역수를 함께 넣어 역수 기준으로 정렬되도록 한다. 전체 코드...

beakjoon백준힙큐실버2beakjoon

[백준] 1238번: 파티 문제 풀이 파이썬

문제 링크 이번 문제의 태그는 다익스트라, 나에겐 생소한 방식이었기 때문에 다익스트라가 뭔지에 대해 먼저 공부할 필요가 있었다. 다익스트라란? 하나의 정점에서 다른 정점들까지의 최단 거리들을 찾는 최단 경로 알고리즘의 일종이다. 이 때, 힙큐를 함께 사용하여, 해당 정점에서 연결된 정점들 중 거리가 가장 짧은 경로 먼저 계산을 한다. 이렇게 하면 이미 계산딘 경로의 길이보다 더 긴 거리가 있...

beakjoon그래프다익스트라백준골드3beakjoon

[백준] 1504번: 특정한 최단 경로 문제 풀이 파이썬

문제 링크 풀이 방식 각 노드간의 거리를 양방향 그래프로 저장한다. v1와 v2를 포함하는 1부터 N까지의 경로 두가지를 구한다. 1 > v1 > v2 > N 1 > v2 > v1 > N 이 때, 다익스트라를 이용하여 구하며, 최소 거리를 구하기 위해 힙큐를 활용한다. 두가지 루트의 거리 중 최소값을 구한다. 이 때, 최소 거리가 비정상적으로 크다면 v1 혹은 v2가 없는 것으로 간주한다. ...

beakjoon그래프다익스트라골드4백준beakjoon

[백준] 1753번: 최단 경로 문제 풀이 파이썬

문제 링크 풀이 방식 기존 다익스트라 문제에서 K번 정점부터 각 노드간의 거리를 출력하는 문제이다. 이 때, 해당 노드와 연결되어있지 않으면 distance 리스트에는 INF(1e9)로 저장되어있기 때문에, 거리가 INF와 같으면 문자열 'INF'로 대체하여 출력한다. 전체 코드...

beakjoon그래프다익스트라골드5백준beakjoon

[백준] 2096번: 내려가기 문제 풀이 파이썬

문제 링크 풀이 방식 해당 문제는 DP 문제로 점화식은 다음과 같다. maxDP1[i] = arr[i][0] + max(maxDP1[i-1], maxDP2[i-1]) maxDP2[i] = arr[i][1] + max(maxDP1[i-1], maxDP2[i-1], maxDP3[i-1]) maxDP3[i] = arr[i][2] + max(maxDP2[i-1], maxDP3[i-1]) minDP도...

beakjoon백준DP골드4DP

[백준] 1916번: 최소비용 구하기 문제 풀이 파이썬

문제 링크 풀이 방식 기존에 사용해왔던 다익스트라 방식을 사용하면 된다. 지금껏 풀어왔던 다익스트라 문제들과 크게 다를것이 없는 문제이다. 전체 코드...

beakjoon그래프다익스트라골드5백준beakjoon

[백준] 2780번: 비밀번호 문제 풀이 파이썬

그 기계의 모양은 다음과 같다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다. 석원이의 힌트 종이는 다음과 같다. 비밀번호의 길이는 N이다. 비밀번호는 위 그림에 나온 번호들을 눌러서 만든다. 15 라는 비밀번호는 불가능하다. ) 하지만 1236이라는 비밀번호는 가능하다.) 첫 ...

알고리즘실버1beakjoon파이썬DP백준DP

[백준] 21738번: 얼음깨기 펭귄 문제 풀이 파이썬

특수 얼음 깨기 펭귄 게임은 특수 안경이 있어 특수 안경을 끼고 얼음들을 보면 얼음들 간의 연결 관계가 보인다. 특수 얼음 깨기 펭귄 게임에 있는 얼음의 종류로는 지지대의 역할을 하는 얼음과 일반 얼음 총 2가지의 얼음이 존재한다. 지지대의 역할을 하는 얼음의 경우, 빨간색으로 구분 일반 얼음의 경우에는 1개의 지지대만이 연결되어 있어도 얼음이 깨지지 않지만 펭귄이 올라가 있는 얼음은 2개 ...

dpsbeakjoon재귀백준골드5beakjoon

<Baekjoon> #17780 #17837 새로운 게임1,2 c++

map상에는 각 색깔이 저장되어 있고, 각 칸에는 여러 개의 체스가 저장되기 때문에 map에 색을 저장하는 벡터와, 각map에 여러 개의 체스를 저장할 벡터를 만들어야 한다 각각의 체스는 위치 (y,x)와 방향을 가지기 때문에 이 셋을 저장할 구조체를 따로 선언한다 각 체스를 움직일 때, 현재 체스보다 위에 있는 체스들을 함께 움직이기 때문에 현재 움직이려는 체스가 현재 칸에서 몇 번째에 위...

beakjoonalgorithm"삼성SW""삼성SW"

[CodingTest] Beakjoon Q1000

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 출처 메모리 : 18340KB 시간 : 224ms 코드길이 : 220B 언어 : java 11...

CodingTestbeakjoonCodingTest

[백준] 1188번: 음식 평론가 문제 풀이 파이썬

소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다. 선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다. 예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 ...

beakjoon백준골드5최대공약수beakjoon

[백준] 2436번: 공약수 문제 풀이 파이썬

문제 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 ...

beakjoon백준최소공배수최대공약수브루트포스골드5투포인터beakjoon