이숭간 공부기록

www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제유형 : 정렬 문제핵심 : 삽입정렬로 시간복잡도 O(n^2)을 가진다. 내코드: (삽입정렬) n = int(input()) array = list(int(input()) for _ in range(n)) for i in range(1, n): # 1,2,3,4 for j in range(i, 0, -1): # 1,2,3,4/2,3,4 if array[j] < array[j - 1]: array[j - 1], ar..

www.acmicpc.net/source/26224365 로그인 www.acmicpc.net 문제유형 : DFS/BFS _ connected component찾기 문제핵심 : 한칸의 땅을 노드로 하고 상하좌우로 연결을 갖는 그래프라고 생각하고 각 노드마다 DFS를 수행하여 처음 DFS를 시작한부분에서만 카운트 DFS수행방법 : 하나의 노드는 상하좌우로 연결되어있다고 생각하고 해당 노드가 1이면서 방문되지 않았을때 ( 배추가 심어져있으면서 방문전이면 ) 방문처리+ 상하좌우로 움직여서 다시 해당노드에서 재귀적으로 DFS수행 그래프는 2차원배열로 구현한 좌표평면의 형태이며, 움직일때마다 움직인곳이 좌표평면을 넘어가면 안되므로 그부분만 예외처리를 해주면된다. 처음 DFS를 시작한부분에서만 카운트하는 방법 : D..

순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 하나씩 확인 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터 탐색 ( 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정한다.) 단계마다 절반씩 줄어드는 알고리즘의 시간복잡도는 보통 로그N 내코드 _ 잘못됨 ( 완전탐색이므로 시간초과남 ) n,m = map(int, input().split()) input_list = list(map(int, input().split())) for i in range(max(input_list), 0, -1): count = 0 for j in input_list: count += max(0, j-i) if count >= m: print(i) break 내코드2 _ 이진탐색으로 다시..

www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제유형 : 구현, 시뮬레이션 문제핵심 : 생각한 아이디어를 구현으로 잘 옮기는것.. 우선 푸는데 좀 오래걸렸다. 이런 구현이나 시뮬레이션 문제는 이렇다할 팁..? 이 없는거같아서 어떻게 정리해야할지 모르겠다. 미래의 내가 다시 풀어도 또 오래걸릴거같은 느낌이다 뭔가 생각할수록 점점 복잡해져서 하던 생각(?)을 끝까지 이어가지않고 자꾸 다른 더 간단한 방법을 찾으려고해서 점점더 생각이 정리되지않고 산으로 ..

www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제유형 : 수학 문제핵심 : 내가있는 위치까지 움직인 거리들(왼쪽경계로부터출발, 아래로부터출발) , 반대편 경계까지 가기위해 움직여야할 거리(위까지, 오른쪽까지 ) 중 가장 작은거리를 구하기 매 우 쉬운문제 x,y,w,h = map(int, input().split()) print(min(x,w-x,y,h-y))

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제유형 : DP / 수학(다르게푼방식) 문제핵심 : 피보나치수열과 같은 점화식임을 깨닫는것(?) dp[i] = dp[i-1]+dp[i-2] 피보나치수열과 같은 형태의 점화식이 나오는 이유 : i번째 사각형의 채우는 방법은 i-1번째에 2*1짜리 사각형을 붙이는것 (오른쪽 기준) + i-2번째에 1*2짜리 사각형을 붙이는것 생각보다 이런유형의 문제는 어느정도까지 직접 구해보고 그 안에서 규칙성을 찾는것도 문제를 빠르게 푸는 방법일수..