본문 바로가기

전체 글

swea 9843 촛불 이벤트 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBKzuaPOoDFAXR&categoryId=AXGBKzuaPOoDFAXR&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N이 주어졋을때 이 N개의 촛불을 1 2 3 4 5 6 7 8 .. K 와 같은 방식으로 쌓을수있는지 판단하는 문제이다. 1~K 의 등차수열의 합은 K(K+1)/2이므로 K(K+1)/2 = N의 해를 구해주면된다. 완전 탐색으로는 N이 10^18 이므로 당연히 안되고 이분탐색을 이용하면 logN시간에 방정식의 해를 구.. 더보기
백준 1736 쓰레기 치우기 https://www.acmicpc.net/problem/1736 1736번: 쓰레기 치우기 방은 세로 N, 가로 M (1 더보기
백준 2458 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 키를 비교한 결과가 주어졌을 때 자신의 키가 몇번째인지 알수있는 학생이 몇명인지 알아내자. 키를 비교한 결과를 그래프로 나타내면 다음과 같다. 자신이 몇번쨰인지 알기 위해서는 1. 다른 점에서 자기를 방문할수 있다. 2. 자기가 다른 점을 방문 할수 있다. 가 모든 점에 대해 만족 되야한다. 위의 그림에서 4번은 2,6번을 방문 할수있고, 1 3 5는 4를 방문할수 있으므로 4번은 자신의 순서를 알.. 더보기
백준 16161 가장 긴 증가하는 팰린드롬 부분수열 https://www.acmicpc.net/problem/16161 16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드�� www.acmicpc.net 주어진 수열의 모든 연속 부분수열를 탐색하는 경우수는 O(N^2)이고, 그 부분수열이 팰린드롬인지 판별하는데 걸리는 시간이 O(N)이므로 시간 복잡도가 총 O(N^3)이다. N=10만이기 때문에 1000조의 계산수를 감당할 수 없다. 하지만, 증가한다는 특성 그리고 팰린드롬의 특성을.. 더보기
백준 1766 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. (1이 가장 쉽고 N이 가장 어렵다) 내가 어떤 한 문제를 풀기 위해서는 그 문제로 들어오는 노드들 또한 풀어야만 가능하다. 즉 부모노드가 0개여야 가능하다는 뜻이다. 부모노드가 0개인 노드들을 배열.. 더보기
백준 7571 점모으기 https://www.acmicpc.net/problem/7571 7571번: 점 모으기 첫 줄에는 격자공간의 크기와 점들의 개수를 나타내는 두 정수 N과 M이 하나의 공백을 사이에 두고 주어진다. 다음의 M줄에는 각 줄마다 격자공간내의 점의 위치를 나타내는 두 개의 정수가 하나 www.acmicpc.net 위와 같이 위치된 점들을 하나의 점으로 모았을때 최소거리를 구하는 문제다. 점들의 x좌표, y좌표를 각각 xx , yy라는 배열에 저장하고 이점들을 모두 (p,q) 라는 점에 모았을때 거리 D(p,q)를 계산한다고 생각해보면 D(p,q) = |xx[0] - p| + |xx[1] -p| + .... |xx[n-1] -p| + |yy[0] -q| + |yy[1] -q| + |yy[2]-q| + .... .. 더보기
백준 16228 GCC의 유산 https://www.acmicpc.net/problem/16228 더보기
백준 15927 회문은 회문아니야!! https://www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 보자. 회문 (한국어) palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어) 回文 (일본어, 중국어) palindrom (독일어, 덴마크어) palindromi (핀란드어) palíndromo (스페인어, 포르투갈어) pal www.acmicpc.net 입력 받은 문자열중에서 가장 긴 부분문자열을 구하는 문제이다. DP문제인줄 알았지만 도무지 점화식이 생각 안 나서 다르게.. 더보기

티스토리툴바