코딩못하는사람

https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1.접근 간단한 문제인거같아 DFS로 목적지에 도달했을때 stack을 정렬해서 값을 찾아냈는데 시간초과를 받았다.(정렬을 너무 많이 사용하게 되서) 'x원으로 해결이 안되는데 x-1원으로 가능할까?' 라는 질문글에 있던 힌트를 보고 문제를 해결할 수 있었다. 2.풀이 이분탐색을 해가면서 다익스트라를 돌릴때마다 가능한 값이면 정답에 저장하도록 했다. 문제에서..

https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 1.접근 삭제와 삽입 연산이 잦으므로 배열이나 일반 ArrayList가 아닌 LinkedList를 사용해야겠다고 생각했다. 하지만 LinkedList를 이용한 풀이는 시간초과를 받았는데 Up 과 Down이 잦은 문제라 그랬다. 단방향 LinkedList는 한칸 앞(이전 노드)으로 이동하려면 처음(head)부터 리..

https://www.acmicpc.net/problem/22115 22115번: 창영이와 커피 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. www.acmicpc.net 1.접근 백트래킹으로 생각하고 풀었다가 시간초과를 맞았다. k가 커질 수록 시간이 급격히 늘어나는 코드였다. 얻어야하는 카페인양과 커피들의 카페인양을 보고 냅색문제처럼 최적 부분 구조로 나누어 풀 수 있다는걸 알았다. 2.풀이 각 커피에 카페인이 1, 2, 3, 4, 5 가 들어있고 마셔야하는 카페인이 15라고 가정해보자. 만약 5가 커피의 최소 개수를 위해 꼭 마셔야하는 커피라면 15에서 5를 뺀 10의 카페인을 1,2,3,4커피를 가지고 마시는 경우 +1이 최소 개수의 커피를 마시는..

https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 1.접근 인접한 격자로 가려면 경사의 절댓값을 지날 수 있어야 한다. 두가지 풀이가 생각났다. 1.이진탐색 경사의 범위가 1 ≤ Ar,c ≤ 1,000,000,000 이므로 가능한 경사의 값을 이진탐색으로 찾아서 값을 찾아가며 (1,1)->(n,n)으로 DFS를 돌려서 찾는 방법. 2.우선순위 큐 가장 경사가 적은값들만 찾아가면서 n,n이 나올때까지 탐색으로 찾아들어가는 방법 2.풀이 1.이진탐색 DFS로 그래프를 순회하며 (1,1)->(n,n)을 찾아간다. 지정한 경사보다 낮은 경사값들만 찾아 들어가다가 n,n에..

https://www.acmicpc.net/problem/19584 19584번: 난개발 이 사실은 대회에 참가하고 있는 여러분들만 알고 있는 사실이다. 방금 외계인들이 지구를 정복했고 서울시청과 서울시의회를 장악했다. 이들은 인간들이 통근과 통학으로 고통받게 하려고 대 www.acmicpc.net 1.접근 문제의 예시 그림을 보고 고민을 해보면 X축의 값은 필요없고 Y축으로 압축해서 누적합이 가장 큰 곳을 구하면 된다는 생각을 할 수 있다. 통행량을 계속 증가시켜주기 위해서 구간에 대해서 세그먼트 트리도 생각해보고 여러가지 생각해보았지만 y축으로 정렬하여 존재하는 모든 y축을 돌면서 시작지점에는 +,종료지점에는 -를 해주는 방식을 생각했다. 2.풀이 누적합을 어떻게 구할지 생각하는게 중요한 문제이다. ..

www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 1.접근 각 알파벳에 자리수를 곱해서 가장 큰 값부터 9를 할당해서 문제를 푸는 그리디 문제이다 2.풀이 알파벳을 한줄 씩 입력받을 때 마다 자릿 수를 곱해서 Map에 저장한다. 예를들면 ABC는 A에 100, B에 10, C에 1을 더하는 것이다. 이렇게 map을 만들고 value값이 가장 큰 순으로 정렬해서 9부터 1씩 줄여가며 곱해서 답을 출력한다. 3.코드 4.배운점 (1)Map에서 value값에 ..

파이썬에서의 문자열 문제해결방법 in을 사용해서 포함여부 판단하기 find()를 사용해서 index까지 구하기 KMP알고리즘을 사용해서 index 또는 포함여부 구하기 1,2번은 최악의 경우 O(N*M)이지만 KMP알고리즘은 O(N+M)에 해결 가능하다. 리스트 형태로 저장하였다면 ''.join(list_name)으로 공백없는 문자열을 만들 수 있다. 1. in을 사용하기 문자열에 in을 사용해서 찾는 문자열이 포함되는지 판단 가능하다. 만약 포함된다면 True를 아니면 False값을 반환해준다. ex) string='python' print('pyt' in string) =>True print('ppp' in string) ->False 2.find() 함수 사용하기 문자열간에 포함여부와 인덱스를 반환..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 1.접근 알파벳 소문자는 26개이다. 따라서 int(32bit) 크기의 2진수 배열에서 알파벳을 각각 하나씩 마스킹에 할당해서 문제를 풀 수 있다. 2.풀이 남극의 모든 단어는 a,n,t,i,c 으로 이루어져 있으므로 k가 5보다 작다면 어떠한 단어도 읽을 수 없다. 5개의 단어는 모두 배운다고 가정한고 한줄씩 입력받으면서 a,n,t,i,c을 지우고 가운데 알파벳들만 입력받는다. 만약 a,n,t,i,c로 지운 리스트의 길이가 0이라면 무조건 읽을 수 있는..

www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 1.접근 N이 2,000,000이므로 NlogN을 생각하게된다. 세그먼트 트리를 이용할텐데 X의 크기도 2000000까지인 것을 보아 리프노드를 200만개로 만들고 1번 유형 쿼리로 숫자와 인덱스가 같은 트리를 만들어야겠다. 2.풀이 우선 트리를 만드는대 어느 숫자가 들어올지 모르기 때문에 리프노드 200만개 모두 만들어야 한다. 그 후 인덱스와 들어오는 숫자가 같은 트리이므로 ..

피보나치 수를 구하는 3가지 방법. 피보나치 수는 알다시피 다음과 같이 정의되는 수열이다. 이렇게 이전 2개의 합이 다음 오는 수가 되는 수열이다. 조금 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...이 된다. 가장 기본적인 문제를 풀어보자 10826 피보나치 수 4 www.acmicpc.net/problem/10826 1.접근 n은 10,000보다 작거나 같은 자연수 또는 0이다. 쉬운 피보나치 수이다. 2.풀이 우리는 DP느낌의 방법으로 쉽게 O(N)시간에 답을 구할 수 있다. 3.코드 4.배운점 사실 dp로 구현했었는데 메모제이션 할 필요없이 for 문을 돌리면 가장 간단했다. 2749 피보나치 수 3 www.acmicpc.net/problem/27..