똥그래미 코딩공장

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이번 문제는 무려 '골드' 문제다... 처음으로 골드 문제를 풀어보았다. 개인적으로 놀란것은 풀만했단 것이다. 그래프 탐색 문제를 풀면서 느끼는 거지만 진짜 문제들의 큰 틀은 다른게 없다. 정말로 접근은 비슷하고 추가하는 조건만 조금 수정해주면 된다. 심지어 이 조건이 그렇게 어려운것도 아니다. if문 하나 수정해주면 모든 문제들이 풀린다. BFS,DFS 더 이상 쫄지 않아도 된다!! 아래..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 이번에도 그래프 탐색 문제를 들고 왔다 이 문제는 DFS,BFS 둘다 풀리지만 난 DFS로 풀었다. 점점 그래프 탐색 문제에 자신감이 붙고 있다 술술 이해가 잘되고 다른문제도 풀리고 있다. 알고리즘에 묶이는 일은 줄어든거 같다. 설명은 코드에 주석처리로 해놓았다. 아래 코드를 보겠다. import sys sys.setrecursionl..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 드디어 DFS와BFS에 대해 공부를 시작했다. 정말 어렵다!!!!!!!!!!!! 이해를 하는데 상당한 시간이 걸렸다. 그래서 어쩔수없이 다른 사람들의 코드를 참고하였다. 이 유형들은 내가 이번 방학동안 꼭 정복하고 말것이다. 아래는 풀이 코드이다. 설명은 주석처리로 해놓았다. from collections import deque N,M,V = map(int,i..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 이 문제는 나에게 새로운 지식을 알려준 문제이다. 이 문제는 공통된 문자열을 찾는 문제인데 집합으로 문제를 풀어야한다. 나는 set()함수가 중복제거만 해주는 함수인줄 알았지만 집합으로 엮을 수도 있다는 것을 이 문제를 통해 알았다. 이 문제는 집합에서 '교집합'의 특징을 이용해야 한다. 아래의 코드를 보며 설명을 이어가겠다. n,m = map(int,input().split()) set1=se..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문자열과 그리디가 합쳐진 유형이다 언뜻보면 쉬울수도 어려울수도 있는 문제이다. 이 문제의 키포인트는 숫자가 바뀌었을때를 찾고 연속해서 나오는 숫자들을 세줘야 한다는 것이다. 아래의 코드를 보며 설명해보겠다. s = input() one_count = 0 zero_count = 0 for i in range(len(s)-1): if s[i] == s[i+1]: continue else: if s[i..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 문자열 일치 문제이다. 코딩테스트에서 문자열 유형의 비율이 나날이 높아져 간다. 그래서 배제 할 수 없고 꾸준히 풀어보아야한다. 난이도는 그렇게 어렵지 않았다. import sys a,b=sys.stdin.readline().split() ans = [] for i in range(len(b)-len(a)+1): cnt = 0 for k in range(le..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르기 문제이다. 가장 대표적인 DP 문제중 하나라고 할 수 있다. DP 유형은 코딩테스트 단골 유형이므로 반드시 익히고 가야하는 유형 중 하나이다. 오늘 이 DP 문제를 풀어보도록 하겠다. import sys input = sys.stdin.readline num = int(input()) dp=[0]*(num+3) d=[0]*(num+3) for i in range (1,num+1): d[i]=int..

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 이 문제는 보자마자 그리디 문제라고 파악을 했고 수학적인 연산도 필요할것이라 생각했다. 그리디 문제는 가장 효율적인 방법을 찾아내야 한다. 그래서 푸는데 시간이 좀 걸린 문제였다. import sys n,m= map(int,sys.stdin.readline().split()) arr1 = [] arr2 = [] for i in range(m): a,b = map(int,sys.stdin.rea..