생각 생각

1697번은 dp로 풀고 dp로 푸는 게 맞는 줄 알았다. 12851이 안 풀려서 보니 bfs였던 문제. ​ 1697 - dp 풀이 ​ 단순하게 dp를 이용해 계속 i-1, i+1, i//2를 비교해가며 작은 것으로 업데이트 하는 방법이다. 정확한 경로를 알아야 할 필요가 없고 시간만 필요하다면 이런 풀이도 가능은 하다. 그러나 사실상 정방향으로 계속 가면 그만이기 때문에 굳이 dp를 쓰는 메리트는 없는 문제. ​ 1697-bfs 풀이 이런 식으로 시작점부터 쭉 끝까지 가면서 특정 지점까지 가는 지점을 업데이트 해주면 끝이다. ​ 12851 12851은 동일하게 순회를 돌되, visited를 이중배열로 만들고 두 번째 항목에는 방문 횟수를 기록한다.

https://www.acmicpc.net/problem/2018 간단한 문제. 투 포인터 공부를 위해 풀어보았다. 이 경우 투 포인터의 간단한 원칙은, sum이 목표 수보다 작으면 오른쪽 포인터를 뒤로 옮긴다. 그러다가 sum과 같은 순간이 오면 count를 올리고 오른쪽 포인터를 뒤로 옮긴다. 옮겨서 sum이 목표 수보다 크면 start를 오른쪽으로 옮겨 sum에서 뺀다. 이때 주의해야 할 것은 정렬이 되어 있어야 한다는 것, 그리고 end의 범위를 n까지로 하는 것.

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 어쩌다 보니 골드 문제도 손 댈 수 있게 되었다. 전형적인 bfs문제인데, 아직까지도 bfs가 손에 익지 않아 실수가 많다. 100줄이니 표준 입력을 사용하고, dx와 dy는 대각선 이동이 안 되니 다음과 같다. bfs 함수를 두 개 만들거나 R를 G로 바꾸거나 두 개가 있었는데, 공연한 그래프 순회는 마음에 들지 않아 함수를 하나 더 설정했다. 적록색약인 사람은 B냐 아니냐만 확인해 주면..

https://acmicpc.net/1620 특이한 점을 배웠는데, 딕셔너리를 빠른 인덱싱에 이용할 수도 있다는 점이다. 예를 들어, 포켓몬 이름을 입력받아 그 번호를 출력해야 한다고 하자. 그러면 그 포켓몬의 이름으로 .index를 실행하면 처음부터 찾아야 하니 시간이 너무 오래 걸린다. 딕셔너리의 key에 이름을, value에 index를 넣어두면 그런 과정 없이 바로 찾을 수 있다고 한다.

처음으로 풀어본 제대로 된 그래프 탐색 문제. 여전히 BFS와 DFS는 어렵기만 하다. ​ Function#1 나이트 이동가능 위치 지정 Function#2 나이트 놓기 (multiple knight로 인한 이동 가능위치와 놓는 위치의 간섭이 문제를 망친다) Function#3 폰 놓기 Function#4 퀸 놓기 (폰을 뛰어넘을 수 없고 나이트도 뛰어넘을 수 없으니 1, 4 만나면 break) 변수선언부(chess에 2차원 배열로 체스판 받기) Solution: 순서가 핵심이다. 어떻게 하면 간섭을 일으키지 않을지를 고민한 결과, 1. 나이트 이동 가능 범위 찾기 2. 나이트 놓기 3. 폰 놓기 4. 퀸 놓기+퀸 이동 가능 범위 파악 의 순서로 놔야 한다고 생각했다. ​ 이 순서가 아니라면 반례가 있기..

정규표현식과 관련하여 탐욕 연산자와 나태 연산자가 있다. 탐욕 연산자는 조건에 해당하는 최대한 긴 부분을 찾는다. 나태 연산자는 조건에 해당하는 최대한 짧은 부분을 찾는다. 정량자에 ?를 붙이는 방향으로 정의된다. 주어진 문제는 (100+1+ | 01)+이다. 즉 100 1개 이상 뒤에 1이 1개 이상 있거나, 01이 있는 것이 반복되는 구조에 해당한다면 "YES"를, 아닌 경우에는 "NO"를 출력하는 것이다. 처음에는 반례가 없을 줄 알고 정규표현식을 그대로 써 문제를 푼 줄 알았다. 해당하는 것들을 다 찾은 후 그 개수가 원래의 str과 같으면 답 아니겠는가. 그런데 오답이 계속 나왔다. 찾아보니 반례는 100111001이었다. 100111001은 분석해보면 10011 1001로 YES가 출력되어야 ..

네이버 블로그에만 기록하다가 티스토리에 기록하는 것이 더 편할 것 같아서 여기로 옮긴다.