지민 개발 블로그

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.www.acmicpc.net풀이과정①문제 들여다보기이건 RGB 문제랑 유사한 것 같음. 다만, list의 len이 매번 달라져서 이 부분을 좀 신경써줘야 한다고 생각함. ②아이디어 열기일단 range를 거의 쌩까고 코드를 짜봄역시 IndexError가 떴다. 심지어 print(max(dp[N-1])) 로 해줘야함! 굉장히 멍청한 실수였다. list의 첫 번째와 마지막 부분일 때 예외적으로 dp[i-1][j-1]과 dp[i-1][j]를 비교할 수 없기에 따로 처리를 해주었다.근데 이 코드가 과연? 시간..

https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net풀이과정①문제 들여다보기누가봐도 dp문제다. 보텀업 방식으로 이 문제는 해결될 것이다. ②아이디어 열기이 문제를 풀기 위해서는 max함수를 활용하고 역시 하던대로 반복문을 활용해야한다.dp[i] = max(dp[i],dp[i-1]+dp[i])가 필요함을 느꼈다.그래서 일단 코드를 짜봤는디생각보다 짧게 나왔다.2주전에 한 코드보다 더 좋았다. 그런데 한번 실수를 했었는데,dp[i] = max(dp[i],dp[i-1..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의www.acmicpc.net풀이 과정① 문제 바라보기 관찰을 해보니 점화식 작성이 간단하게 됩니다. 알고보니 피보나치였음! ② 아이디어 열기그럼 보톰업방식으로 해결이 아래와 같이 됩니다.**보톰업방식: 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답이 도출되는 것dp = [0 for _ in range(101)]dp[1] = 1dp[2] = 1dp[3] = 1for i in range(4,101):    ..

https://www.acmicpc.net/problem/1904 1904번: 01타일지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이www.acmicpc.net풀이과정①문제 바라보기 이 문제는 타일링문제로 dp문제 중 하나이다. 저번에 타일링 문제를 풀었었는데 그때 점화식으로 푼 기억이 난다. 사실 dp문제가 점화식으로 많이 풀리긴 하더라..고통을 받으며 점화식을 찾게 되었다.dp[i] = dp[i-1] + dp[i-2] 였던 것임! ②아이디어 열기신나는 마음으로 코드를 짰는데.. 나름 짧아서 예뻤다. 근데 메모리초과가 떴다!! 오마이갓..사실 저 식이 피보나치잖..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.www.acmicpc.net풀이과정①문제 바라보기굉장히 와닿지 않았다. 굉장히 굉장히.. 그래서 recursive로 먼저 코드를 작성해보았다.그런데 문제의 설명대로 역시 15  15 15를 넣을 경우 굉장히 연산 속도가 느렸다.조금 생각을 해보니 위의 코드는 탑다운 방식처럼 재귀를 사용해서 느린 것 같다. 그래서 반복문을 활용하는 보텀업 방식을 사용하면 해결 될 수 있을거라는 생각을 하게 되었다. 그런데 문제는, 값이 abc로 세 ..

문제 풀이:이 문항은 dp문항이다. 처음에 input을 arr list를 만들어 따로 받았는데, 그럴 필요가 없었다.arr로 따로 만들게 된 이유는, 이때까지 풀었던 몇 가지 dp 문항들이 min(dp[i-1] + arr[i],dp[i]) 이런식으로 자꾸 비교하면서 들어오길래 이상하게 생각없이 arr를 무작정 만들었었다. 그런데 해결이 안되니, 근본적인 이유는, 그냥 R일 때 G일 때 B일 때를 모두.. dp로 해보면 된다는 점이었음. '모두'라 함은 작을 수 있는 가능성이 있는 경우를 뜻함. 그래서, 시작이 무엇이니에 따라서 case가 3가지가 나오고 그때마다 그냥 가장 적게 드는 값을 탐색하다보면 답이 나온다. 코드:N = int(input())dp = []for _ in range(N):    dp..

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘이다.1)선택 정렬(Selection Sort) 가장 원시적인 방법'이다. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬이다.2)삽입 정렬(Insertion Sort) 특정한 데이터를 적절한 위치에 '삽입'하는 정렬이다. 삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적..

미로 찾기 문항은 BFS를 이용했을 때 매우 효과적으로 해결할 수 있다.Why? : BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.그러므로 (1,1)지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. from collections import deque# N, M을 공백으로 구분하여 입력받기n, m = map(int,input().split())# 2차원 리스트의 맵 정보 입력받기graph = []for i in range(n):    graph.append(list(map(int,input())))# 이동할 네 방향 정의(상,하,좌,우)dx = [-1,1,0,..

DFS/BFS 는 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘이다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조  안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다.  자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다.삽입(Push): 데이터를 삽입한다.삭제(Pop): 데이터를 삭제한다.스택 (~=박스 쌓기)스택은 선입후출(First In Last Out)구조 또는 후입선출(Last In Fi..

알고리즘 분류)이분탐색, 매개 변수 탐색*매개 변수 탐색(Parametric Search): 이분 탐색을 사용하여 조건을 만족하는 최대값을 구하는 방법이다.*Parametric Search의 Detail은 https://stopmin.tistory.com/31 여기 정리해 놨음. Solution)이진탐색의 정의에 맞게 일단 비교해야 하는 값들을 sorted해서 House에 정리해줬다.start, end 포인트를 1과 가장 멀리 떨어져있는 집 사이의 거리로 설정했다. 그리고 이제 while (start 일단 기준점이 필요하다. house[0]을 기준으로 삼고, 일단 최소 거리 1이니 count = 1로 잡는다.그리고 for문을 돌린다. 집의 개수까지 돌리는데 만약 집의 거리가 기준점+중간값 보다 크거나 같..