Seung's Learning Record

난이도 : 실버2 소요시간 : 27m 사용한 풀이법 : DP 풀이 과정 입력받은 문자열을 정수형 리스트 arr[]로 변환 dp[]에는 해당 인덱스에서 가질 수 있는 최대값을 넣는다 dp[i-1]+arr[i]가 음수일 경우 최대값 생성에 방해가 되므로 해당 dp값은 0으로 초기화 원래는 여기서 풀이를 끝낼라했는데 모두 음수일 경우를 고려안하게 생각나서 dp첫번째 조건문 뒤에 arr값을 dp값으로 초기화 해주는 코드 추가 ⇒ 내가 생각해도 좀 후진 코드..ㅎ 원래는 max(dp)를 하려했으나 위 코드 추가되면서 max(arr)로 변경 다른 풀이 입력받은 문자열을 정수형 리스트 arr[]로 변환 현재합과 최대합 연산용 변수 선언 arr을 돌면서 해당 인덱스와 해당 인덱스에 현재합을 더한 것중 max를 현재합에..

난이도 : 실버2 소요시간 : 48m 사용한 풀이법 : DP 풀이 과정 dp용 리스트 선언 각 인덱스에는 1로만 표현했을경우의 개수를 넣는다. 즉, 인덱스 번호를 그대로 대입! 루프를 돌면서 DP탐색 시작 인덱스 번호보다 작은 제곱 수 중에서 가장 큰 값을 찾는다. 현재 인덱스 번호에서 해당 제곱 수를 뺀 인덱스 번호에 +1을 한 후, 대소비교를 진행한다. ex) dp[10] = dp[10-33]+1 = dp[1]+1 (11 + 3*3, 2개!) +1을 하는 이유는 앞선 dp[]값에 제곱 수의 경우가 하나 추가되는 것이기 때문 작성 코드 import math N = int(input()) dp = [x for x in range(N+1)] for i in range(1, N + 1): for j in r..

