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] 객체 지향 프로그램, 객체 지향 특징 (상속,다형성,추상화,캡슐화), 오버라이딩 및 오버로딩 > : 초기에는 프로그램의 규모가 ..

출처 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] 객체 지향 프로그램, 객체 지향 특징 (상속,다형성,추상화,캡슐화), 오버라이딩 및 오버로딩 > : 초기에는 프로그램의 규모가 ..

출처 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 loC (Inversion of Control) : 제어의 역전 : 기존 프로그램은 구현 객체가 스스로 서버 구현 객체를 생성하고 연결, 실행까지 하며 모든 제어 흐름을 스스로 조종했다. 그러나 AppConfig가 등장하고 난 이후로는 AppConfig가 프로그램의 제어 흐름을 조종한다. 따라서 구현 객체(OrderServiceImpl)는 인터페이스들을 호출은 하지만 어떤 구현 객체들이 실행되고 있는지를 모른다. DI (Dependency Injection) ..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 정사각형을 찾으려면 다이나믹 프로그래밍을 사용해야 한다. ** 정사각형 변의 길이를 구하는 방법 ** 1. 해당 칸이 1로 채워져있어야 한다. 2. array[i-1][j], array[i][j-1], array[i-1][j-1] 중에서 가장 작은 값을 array[i][j]와 더해서 array[i][j]의 값을 갱신한다. >> 정사각형이 되려면 현재 위치를 기준으로 한칸 위(i-1, j), 왼쪽으로 한칸 옆(i,j-1), 대각선 기준으로 왼쪽 위 (i-1, j-1)이..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이렇게 보면 일정한 규칙들을 찾아낼 수 있었다. 표로 정리해보니 아래와 같이 나왔고 다이나믹 프로그래밍을 사용하면 손쉽게 값을 구해낼 수 있었다. ''' 조건 1. 덧셈의 순서가 바뀐 경우 > 다른 경우로 센다. 조건 2. 한 개의 수를 여러번 쓸 수 있다. 출력 : 1000000000으로 나눈 나머지를 출력한다. ''' n, k = map(int, input().split()) array = [i for i in range(0, n + 1)] dp = [[0 for _ in range(n)] for _ in range(k..

문제 이해를 못해서 한참 헤맸던 문제 ㅠ..ㅠ 부피가 A,B,C 리터인 물통 3개가 있다. 처음에는 C 리터인 물통만 가득 채워져있다. 물을 옮길땐 조건이 있다. 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 사실 위 문장을 제대로 파악하지 않고 넘어가서 정말 헤맸던 문제다. 예시를 들어서 설명해보면 8,9,10 리터인 물통 3개가 있다고 가정한다. C물통에서 A물통으로 물을 옮기려면 A물통을 가득채우거나 또는 C물통이 빌때까지 부어야하는데 A물통이 C물통보다 용량이 작으므로 이때는 C물통에서 A물통으로 8리터를 옮긴다. 그러면 C리터에는 2리터의 물만이 남게 된다. 만약 B물통에 5리터, C 3리터가 남아있다고 가정한다. B물통를 가득채우려면 4리터가 필요하다. 그러나 C물통..

https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 처음에 소수 구할때 에라토스테네체 방식을 떠올리지 못했다 ㅎㅎ... 왜 항상 떠올리지 못하는 걸까.. 이런 바부.. 심지어 이렇게 정리까지 해놓고.. https://eboong.tistory.com/398 [n15965] k번째 소수 in python 무작정 for문을 돌리게 되면 시간초과가 날 것 같았다. 그래서 에라토스테네스의체를 이용하여 문제를 풀었다. 에라토스테네스의 체에 대한 이해 먼저 해..

이분탐색으로 풀어야하는 문제 인출금액(k)와 인출횟수(cnt)의 값은 반비례한다는 것에 주목해야 한다. 통장에서 인출하는 금액의 값이 이용금액보다 모자라게 되면 남은 금액은 통장에 집어넣고 다시 k원을 인출한다. 그러면 인출하는 횟수는 늘어나게 된다. 따라서 인출하는 금액의 값이 인하되어야 인출하는 횟수를 늘릴 수 있기 때문에 반비례 관계라고 말할 수 있다. 계산한 cnt (인출횟수)의 값이 m값보다 작으면 -> k의 값을 감소시켜야하므로 right=mid-1 cnt의 값이 m값보다 크거나 같으면 -> k의 값을 증가시켜야하므로 left=mid+1 # 1/12일 n, m = map(int, input().split()) array = [int(input()) for _ in range(n)] left =..

이분탐색으로 풀어야하는 문제 인출금액(k)와 인출횟수(cnt)의 값은 반비례한다는 것에 주목해야 한다. 통장에서 인출하는 금액의 값이 이용금액보다 모자라게 되면 남은 금액은 통장에 집어넣고 다시 k원을 인출한다. 그러면 인출하는 횟수는 늘어나게 된다. 따라서 인출하는 금액의 값이 인하되어야 인출하는 횟수를 늘릴 수 있기 때문에 반비례 관계라고 말할 수 있다. 계산한 cnt (인출횟수)의 값이 m값보다 작으면 -> k의 값을 감소시켜야하므로 right=mid-1 cnt의 값이 m값보다 크거나 같으면 -> k의 값을 증가시켜야하므로 left=mid+1 # 1/12일 n, m = map(int, input().split()) array = [int(input()) for _ in range(n)] left =..

https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net 이 문제는 울타리의 최소 개수를 구하는 문제가 아니라는 것을 감안하면 쉽게 풀 수 있었던 문제입니다.. 흡 양은 이동할 능력이 없기 때문에 움직일 수 없고 늑대만이 인접한 칸을 자유롭게 넘나들수 있습니다. 인접한 칸이라는 뜻은 변을 공유하고 있다는 뜻과 동일함다. . : 빈칸 s : 늑대 w : 양 d : 울타리 울타리를 어떻게든 설치해도 늑대가 양이 있는 칸으로 이동할 수 있다면? > 0 을..

게시글 참조 출처 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 추상(인터페이스)에만 의존하게끔 설계하여 DIP, OCP 위반 방지하는 방법 >> AppConfig 설계 AppConfig = 공연 기획자 역할. : 애플리케이션의 전체 동작 방식을 구성(..

자동완성 Command + Enter test class 만들기 command + shift + T 생성자 자동 생성 (generate -> constructor) control + Enter (); 자동 완성하기 command + shift + Enter 변수명 자동 완성 new 생성자() 작성 후 커서를 맨 앞으로 옮긴 다음 command + option + v println -> sout soutv (변수명 포함 출력문) soutm (메소드 포함 출력문) main -> psvm for 문 자동생성 -> iter 해당 생성자 코드로 바로 옮겨지는 단축키 command + B 위치 상관없이 엔터 shift + Enter 클래스 찾기 command + o 과거 히스토리 보기 command + E Extr..

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 게시글 참고 출처 강의 링크 첨부! 강의를 들으면서 몰랐거나 얕게 알고 있었던 부분들 중심으로 게시글 작성합니다 +_+ Enumeration Type (열거 타입) : 요일, 계절과 같이 한정된 데이터만을 ..

(Unified Modeling Language : 객체 모델링 언어 또는 통합 모델링 언어) - 시스템 설계, 요구분석, 구현 등의 과정에서 사용되는 모델링 언어 - 산출물을 명세화, 시각화, 문서화 할 때 사용하는 언어 건물을 짓기 위한 설계도와 비슷한 역할! - UML의 목적 : 하나의 시스템을 표현하기 위한 표준적인 방법을 제공 즉 표기법의 표준화를 위한 모델링 언어 시스템을 여러가지 시각에서 볼 수 있도록 뷰를 제공한다. 이러한 뷰의 집합을 모델이라고 한다. - UML을 사용하는 이유 : 개발자끼리 설계 개념에 대한 의견을 주고 받을 때 굉장히 편리하다. 대규모 소프트웨어 구조의 로드맵을 만들 때 유용하다. - UML의 종류 : UML은 크게 구조와 행위, 두 가지의 다..

문제출처 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net in Java HTML 삽입 미리보기할 수 없는 소스 주사위 회전 시 주사위의 윗면, 앞면, 오른쪽면을 각각 1,2,3 으로 숫자를 지정해준다. 그러면 필연적으로 아랫면, 뒷면, 왼쪽면은 각각 6, 5, 4가 되어야한다. 왜냐하면 일반적인 주사위는 마주보는 양면의 합이 7이 되어야하기 때문이다. 이를 이용하면 쉽게 문제를 ..

ㅎr.... dp는 왤케 어려운걸까.. 머리가 돌아가지 않는다아... 이 문제 딱 보는 순간 dfs 문제라는 걸 직감하였디! 그래도 문제 풀면 풀수록 나아지는 게 느껴져서 행복하다.. (물론 아직 갈길이 멀긴 하지만!) 이 문제는 처음부터 이해를 잘못했었다.. 역시 나답다 ^_^ 현재 높이보다 작은 곳으로 이동하는건데 가장 작은 높이들만 찾아서 이동하는 건줄 알았다 ^0^.. 예시를 가지고 풀이 시작! 총 3가지의 경우의 수가 있다! 1번째 경로 50 -> 45 -> 37 -> 20 -> 17 -> 15 -> 10 0 0 0 1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 2번째 경로 50 -> 45 -> 37 -> 32 -> 20 -> 17 -> 15 -> 10 2 2 ..