🍎🍏 — 🍎🍏

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과

2021.01.13

- 목표 - codekodo.tistory.com/26 [코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표 목표 : 최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습 codekodo.tistory.com 다익스트라란? 최단 경로를 탐색하는 알고리즘의 한 종류로 정점들 사이의 가중치를 비교하는 과정을 통해 최단 경로를 탐색한다. 해당 그림에서 정점과 간선의 가중치를 표로 나타내면 다음과 같다. 특정 행에서 특정 열로 이동할 때 발생하는 가중치를 나타낸 표이다. 인접하지 않은 경우 INF, 방향성에 의해 도달할 수 없을 때는 X로 나타내었다. A(여기로) B C D E F..

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표

2021.01.13

- 목표 - 최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습한다. 1. 다익스트라 방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오. [입력 값] 6 7 A B C D E F A B 10 A C 15 B D 12 B F 15 C E 10 D F 1 F E 5 A E [출력 값] A C 15 C E 10 2. 벨만 포드 음의 가중치가 있는 방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오. 만약, 무한 루프가 발생할 경우 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 1932번. 정수 삼각형

2021.01.13

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 해결 방법 이전 문제였던 RGB 거리 문제와 유사하다. dp를 이용할 것이므로 점화식, 즉 규칙을 찾아내야 한다. 첫번째 행은 무조건 자기 자신을 택하므로 제외 두번째 행부터는 i) 가장 좌측 원소의 경우 이전 행의 가장 좌측 원소 ii) 가장 우측 원소의 경우 이전 행의 가장 우측 원소를 무..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 1149번. RGB 거리

2021.01.13

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다. 해결 방법 이 문제의 시간 제한은 0.5초로 짧다. 중첩 반복문을 이용한 브루트 포스의 방법..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 9461번. 파도반 수열

2021.01.13

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 해결 방법 처음 들어보는 새로운 수열이지만 그 규칙은 피보나치와 비슷하다. 피보나치의 점화식이 f(n) = f(n-1) + f(n-2) 였다면 N 1 2 3 4 5 6 7 8 9 P(N) 1 1 1 2 2 3 4 5 7 파도반의 점..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 1904번. 01타일

2021.01.12

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 입력 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 출력 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. 해결 방법 언뜻보면 어려워 보일 수 있다. 하지만 타일의 경우의 수에는 규칙이 있다. N 1 2 3 4 5 6 7 2진 수열의 경우의 수 1 2 3 5 8 13 21 피보나치와 같은 점화식을 가진다. f(n) = f(n-..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 9184번. 신나는 함수 실행

2021.01.12

www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 입력 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. 출력 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다. 해결 방법 dp를 활용한다. 해결 과정 [0][0][0] ~ [20][20][20]의 3차원 배열을 생성하고 각 조건별로 나눈다. 특정 범위 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 1003번. 피보나치 함수

2021.01.12

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. 출력 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. 해결 방법 피보나치 재귀 함수에 관한 문제다. 0과 1이 호출되는 횟수 자체도 규칙이 있음을 알 수 있다. 0 1 2 3 4 5 6 7 0 1 0 1 1 2 3 5 8 1 0 1 1 2 3 5 8 13 위와 같이 호출되는 횟수도 (n-2) + (n-1..

✍️ 코테 준비/Brute Force

[브루트 포스 / Python] BOJ 1436 - 영화감독 숌

2021.01.11

www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 입력 첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다. 해결 방법 정답률 44%의 실버5의 문제이지만 해결하는데 너무 오래 걸렸다. 접근 방식 자체가 잘못되었기 때문이었다. 666 1666 2666 ... 9666 1666666 2666666 ... 9666666 영화 제목은 위와 같은 수일줄 알았다. 하지만 그렇지 않았..

✍️ 코테 준비/Brute Force

[브루트 포스 / Python] BOJ 1018 - 체스판 다시 칠하기

2021.01.11

www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 입력 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. 출력 첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다. 해결 방법 8X8 체스판의 모든 좌표를 탐색해서 해당 위치에 W(혹은 B)가 없는 경우 이를 count 한다. 해결 과정 8X8보..

전체 글

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표

[동적 계획법 1] [C++] 1932번. 정수 삼각형

[동적 계획법 1] [C++] 1149번. RGB 거리

[동적 계획법 1] [C++] 9461번. 파도반 수열

[동적 계획법 1] [Python] 1904번. 01타일

[동적 계획법 1] [Python] 9184번. 신나는 함수 실행

[동적 계획법 1] [Python] 1003번. 피보나치 함수

[브루트 포스 / Python] BOJ 1436 - 영화감독 숌

[브루트 포스 / Python] BOJ 1018 - 체스판 다시 칠하기

티스토리툴바