Python
14501_퇴사
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp를 활용하면 풀 수 있는 문제이다. 단 상담 날짜가 안되는게 해당날짜부터 뒤부터 안되므로 dp를 채워나갈 때 뒤에 날짜부터 시작하였다. 백준의 주어진 입력케이스로 생각해보자. 7일 부터 시작해서 과거로 하루씩 늘어난다고 생각하고 이걸 i라고 생각해보자 즉 i 는 1일부터 7,6,5,4,3,2,1 이 된다. (코드로 구현한다면 6,5,4,3,2,1,0으로 구현할 수도 있다.) 7일인 경우 i는 1이고 상담에 걸리는 날짜가 2일이기에 추가할 수 없다. 이런식으로 dp를 거꾸로 채워나갈 것이다. 그렇다면 상담을 할순 있는 날짜임을 걸러..
1305_광고
https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 역시 KMP알고리즘을 활용해 푸는 문제이다. 특히 KMP Table을 이용해서 풀 수있다. 예를들어서 7 aabaaba라는 문자열이 있다고 생각하면 KMP Table을 구하면 [0, 1, 0, 1, 2, 3, 4] 가 나온다 즉, 광고판의 끝부분에서 보았을때 시작부터 4개의 지점이랑 겹친다는 의미이다. 그렇기 때문에 광고판의 개수에서 겹치는 개수를뺀 l - KMP_Table[-1]을 구하면 답을 구할 수 있다. l..
4354_문자열제곱
https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net KMP 알고리즘을 활용해서 문제를 풀 수 있다. a란 이름의 str이 입력된다고 생각해보자. a+a 문자열을 하나 만들 수 있을 것이다. 만약 abcd가 들어온다면 abcdabcd를 만들어준다. 이 a+a 문자열에서 a가 시작되는 부분을 구해준다. abcdabcd라면 abcd가 다시 시작되는 부분은 5번째일 것이다 index로 나타내면 4이다. aaaa가 들어온..
클러스터링 K-Means 직접구현
이번에는 K-Means를 직접 구현 해볼것이다. 우선 클러스터링에 대해서 간략하게 설명부터 해보자! 만약 위처럼 사과,배,바나나를 분류하는 문제를 구현해본다고 생각해보자. 이전에 배웠던 인공신경망을 활용할 수도 있겠지만 이번에는 클러스터링을 이용하여 군집을 나누어 볼 것이다. 어떠한 특성을 잘 집어낸다면 결국 사과,배,바나나들은 군집처럼 분류될 것이다. 이들의 군집의 중심점을 찾은 후, 근처에 있는것들을 한 군집을 분다면 우리는 분류를 할 수 있다. 클러스터링의 기본적인 프로세스는 아래와 같다. 즉 랜덤의 중심점을 설정한 후에, 가까운곳들을 해당 군집으로 묶어준다. 그이후 같은 군집내의 중심을 다시 중심점으로 잡은 후에 군집의 분류를 시켜준다. 이를 계속 반복하여 군집이 더이상 변하지 않을떄까지 한다면,..
1786_찾기
https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP알고리즘을 사용해서 풀면된다. 백준 문제 글에 설명이 자세히 되어있으니 알고리즘 자체는 설명을 읽으면 될 것 같다. 최대의 k를 미리 계산해 놓으면 편리할 것이다 라는 구절이 있는데 이를 먼저 구해두면 된다. p를 처음부터 순환하면서 k를 저장해둘 공간을 넣어두면 된다. 해당 부분은 코드로 보는것이 좀 더 편할 것 같다. t = input() p = input() k=[0 for _ i..
11659_누적합
https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 리스트의 i번째부터 j번째까지의 누적합을 구한다고 생각하면 그때그때 리스트를 슬라이스 해서 구하는 것보다 누적합 리스트드를 하나 미리 만들어놓는것이 좋다. 문제 예시의 5 4 3 2 1 리스트가 있다면 [0, 5, 9, 12, 14, 15] 처럼 누적합 리스트를 만들어놓고 뽑아쓰는 것이다. import sys input = sys.stdin.readline n,m = map..