yeony's story

(+ 클래스 이름은 Main) 1. 입력 ex) 한 줄에 있는 여러 개의 숫자 입력받기 n,m=map(int,input().split()) ex) 한 줄에 있는 여러 개의 문자 입력받기 n,m=input().split() ex) 숫자 배열 입력받기 array=[list(map(int,input().split())) for _ in range(행의개수)] ex) 문자 배열 입력받기 (띄어쓰기 o) array=[list(input().split()) for _ in range(2)] ex) 문자 배열 입력받기 (띄어쓰기 x) array=[list(input()) for _ in range(2)] 2. 출력 print() (1) 배열 생성 array=[[] for _ in ra..

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 문제를 보며 요약한 내용=> 내 위치 : (1,1) 상대 위치 : (n,m) 검은색 = 막힌 길 (0) 흰색 = 갈 수 있는 길 (1) 맵 벗어난 길은 갈 수 없다. 상대 팀 진영으로 가는 가장 빠른 길 -> bfs? 도착못할수도 있다. -> visited[x][y]=-1이면 도착 못한 거! => -1 출력 ..

https://programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 이 문제는 입력받은 문자열의 개수를 이진법으로 바꿨을때의 값이 1이 될 때까지 아래 과정을 반복하는 것! 1. 입력 받은 문자열에서 0을 모두 제거한다. 2. 1의 개수를 이진법으로 변환한다. 3. 이진법으로 변환한 값이 딱 "1"이 될 때까지 위 과정을 반복한다. def solution(s): zero_cnt=0 # 0의 개수 change_cnt=0 # 변환 횟수 while s!='1': # 1. 0 제거 word='' for i in s: if i=='1': word+=i else: zero_cnt+=1 after_cnt=len(..

1. 사사오입 : 4 이하면 버림, 5 이상이면 올림 2. 오사오입 : 5 미만의 숫자는 버림, 5 초과의 숫자는 올림 5일때 처리해주는 방식이 사사오입 방식과 다르다. 5의 앞자리가 짝수 -> 버림 5의 앞자리가 홀수 -> 올림 흔히 파이썬에서 쓰는 round 함수는 오사오입 방식이다. round 함수로 사사오입 방식을 구현하려면? 해당 값이 양수이면 0.5를 더해주고 음수이면 0.5를 빼주면 된다. 왜 위처럼 해야하는 지 이제부터 상세하게 설명해보기! 오사오입 방식은 5의 앞자리수가 짝수일 때 버린다. 이를 해결하기 위해 0.5를 더해주고 빼주는 것이다. 예시를 들면 사사오입 방식대로 2.5를 반올림하면 3이 나와야한다. 하지만 오사오입 방식에서는 2가 나온다. 왜냐하면 5의 앞자리 수가 짝수이기 때..

입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 한다고 해요! 알면서도 매번 코드 구현만 하던 나 자신 반성하며,, 이번 기회에 시간 복잡도에 관련된 내용을 정리하는 포스팅을 해보려고 합니다 ! 알고리즘 시간복잡도는 주로 빅오 표기법을 사용해서 표기합니다. O < (1) < O(logn) < O(N) < O(nlogn) < O(n^2) < O(n^3)

1. 특수 문자 출력하기 He says "It's really good life!"를 출력하려면 \를 이용해야 합니다. 출력하고 하는 문자 앞에 \를 붙여주면 됩니다. print("He says \"It\'s really good life!\""); 2. 두 줄 출력하기 (1) \n 이용하기 print("Hello\nWorld!") (2) print문 이용하기 print("Hello") print("World") 3. 공백 또는 구분자 사용하여 출력하기 (1) 공백을 사이에 두고 출력하기 : 쉼표 이용 print(3,5) (2) 구분자 사용하기 : sep 이용 print(3,5,sep=":") 4. 출력 형식 (1) 변수 포맷 (%d, %s, ..)과 %를 사용한다. %s : 문자열 %c : 문자 %d ..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 시간 복잡도를 생각하지 못하고 bfs로 탐색을 진행했다가 메모리초과 뜸.. 아래 코드의 시간복잡도는 O(N^2) 1초에 N의 범위가 2000 이하여야 쓸 수 있는 코드! 하지만 주어진 데이터 개수는 10만 시간 복잡도를 계산하면 10만 *. 10만 =. 100만 결국 O(N)으로 작성을 해야 함! 시간 제한은 2초 # import sys # from collection..

https://www.acmicpc.net/problem/9095 dp[1] = 1가지 dp[2] = 2 , 1+1 = 2가지 dp[3] = 3, 2+1, 1+2, 1+1+1 = 4가지 dp[4] = 3+1, 2+1+1, 1+2+1, 2+2, 1+3, 1+1+2, 1+1+1+1 = 7가지 (1+2+4) dp[5] = 13가지 (2+4+7) t=int(input()) dp=[0 for _ in range(11)] dp[1]=1 dp[2]=2 dp[3]=4 for _ in range(t): n=int(input()) if n < 4: print(dp[n]) else: for i in range(4,n+1): dp[i]=dp[i-1]+dp[i-2]+dp[i-3] print(dp[i])

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net > dp i%2로 나눠지고 i%3으로 나눠지면 min함수를 이용해서 어떤 경우를 선택해야 최솟값으로 나오는 지 확인해야한다. 위에서 구한 값과 -1을 뺀 값중에서도 어떤 경우를 선택해야 최솟값으로 나오는 지 확인해야 한다. import sys n = int(sys.stdin.readline()) dp = [0 for _ in range(n + 1)] dp[0],..

> dp https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 총 4개 이하의 자연수 제곱수들의 합으로 모든 자연수를 정의내릴 수 있다. N = a^2 + b^2 + c^2 + d^2 dp를 푸는 문제는 항상 규칙이 존재한다. n이 6일때를 생각해보자. i가 1일땐 1이라고 초기화 진행 i=2일때, 2는 1의 제곱수들의 합으로 정의할 수 있음. 2 = 1^2 + 1^2 2 - 1^2 = 1이다. 따라서 dp[1]과..