yeony's story

itertools에 있는 permutation 함수를 사용하여 문제를 풀었더니 당연히 메모리 초과,,, 큽.. import itertools n = int(input()) array = list(map(int, input().split())) temp = list(itertools.permutations(range(1, n + 1), n)) # array[0] = 소문제 번호 if array[0] == 1: # k를 입력받음 -> array[1]에 있음 print(*temp[array[1] - 1]) else: # 임의의 순열을 나타내는 n개의 수를 입력받음 # array[1:n+1] print(temp.index(tuple(array[1:n + 1])) + 1) 직접 구현해야하나 고민했지만, 이것도 마..

dfs만을 이용하면 시간초과가 나는 문제 다이나믹 프로그래밍을 이용해야 한다. 이중 for문으로 탐색을 진행한다. 오른쪽, 아래로만 이동가능하며 dp[n-1][n-1]에 경로의 수가 저장되어 있다. N=int(input()) array=[list(map(int,input().split())) for _ in range(N)] # 오른쪽이나 아래로만 이동 가능 # 0이 종착점 answer=0 dp=[[0]*N for _ in range(N)] dp[0][0]=1 for i in range(N): for j in range(N): if i == N - 1 and j == N - 1: # 끝에 도달했을 때 print(dp[i][j]) break cnt = array[i][j] # 오른쪽으로 가기 if j + ..

https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 처음엔 함수를 만들어서 하려고 했는데 굳이 그렇게 할 필요 없을 것 같아서 (사실 재귀함수보다 반복문이 더 편함..) 반복문을 사용하여 다이나믹 프로그래밍 기법으로 문제를 해결했다! t = int(input()) array = [0 for _ in range(68)] array[0] = 1 array[1] = 1 array[2] = 2 array[3] = 4 for _ in ..

문제에서 주어진 예시를 토대로 돌아가는 방식을 이해하기 위해 위와 같이 그림을 그려봄. 입국심사대가 1개일 경우에는 반복문을 돌릴필요 없이 m명을 곱해주면 된다. 입국심사대가 여러 개 일 경우가 문제이다. 이분 탐색 문제라고는 생각도 못했는데 이분탐색을 이용하여 푸는 문제였다 0_0 ! 내가 생각했던 방식으로 구현하려고 하니 머리가 지끈거렸는데 이분 탐색을 이용하면 쉽게 구할 수 있었다 ㅎ .. cnt=0 for time in Times: cnt+=mid//time -> 이 식을 이용하면 되는데 이 식을 떠올리지 못했다... 흑 n=2, m=6 Times=[7,10]의 예시로 들어보면 일단 최솟값은 28초이다. mid를 28초라고 치자. 위 반복문이 돌아가는 걸 확인하면 28//7 = 4 28//10 =..

