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/2573이 문제는 그래프 탐색 문제로, 문제에서 설명하는대로 착실하게 구현만 하면 되는?(그게 어렵지만,,)문제라고 할 수 있다. 빙산이 분리가 되는지 탐색하는 것은 bfs를 통해 구현하였고, 1년 후 빙산의 상태는 이중 for문으로 구현하였다. 중요한 점은 방문 그래프가 반복문을 실행할 때마다 초기화 되어야 한다는 것이다. import sys from collections import dequeread = sys.stdin.readline N, M = map(int, read().split())graph = []for _ in range(N):    graph.append(list(map(int, read().split())))# 상하좌우 dx ..

https://www.acmicpc.net/problem/2667이 문제는 DFS와 BFS모두 풀이가 가능한 문제이다.나는 BFS로 풀었는데, 사실 BFS는 구현하기가 어렵진 않았지만, 잊어버린 부분이 몇가지 있다. 방문 리스트를 초기화할때, visited = [[False] * N] * N이런식으로 하게되면, visited 배열의 모든 행이 같은 리스트 객체를 참조하도록 만들기 때문에, 나중에 방문처리를 하게 될때, 한 행의 값을 수정하면, 모든 행의 값이 동시에 변경된다. visited = [[False for _ in range(N)] for _ in range(N)] 이렇게 초기화 해야한다!또 주의해야할 부분은 bfs(0,0)만 하게 되면 단지 하나만 탐색하고 끝나버리는데, 이를 방지하기 위하여 ..

https://www.acmicpc.net/problem/1697이번 문제도 어제와 마찬가지로 그래프 탐색 문제이다. 나는 항상 코딩테스트 문제를 잘 풀기 위해서는 이 문제를 어떤 알고리즘을 사용하여 풀어야할지 고민해봐야한다고 생각하는데, 이문제는 최단경로 라는 단어에서 힌트를 준것 같았다. DFS는 깊이 우선탐색으로, 특정한 경로를 원할 때 주로 사용한다고 보면되고, BFS는탐색을 현재 노드와 가까운 노드부터 순서대로 진행합니다.큐를 사용하며, 먼저 들어온 노드부터 처리됩니다.특징: BFS는 모든 경로를 동일한 깊이(거리)로 탐색하므로, 특정 노드에 처음 도달한 순간이 곧 최단 경로임이 보장됩니다. 라는 특징 때문에 이 문제에 사용할 수 있다고 생각하였다. 처음에는 node를 print하면 최단경로가 ..

https://www.acmicpc.net/problem/1260 99클럽 1주차는 이분탐색이나 투포인터 문제를 풀었다면, 2주차의 문제 주제는 그래프 탐색인 것 같다. 이번 문제는 DFS와 BFS의 개념을 확실히 알 수 있는 문제이다. 먼저 그래프는 두가지 형태로 입력받을 수 있는데, 인접행렬과 인접리스트 형태이다. 인접행렬과 인접리스트의 차이는 다음과 같다. 예를 들어 다음과 같은 그래프가 있다고 가정해볼 때, 인접행렬과 인접리스트는 다음과 같이 입력될 수 있다. 1. 인접행렬 : 각 노드가 연결되어 있는지 아닌지를 0혹은 1로 나타낸 행렬이다. (모든 노드에 대한 연결정보를 저장하므로, 공간메모리가 소모되서 잘 안쓰이는 것 같다.)2. 인접리스트 : 각 연결 정보를 중첩리스트를 활용하여 나타낸 것이..