백준 알고리즘
1.[Python] 백준 2193_ 이친수
https://www.acmicpc.net/problem/2193이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다. 이친수는 0으로 시작하지않으므로 d0=1이친수에서 1은 두 번 연속으로 나타나지 않으므로 d0=1따라서 di = di-1
2.[Python] 백준 1912_ 연속합
https://www.acmicpc.net/problem/1912이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.dp: i번째 이전의 어느 특정 시점부터 i번째까지 더했을때의 합의 최대값max_n: 특정시점부터 특정 시점까지의 연속합의
3.[Python] 백준 11053_ 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.dp: i번째까지 증가했을때 수열의 최대 길이d = 1\*n 으로 초기화 -> 최소 현재 부터 시작하는 길이 1인 수열이
4.[Python] 백준 11055_ 가장 큰 증가 부분 수열
https://www.acmicpc.net/problem/11055이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.dp: i번째까지 증가했을때 수열의 합의 최대값dp의 초기값은 입력받는 수열 A와 같도록 초기화 해준다(예제)510 90
5.[Python] 백준 1013_Contact
https://www.acmicpc.net/problem/1013이 문제는 입력된 신호가 (100+1+ | 01)+ 패턴을 가지는지 판별하는 문제이다. 문자열의 앞 인덱스부터 판별하여 특정 케이스를 만족하면 만족하는 부분을 제거해나가면서 중간에 중단하지 않고
6.[Python] 백준 2608_로마숫자
https://www.acmicpc.net/problem/2608주어진 두개의 로마숫자를 더하여 아라비아 숫자로 표현하고, 그 아라비아 숫자를 다시 로마숫자로 표현하여 출력하는 문제이다. 로마숫자를 아라비아 숫자로 변환해주는 to_num(s)함수와 아라비아 숫
7.[Python] 백준 2491_수열
https://www.acmicpc.net/problem/2491이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.dp: i번째까지 왔을때 수열의 최대 길이이차원리스트로 하여 d0:증가할때/ d1:감소할때 dp테이블은 처음에 모두 1로
8.[Python] 백준 15988_1, 2, 3 더하기 3
https://www.acmicpc.net/problem/15988이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.di = i를 1,2,3으로 만들 수 있는 가짓수d0 = 0, d1 = 1, d2 = 2, d3 = 4 으로 초기화di
9.[Python] 백준 2631_ 줄세우기
https://www.acmicpc.net/problem/2631이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.(예제)73752614위 예제는 다음과 같이 옮겨 줄 세울 수 있다. 즉, 가장 긴 증가하는 부분수열을 구해서 그 길이를
10.[Python] 백준 18870_ 좌표 압축
https://www.acmicpc.net/problem/18870<틀린 코드 - 시간 초과><맞은 코드>받은 리스트를 집합으로 만들어 중복을 제거해준뒤, 다시 딕셔너리로 만들어줘서 해당 값을 키값으로 찾을 수 있게 구현하였다.
11.[Python] 백준 11657_타임머신+벨만포드 알고리즘 이론
https://www.acmicpc.net/problem/11657출발 노드 설정최단 거리 테이블 초기화다음의 과정을 N-1번 반복\-전체 간선 E개를 하나씩 확인\-각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신\*만약 음수 간선 순
12.[Python] 백준 1495_ 기타리스트
https://www.acmicpc.net/problem/1495이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.di :i번째 곡을 j볼륨으로 만들 수 있는지 여부(1:가능/0:불가능)주석을 통해 최대한 자세히 설명을 적었다.
13.[Python] 백준 1325_ 효율적인 해킹
https://www.acmicpc.net/problem/1325이 문제는 너비 우선 탐색(bfs)을 이용하여 해결하였다.주석을 통해 최대한 설명을 자세히 적어놓았다.
14.[Python] 백준 1068_ 트리
https://www.acmicpc.net/problem/1068이 문제는 깊이 우선 탐색(dfs)을 이용하여 해결하였다.(예제)9\-1 0 0 2 2 4 4 6 64먼저 루트 노드는 root변수에 따로 저장해두고, node리스트의 인덱스 값의 자식 노드 번호
15.[Python] 백준 2841_ 외계인의 기타 연주
https://www.acmicpc.net/problem/2841이 문제는 스택의 개념을 이용하면 해결할 수 있다. 주석을 통해 최대한 자세히 설명을 적어두었다.
16.[Python] 백준 16953_ A->B
https://www.acmicpc.net/problem/16953이 문제는 너비 우선 탐색(bfs)을 이용하여 해결하였다.주석을 통해 최대한 자세히 설명을 적어놓았다.
17.[Python] 백준 1991_ 트리 순회
https://www.acmicpc.net/problem/1991먼저, 트리를 딕셔너리를 이용하여 만들어주고, 트리 순회는 재귀 함수로 진행하였다.(처음에는 재귀함수로 구현할 방법을 생각하지 못해 일일히 구현하려고 했다;)
18.[Python] 백준 1043_ 거짓말
https://www.acmicpc.net/problem/1043이 문제는 집합(set())을 이용하여 문제를 풀면 된다.집합에서 다음의 메소드를 알아두자.add(): 집합에 원소 추가update(): 집합에 원소 여러개 추가 set.union(a,b): a
19.[Python] 백준 1629_ 곱셈
https://www.acmicpc.net/problem/1629시간을 줄여주기 위해 함수를 retrun할때 미리 c로 나눈 나머지를 리턴해준다.마지막 결과값에 c로 나누는것보다 시간을 줄일 수 있다.
20.[Python] 백준 9663_ N-Queen
https://www.acmicpc.net/problem/9663\*\*다음 내용은 유튜브 '바킹독'님의 백트래킹 강의를 듣고 작성한 내용이다. (youtube.com/watch?v=Enz2csssTCs&t=1237s)이 문제는 백트래킹을 이용하여 해결할 수
21.[Python] 백준 1080_행렬
https://www.acmicpc.net/problem/1080\*\*여기서 주의할 점은, a행렬에서 b행렬과 다른 부분을 찾을 때, for문의 범위를 n-2/m-2로 해줘야한다. n,m으로 설정하면 index error가 발생한다.