dp는 항상 어렵다 ^^... →, ↓의 두 방향으로 움직일 수 있을 때 (1,1)에서 (n,m)까지 도달하는 경우의 수는 dp[x][y]= dp[x-1][y] + dp[x][y-1] 해결할 수도 있다. →, ↓, ↘의 세 방향으로 움직일 수 있을 때, (1,1)에서 (n,m)까지 도달하는 경우의 수는 dp[x][y]= dp[x-1][y] + dp[x][y-1] + dp[x-1][y-1] 위 점화식을 이용하여 구할 수 있다. 즉 갈 수 있는 방향에 따라 더해지는 인수가 달라지는 것을 유의하기 dp[1][1]에 1을 넣어서 초기화한 후 해당 점화식을 실행시킨다. n=3, m=2이면 0 0 0 0 1 1 0 1 3 0 1 5 n, m = map(int, input().split()) dp = [[0 for ..

전형적인 bfs 함수 문제! 문제에서 주어진 예제의 맵은 아래와 같다. 0은 벽, 1은 상어 이 문제에서 원하는 것은 안전거리가 가장 큰 칸을 구하는 것 안전거리가 무엇을 의미하느냐! 해당 칸과 가장 가까이 있는 아기 상어와의 거리를 의미한다. 상어가 1마리면 구하기 쉬웠을 텐데 상어가 여러마리 존재하니까 그걸 어떻게 해결해야 하느냐가 관건이었던 문제다. bfs를 이용하여 처음에 상어의 위치들을 먼저 큐에 넣고 시작한다. (1,3) (3,1) (5,4) 를 각각 큐에 먼저 넣는다. 그리고 나서 (1,3) 위치에 있는 상어 주변 8방향을 살펴보고 0인 곳은 array[1][3]+1을 더해준 값을 넣어준다. 0이 아니면 패쓰! 이런식으로 하면 된다! (간단) dfs로 풀 수 없는 이유는 상어가 여러 마리 존..

중간값만 이용하면 손쉽게 풀 수 있는 문제! divmod 함수를 이용하면 몫과 나머지를 한 번에 구할 수 있다는 것도 꼭 기억해두자! n이 짝수이면 아래와 같이 n//2-1 값이고 n이 홀수이면 아래와 같이 n//2+n%2-1 값이다. 코드는 아래와 같다. n=int(input()) array=sorted(list(map(int,input().split()))) a,b=divmod(n,2) print(array[a+b-1]) 처음에는 중간값, 왼쪽, 오른쪽 값을 이용하면 되는 줄 알았는데 그게 아니었다 ^^

다이나믹 프로그래밍 기법을 사용하여 푸는 피보나치 수열 문제 시간은 68 ms 나옴! n이 3 이하면 1을 출력하고 프로그램 종료 n이 4 이상이면 피보나치 수열 기법을 적용한다. n = int(input()) if n < 4: print(1) exit() else: f = [0 for _ in range(n + 1)] for i in range(1, 4): f[i] = 1 for i in range(4,n+1): f[i]=f[i-1]+f[i-3] print(f[n]) 코드 양을 좀 줄여봄! 배열의 크기를 미리 주어진 최대 크기만큼 잡아주고 시작함! 그러면 for문을 덜 돌려도 되고 if else문을 쓸 필요가 없음! f = [0 for _ in range(117)] f[1], f[2], f[3] = 1..

출처 https://www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%ED%95%B5%EC%8B%AC-%EC%9B%90%EB%A6%AC-%EA%B8%B0%EB%B3%B8%ED%8E%B8/dashboard 스프링 핵심 원리 - 기본편 - 인프런 | 강의 스프링 입문자가 예제를 만들어가면서 스프링의 핵심 원리를 이해하고, 스프링 기본기를 확실히 다질 수 있습니다., 스프링 핵심 원리를 이해하고, 성장하는 백엔드 개발자가 되어보세요! 📢 www.inflearn.com 순수한 DI 컨테이너 순수한 DI 컨테이너인 AppConfig는 요청을 할 때 마다 객체를 새로 생성한다. 고객 트래픽이 초당 100이 나온다면 초당 100개 객체가 생성되고 소멸된다. 즉 메모리 낭비..

출처 https://www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%ED%95%B5%EC%8B%AC-%EC%9B%90%EB%A6%AC-%EA%B8%B0%EB%B3%B8%ED%8E%B8/dashboard 스프링 핵심 원리 - 기본편 - 인프런 | 강의 스프링 입문자가 예제를 만들어가면서 스프링의 핵심 원리를 이해하고, 스프링 기본기를 확실히 다질 수 있습니다., 스프링 핵심 원리를 이해하고, 성장하는 백엔드 개발자가 되어보세요! 📢 www.inflearn.com 다형성 https://eboong.tistory.com/407 [Ch2] 객체 지향 프로그램, 객체 지향 특징 (상속,다형성,추상화,캡슐화), 오버라이딩 및 오버로딩 > : 초기에는 프로그램의 규모가 ..