whatisworth 님의 블로그 whatisworth 님의 블로그

꽤나 유명한 DP문제이다. 사실 DP문제는 굉장히 자신이 없어서 한 5분 정도 고민하고 바로 답을 봤다.. dp[i]를 정의하는 것부터 꽤나 접근이 어려웠다. dp[i]를 i번째 원소를 가장 마지막으로 하는 증가하는 부분수열의 최대 길이라고 한다. 그리고 모든 원소는 자기 자신을 부분수열로 가질 수 있으므로, dp 초기 테이블을 dp = [1] * N으로 잡을 수 있다. 예제를 표로 그려보면, 다음과 같다. 인덱스 iA[i]dp[i] 초기값010112012101330142015501 이전 dp 테이블 값 + 1 과 자기 자신의 dp 테이블 값을 비교했을 때 큰 값을 현재 자신의 dp 테이블 값으로 설정하는 점화식을 세우면 끝난다. i = 1, A[1] = 20j = 0: A[0] = 10 dp = [1,..

일주일 동안 정신없이 면접보고.. 준비하고.. 하느라 한동안 코딩테스트를 못풀었다 ㅠ 좋은 결과가 나왔으면 좋겠는데.. 잘모르겠다 ㅠㅠ 어쨌든, 이 문제는 대표적인 DP문제이다. DP문제란, 분할정복과 비슷한 개념인데, 작은 것을 더해서 큰 것을 구한다? 느낌이다. 점화식이라고 보면 될것 같다. 나는 DP문제를 한번도 풀어본적이 없어서 처음에는 문제 그대로 피보나치 함수를 짜서 카운트만 해봤는데 시간초과로 실패했다. 다음은 실패한 코드. import sys read = sys.stdin.readline T = int(read()) def fibonacci(n):    global zero_cnt, one_cnt    if n == 0:        zero_cnt += 1         return 0 ..

https://www.acmicpc.net/problem/2529일단 이 문제는 처음 보자마자 bruteforce 일것 같다라는 생각이 들었었다. 그런데 조금 더 생각해 보니 모두 다 탐색할 필요 없이 중간에 부등호에 맞지 않는 숫자배열이 나온다면 멈추는 알고리즘, 즉 백트래킹을 사용해야할 것 같다는 생각이 들었다..! 먼저 문자 부등호를 입력받아서 값을 비교하는 로직을 하나 짜고, 백트래킹 알고리즘을 활용하였다..!최댓값, 최솟값만 구하면 되기 때문에 부등호에 맞는 가장 처음과 가장 마지막 숫자 배열을 프린트 해주기 위하여 함수를 두개 짰다.주의할 점은, visited 와 global 변수 found를 max값 구하는 함수와 min값 구하는 함수에 각각 초깃값을 다르게 해주어야한다는 점이다. impor..

테스트 크기를 보고 딱 브루트포스알고리즘이겠다~ 해서 전부 다 탐색하는걸로 풀었는데 좀 오래걸렸다... 더 예쁘고 효율적인 풀이도 공부해야겠다 풀이 순서는 8*8 윈도우 모두 구하기 정답 체스판 2가지 구현해놓기 3중 for문으로 모든 윈도우에 대하여 정답과 다른 문자 카운트하기최솟값 구하기 인데, 조금 더 예쁜 풀이도 찾아보았다..내풀이 import sys read = sys.stdin.readline N, M = map(int,read().split())chess_map = []for _ in range(N):    chess_map.append(read().rstrip())windows = []for i in range(N-7):    window_xs = chess_map[i:i+8]    for..

https://www.acmicpc.net/problem/17144이문제,, 너무 어려웠다 ㅠㅠ 정말 거의 반나절 걸려서 간신히 풀었는데,, ㅠㅠ 자괴감이... 난 언제 이런 문제 술술 잘 풀려나,,, 여튼 나의 패착은 두 가지였다. 미세먼지 확산을 bfs로 해결하려고 했던 것간신히 정신줄 잡고 그냥 시뮬레이션으로 확산 돌렸는데 기존 graph값을 계속 변화시키는 방향으로 함수를 짜는 바람에 계속 답이 안나옴 공기청정기 방향 아이디어는 잘 잡았는데 테스트케이스 반복문으로 돌리는 과정에서 공기청정기 위치를 초기화 안해줘서... 느낀점은,, 진짜 시뮬레이션은 엄청엄청 꼼꼼해야하구나,,, ㅠㅠㅠ 후... 전체 코드는 다음과 같다.! 헷갈리는 부분은 주석을 달아두었다..import sys from collect..

https://www.acmicpc.net/problem/9012스택 문제 중에 가장 유명한 괄호 문제이다! 내 기억에는 프로그래머스에서도 비슷한 문제를 봤던 것 같다... 스택이란 자료구조는 LIFO 구조로, Last In First Out 구조이다. 파이썬에서는 리스트라고 보면된다. 만약에 코테에 스택 문제가 나온다? 하면 거의 무조건 append, pop만 쓰면 된다..! 다른 내장 함수 쓰는거는 거의 본적이 없다.여튼, 이 문제는 짝이 맞는지 확인해주는 빈 스택을 따로 정해주는 문제이다. 코테 식 문제풀이는 뭔가를 판단할 때 이런식으로 딕셔너리든, 리스트든 새로운 자료구조를 정의해서 판단용으로 사용하는 문제가 많은것 같다... 전체 코드는 다음과 같다. import sysdef is_vps(str..

https://www.acmicpc.net/problem/1913이 문제는 나선형으로 숫자를 배열하는 문제인데, 하우상좌로 이동하는것은 파악했는데 이동방식을 어떻게 조건문을 줘야할 지 몰라서 헤맸던 문제다.. ㅠㅠ 특히 계속 중앙인 1에서부터 시작하려고 했어서 막혔던 문제이다... ㅠㅠ 전체 코드는 다음과 같다. 이동시 조건은 그냥 범위를 벗어나지 않는지, 0이 아닌지만 주면 되는.. 싱거운 문제였다 ㅠㅠimport sys read = sys.stdin.readline N = int(read())M = int(read())arr = [[0 for _ in range(N)] for _ in range(N)]# 하우상좌dx = [1,0,-1,0]dy = [0,1,0,-1]dir = 0num = N ** 2x..

https://www.acmicpc.net/problem/16236이 문제는 기본 BFS에 여러가지 조건이 붙은 문제여서 구현하기가 좀 까다로웠다.문제의 특징을 몇가지 말해보자면, 아기상어의 위치를 구하고 그 자리를 0으로 초기화 해주기 아기상어의 이동(BFS)와 물고기를 먹으면서 크기를 성장하는 로직을 따로 작성해주기 BFS에서 먹은 물고기의 위치, 거리를 리스트로 저장해서 정렬하기 가 있다. 특히 세번째의 경우 굉장히 중요한 포인트인데, 나는 처음에 BFS로 이동하면 자동으로 제일 위에 있는 물고기, 제일 왼쪽에 있는 물고기부터 먹을줄 알았다. "거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다."이 부분을 어떻게 구현하느냐를 생..