난이도 : 실버3 소요시간 : 31m 사용한 풀이법 : DP 풀이 과정 dp용 리스트 선언 후 0으로 초기화 dp 리스트는 인덱스 숫자가 1이 되기까지의 최소연산횟수를 저장하는 용도 2~n+1까지 루프 실행 dp[i] = dp[i-1]+1 : i번째 수는 i-1번째 수의 dp값에 +1을 한것을 디폴트로 둔다 만일 i가 2나 3으로 나누어 떨어진다면, i에 2를 나눈 몫의 수에 해당하는 dp값과 디폴트값을 비교하여 최소값을 선택한다 작성 코드 n=int(input()) dp = [0]*(n+1) for i in range(2,n+1): dp[i] = dp[i-1]+1 if i%2 == 0 : dp[i] = min(dp[i],dp[i//2]+1) if i%3 == 0: dp[i] = min(dp[i],dp[..

난이도 : 실버3 소요시간 : 23m 사용한 풀이법 : DP 풀이 과정 dp[1] = 1 => 1 dp[2] = 1+1, 2 => 2 dp[3] = 1+1+1, 1+2, 2+1, 3 => 4 dp[4] = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 => 7 위의 식을 잘 보면 1로 시작하는 건 곧 1+3 인거라서 3을 이루는 덧셈의 경우의 수, 즉 dp[3]만 알면 됨 2로 시작하는건 2+2라서 dp[2]만 알면되고 3으로 시작하는건 dp[1]만 알면 됨. dp[5]를 예시로 들어보자 1+…. 일때는 4를 이루는 경우들만 알면 됨 ⇒ dp[4] == dp[5-1] 2+…. 일때는 3을 이루는 경우들만 알면 됨 ⇒ dp[3] == dp[5-2] 3+…. 일때는 2를 이루..

난이도 : 실버1 소요시간 : 1h 17m 사용한 풀이법 : DP 풀이 과정 풀이과정(백트래킹) 각 요소[i][j]는 대해서 [i+1][j],[i+1][j+1]만 더할 수 있음 해당 위치에서 이동가능한 경로를 인자로 해서 함수 재귀 진행 인자가 n과 같아지면 결과갑 리스트에 삽입 모든 경우의 수 탐색 후 리스트의 max를 출력하면 정답!! 이긴 한데 메모리 초과 뜸 풀이과정(DP) 위에꺼에서 아래꺼를 더하는 방식이 아닌 아래꺼에서 위에 값을 참조해오는 것으로 변경 =>메모리 손실 방지 참조 방식은 총 3가지 행의 첫번째 인자일 경우, 바로 위 행의 첫번째 인자값에 더하면 됨 ([i-1][0]) 행의 마지막 인자일 경우, 바로 위 행의 마지막 인자값에 더하면 됨 ([i-1][-1]) 행의 중간일 경우, 바..

난이도 : 실버2 소요시간 : 57분 사용한 풀이법 : dfs_재귀, bfs_큐 풀이 과정 입력받은 n값에 대한 탐색용 배열 생성 후 false 초기화 bfs, dfs 각각의 방문 탐색용 배열 생성 후 false 초기화 m에 대해 반복문 돌리면서 입력된 값들에 해당하는 인덱스 값 True 변환 각각의 행의 값들 중 True값은 연결된 엣지의 번호를 뜻함 ex) 1번 행의 3,4열이 true이면, 1-3/1-4 연결된 것! bfs는 큐를 이용한 풀이 python 특성상 queue보다 deque가 효율적이라서 deque사용 dfs는 재귀를 이용한 풀이 스택으로 할라다가 실패함ㅎ.. 작성 코드 from collections import deque n,m,v = map(int, input().split(' ')..

난이도 : 실버2 소요시간 : 58분 사용한 풀이법 : 백트래킹 풀이 과정 1. 현재 원소 위치와 총합을 매개변수로 하는 func()정의 2. 현위치 변수가 n과 같고, 총합이 s와 같은 경우에 카운트 후 리턴 3. 조건 미 충족 시, func() 재귀 4. 재귀는 다음 위치의 수를 더하는 경우와, 더하지 않는 경우 두가지로 진행 5. S가 0일 때, 모두 더하지 않은 경우를 카운트에서 제외시켜야 함. 작성 코드 #include using namespace std; int n, s; int arr[30]; int cnt = 0; void func(int cur, int tot){ if(cur == n){ if(tot == s) cnt++; return; } func(cur+1, tot+arr[cur]);..

난이도 : 골드5 소요시간 : 47분 사용한 풀이법 : bfs 풀이 과정 1. color 입력 받는 동시에 배열에 삽입 2. for문 돌면서 미방문한 곳 발견 시 bfs() 호출 3. bfs()함수에서는 호출 된 부분의 색과 동일한 곳만 탐색 4. 탐색이 끝나면 normal++ 후 bfs 재호출 5. color배열 탐색 종료 후, 적록색약 버전 카운트위해 vis[][] 0으로 재초기화 6. color배열의 'G'를 'R'로 대치 7. bfs()호출 및 blind++과정 반복 8. normal과 blind 각각 출력 작성 코드 #include #include #include using namespace std; queue Q; char color[101][101]; int vis[101][101]; int..

난이도 : 실버2 소요시간 : 1시간 9분 사용한 풀이법 : bfs,queue 풀이 과정 1. 테스트 케이스 시작 때 마다 vis[][], bc[][] 배열 0으로 초기화 2. 배추 위치 입력 들어올 때 마다 bc[][]배열 1 삽입 3. for문 돌면서 방문 이력이 없으면서 배추가 있는 곳을 만나면 bfs 실행 => 하나의 배추 군단이 끝나면 bfs종료 후, cnt++됨 4. cnt값 출력 작성 코드 #include #include #include using namespace std; queue Q; int bc[50][50]; int vis[50][50]; int t,n,m,k,x,y; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int d..

해당 문제를 풀기 위해 필요한 사전 지식으로는 아스키코드와 배열정도일 것이다. 당장에 구글에만 쳐봐도 정답 코드가 넘쳐난다. 그러던중 바킹독님의 풀이가 유독 눈에 띄어서 정리할 겸 가져와봤다. #include #include using namespace std; int main(void){ int arr[26]={0}; string s; cin >> s; for(auto c : s) arr[c-'a']++; for(auto i : arr) cout