이숭간 공부기록

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제유형 : 다이나믹 프로그래밍 문제풀이 : 1. 큰 문제를 작은문제로 쪼개서 생각해내는것이 필요 2번째 집을 파란색으로 색칠할때의 최솟값? -> 1번째집을 min(빨간색으로 색칠, 초록색으로 색칠) + 2번째집을 파란색으로 색칠할때의 비용 그렇다면 3번째 집을 빨간색으로 색칠할때의 최솟값? -> 2번째집을 min(파란색으로 색칠, 초록색으로 색칠) --> 위에서 구했네?? ..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제유형 : 수학, 그리디, 문자열 문제풀이 : 괄호를 적절히 넣어 최솟값을 만드는 방법이므로 - 를 만나면 앞에 괄호를 넣는다. 언제 괄호를 닫아주는가? 그다음 - 를 만나면 괄호를 닫고 다시 괄호를 열여준다. +일때는 계속 지나간다. 만약 배열이 모두 끝났는데 아직 괄호가 열려있는 상태라면 맨 마지막에 괄호를 추가하여 닫아준다. 괄호가 열려있냐 닫혀있냐의 여부는 flag변수를 통해 수행한다. 위 과정을..

www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제유형 : 큐 (자료구조) 문제풀이 : 원 형태로 연결되어있는 자료구조를 큐로 구현하기 내가 원하는 곳 (타겟지점) 으로 도달하기까지 거치는 것들은 큐에서 빼고 다시 큐에 넣어주는 형식으로 하면 원 형태의 자료구조를 큐로 구현할 수 있다. ex ) 1,2,3,4,5,6,7에서 3을 타겟으로 할때 거치는 1,2,는 다시 뒤에 넣어줌으로써 3,4,5,6,7,1,2를 구현할 수 있다. 정답코드 : import sys input = sys.stdin.readline n,k = map(int, inpu..

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제유형 : 문자열, 정렬, 해시 문제핵심 : 1. 파이썬 라이브러리 startswith메소드 2. 전화번호 배열을 정렬하면 접두어가 있는경우 같은번호로 시작하는 번호들은 무조건 인접하게 위치한다!! 3. zip()함수 : 파이썬 내장함수인 zip()은 동일한 개수로 이루어진 자료형을 묶어주는 역할을 하는 함수다. (동일한개수 아니여도 됨 _ 더작은 개수에 맞춰서 짝짓기됨, 즉 길이다른 ..

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..