생각 생각

https://acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹에 대해 처음 알게 된 문제. 지난 토요일 카카오 코테에서 못 풀고 시간만 날린 문제가 bfs가 아닌 백트래킹 문제임을 알게 되었다. 문제는 간단하게, 1부터 N까지의 자연수 중 M개로 이루어진 중복순열을 다 구하는 것이다. ​ 백트래킹의 개념은 굉장히 단순하다. 결국엔 다 해보는 것과 다를 바 없지만, 하다가 아닌 것 같은 때 그만 둔다. ​ dfs의 탈출 조건은 s라는 현재 배열의 길이가 m..

https://acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net https://acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 둘 다 class 3의 standard 문제이고, 모든 것이 ..

https://acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 노가다 구현문제. bfs로도 풀 수 있다고 하니 나중에 도전해봐야겠다. 보드 입력 받고 쭉 함수 지정한 후 (총 19개여서 생략한다), 특정 지점에서 최대값 찾아 갱신하고 답 출력.

https://acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 3달전, 처음 ps를 시작하고 3주차에 주제넘게 덤볐다가 포기한 문제. ​ 이제는 쉽게 풀 수 있었다. 최대 그래프 크기가 20*20이니 사실상 시간 복잡도를 고려하는 문제라기보다는, 빡구현 문제임을 예상해 볼 수 있다. bfs인듯 아닌듯한 bfs 문제이다. 선언부에서는 문제의 조건대로 시간 (물고기를 먹는 순간의 시간), 물고기의 크기, 물고기의 크기가 증가하기 위해 먹어야 하는 개수의 상태(일..

https://acmicpc.net/9019 제목으로 드립치는 게 당황스러웠던 문제. python3로 푼, 풀수 있는 사람이 애초에 거의 없는데 python3로 제출하는 게 실수였다. 배웠던 점은 우선 문자열로 전환하는 연산보다 숫자 연산이 훨씬 더 빠르다는 것. 그리고 일차원 bfs에서는 방문 기록을 할 때 set과 add를 적극적으로 활용해야 한다는 것이었다. 숫자를 이용해 DSLR을 정의하고, bfs를 돌아 해결한다.

https://acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택의 원리를 이용한 문제. 거의 다 풀어놓고 한참을 헤맸다. 원래 풀이는 이랬다. 이 풀이에서 고민하던 것은 다음과 같은 반례였다. 풀이 방법 자체에 하자가 있었는데, 바로 temp_lis에 굳이 숫자를 저장하는 것이었다. temp_lis에 숫자를 저장하느니 그냥 index를 저장하고, 어차피 넣을 오큰수는 정해져있으니 그 오큰수를 index에 넣으면 되는 것이었다. 애초에 answer를 "-1"로 채워두면 굳이..

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4#s-3.2 최장 증가 부분 수열 - 나무위키 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. namu.wiki LIS 알고리즘 관련된 문제를 쭉 풀어보았다. 생소하고 어려워서 시간은 좀 걸렸지만 이제는 익숙해졌다. 크게 두 가지 방법이 있다. 간단하게 정리하자면, ​ O(n2)의 해결 방법 dp로 해결한다. 시작점부터 끝점까지, 끝점을 한 칸씩 옮겨가며 만약 탐색하다가 탐색하는 점이 ..

https://acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 원론적인 dfs와 bfs 문제. 출발점과 도착점을 1 5 와 같은 식으로 주는 문제들이 있다. (양방향 간선) 이때 풀기 좋은 방법을 알려준 문제. graph[a][b]에 1이 있다면 a-b 사이 간선이 있는 것이다. 반대로 그렇다면 b-a 사이도 간선이 있는 것이니 graph[b][a]도 1로 표시해주면 된다. ​ bfs는 항상 하던대로 pop하고 print하고 방..