Nanarin🙃

알고리즘 문제 해결 전략 - 06 무식하게 풀기 (Brute-Force 브루트 포스) 예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하) 보글(boggle)은 5X5 크기의 알파벳 격자를 가지고 하는 게임 게임의 목적은 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것 각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있음 문제 이해했고 C++로 구현되어 있는 코드를 파이썬으로 잘 변경했다 그대로 변경하지 않고 시작점을 주지 않고 모든 칸을 돌면서 찾는 방법으로 변경하였다 # 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘 dx = [-1, -1, -1, 1, 1, 1, 0, 0] dy = [-1, 0, 1, -1, 0, 1, -1, 1] def..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 여러 방법을 써봤는데 다 시간초과... 입력 방법때문인가 싶어서 sys 모듈 readline 함수로도 바꿔봤는데 계속 시간초과가 난다 뭐때문일까?.. 그냥 너무 오래 걸려서 시간초과였음 ㅎ.. 머리가 다 굳어버린거같다 계속 시간초과나서 찾아봤는데도 이해가 안되서 한참 버벅댐 짧고 간단하게 풀리는 문제였는데 딕셔너리 너무 오랜만이라 더 그랬던 듯....

파이썬 3.8에 도입된 바다코끼리 연산자 := := := 1. 형식 이름 := 표현식 2. 목적 표현식에 이름을 부여하고 재사용 할 수 있도록 하는 것 바다코끼리 연산자를 사용하면 할당과 테스트를 한 단계로 줄일 수 있음 3. 사용 예 walrus = "walrus operator" n1 = len(walrus) if n1 > 5: print("kkk") if n2 := len(walrus) > 5: print("kkk") => 2,3 번 라인의 두 단계를 6번 라인 한 단계로 줄임 + for문, while문 등에도 사용이 가능

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 나는 아직 DP 문제에 적응을 못한거같다... 계속 혼자는 못풀겠다 ㅜ 아니 풀긴 푸는데 계속 시간초과나고 난리난리 입력받은 숫자를 앞에서부터 하나씩 셀것 입력받은 숫자들을 리스트 num에 저장하였다고 할 때 num[n] 과 num[n] + num[n-1] 을 비교하여 num[n] 에 저장한다 num[n]이 더 크다면 앞의 수들의 합 중 가장 큰 num[n] + num[n-1]이 더 크다면 예제 1번을 예로 들면 num ..

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 어우 너무 어려웠다 문제을 백번 읽어도 대체 이걸 어떻게 풀어야하나 모르겠는.. 그런... 그래서 찾아봤는데 DP의 유명한 문제라더라 LCS.. 아니나다를까 풀이 방법을 봤는데도 이해하는데 한참 걸렸다 다들 아... 이렇게 푸는구나만 설명하고 왜 이렇게 푸는지는 설명을 안해주셔가지고 너무 괴로웠다 뭐 설마 다들 풀이 방법을 보면 번쩍 하고 이유가 이해되는건가 나만 안..

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 허허 리스트에 교차점 다 넣고 지우고 넣고 빼고 난리난리를 쳤는데 반례를 없앨 수가 없어서 대체 어떻게 푸는건가 봤더니 참.. 세상에 이런 방법이..... 똑똑한 사람 개많다 증말 ㅜ 어쩐지 앞에 문제가 뜬금없다 했는데 써먹으라고 알려준거구나.... 없애야 하는 전깃줄의 최소 개수를 구한다는건 없애지 않고 그대로 놔둘 전깃줄의 최대 개수를 구하는 것과 같다 A 전봇대 기준 오름차순으로 정렬했을 때 B 전봇대에 연결된 ..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분 수열은 앞 문제 11053번과 비슷하지만 조금 다르다 그냥 양쪽으로 계산해주면 된다 k개 원소를 가진 수열 = n번째 숫자 기준으로 0~n까지 가장 긴 증가하는 부분 수열 + n~k-1까지 가장 긴 감소하는 부분 수열 - 1 감소하는 부분 수열을 구하기 힘들기 때문에 수열을 뒤집어서 증가하는 부분 수열을 구한 후 다시 뒤집으면 감소하는 부분 수열이 된다 1. 입력받은 수들을 리스트 seq_1에 저장, seq_1을 복..

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 입력받은 수들을 리스트 seq에 저장 2. seq와 같은 길이의 t_seq를 생성하고 첫번째 요소는 1, 나머지는 0으로 채운다 => seq[n]까지의 가장 긴 증가하는 부분 수열의 개수를 리스트 t_seq[n]에 저장할 것 3. for문으로 t_seq[1] ~ t_seq[n-1] 까지 계산 => 가장 긴 수열에는 seq[n]가..

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2579 : 계단 오르기 문제랑 똑같이 풀면 된다 대신 계단은 마지막 계단을 꼭 밟아야 하지만 마지막 포도주를 마실 필요는 없기 때문에 맨 마지막 포도주의 최종 양이 아닌 리스트 중 최댓값을 출력해주면 된다 라고 생각했는데 이게 웬걸 대뜸 틀려버려서 뭐가 틀린건지 찾아봤는데 아니 n번째 포도주를 마시는데 대체 왜 n번째 포도주를 마시지 않는 경우가 고려사항에 포함된단 말인가? 세상에나 1도 이해 안가네 ... 그..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. step[n][m] 에는 m으로 끝나는 n+1자리 계단 수의 개수를 저장할 것이다 2. step[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] 이다. ( 한자리 계단수는 1~9 ) 3. for문을 통해 2자리부터 n자리까지의 계단수를 구한다 3-1. n자리 계단수가 0으로 끝나려면 n-1자리 계단수가 1로 끝나야한다 3-2. n자리 계단수가 t(2~8) 로 끝나려면 n-1자리 계단수는 t-1로 끝나거나 t+1로 끝나야 한다 3-3. n자리 계단수가 9로 끝나려면 n-1자리 계단수가 8로 끝나야한다 3-..