링크 https://www.acmicpc.net/problem/2178 난이도(solved.ac 참고) 실버1 풀이 이 문제를 왜 지금까지 안 풀었었는지 모르겠다. BFS(DFS도 쓸 수 있긴 함)의 너무 기본적인 문제라 쓰기도 좀 애매하긴 한데.. 값을 받아오고 각 위치별로 방문 여부를 확인하는 visited 배열을 선언해준다. 그다음 0, 0 위치에서 BFS 함수를 시작하면서 1) nx와 ny가 미로를 벗어났는지 확인 2) (nx,ny) 좌표를 이미 방문했는지 여부를 확인 3) 1, 2 모두 충족했을 경우 해당 좌표가 벽인지 확인(0이면 벽, 1이어야 지나갈 수 있는 길임) 이 경우 방문처리를 하고 큐에 지금까지 이동한 값인 distance에 1을 더한 값을 넣는다. 시작점도 거리에 포함한다고 했으므..

링크 https://www.acmicpc.net/problem/17086 난이도(solved.ac 참고) 실버2 풀이1(메모리 초과) 왜 메모리초과가 떴는지 이해가 안 간다.. 시간 초과도 아니고 메모리 초과라니. ans값을 심지어 배열로 두지도 않았고 상수로 두어 최댓값을 계속 업데이트하는 식으로 진행했는데? 메모리 초과가 뜬 원인을 아는 분이 있다면 댓글로 남겨주시면 좋겠다. 하.. 그래프탐색 문제를 오랜만에 푸니까 정신이 나갔나보다. visited 배열을 당연히 선언해줬어야 했는데 실수했다. 풀이2(AC) 풀이1에서 visited를 추가했다. 풀이3(AC) 위 풀이와는 다르게 1일 때 큐에 넣고 BFS를 함수 형태로 빼지 않고 바로 시작했다. 뭐 결국 거리의 최댓값을 구하는 것이니 어렵지 않았다만 ..

링크 https://www.acmicpc.net/problem/10942 난이도(solved.ac 참고) 골드3 풀이 질문의 수가 100만개까지 있을 수 있기 때문에 인덱싱을 하면 100% 틀린다. 특정 구간이 팰린드롬이기 위해서는 3가지 조건 중 하나를 만족해야 한다. 1) 구간의 길이가 1이어야 한다. - 구간의 길이가 1이라면 무조건 팰린드롬이다. 2) 구간의 길이가 2라면 두 값이 같아야 한다. - 숫자가 두개가 있을 땐 무조건 같을 경우에만 팰린드롬이 되며, 다르다면 팰린드롬의 조건을 만족하지 못한다. 3) 구간의 길이가 3 이상이라면, 구간의 시작점과 끝점의 값이 같으면서 그 두 점을 제외한 구간이 팰린드롬이어야 한다. - 1 2 1 3 1 2 1 에서 1 3 1 2 1을 떼서 봤다고 해보자...

링크 https://www.acmicpc.net/problem/12852 난이도(solved.ac 참고) 실버1 풀이 해당 위치에 방문하지 않았다는 전제 하에 되는 값(3으로 나눠떨어지거나, 2로 나눠떨어지거나, 1을 빼거나)을 다 넣어주는데, 값을 줄여가면서 지나가는 경로를 answer_arr에 하나씩 넣어준다. 큐에는 현재 숫자와 그 숫자에 오기까지의 경로가 담겨있다. 1이 되는 순간 함수를 마치고 숫자 및 그 숫자까지의 경로를 출력한다. 습관적으로 sys.stdin.readline을 사용했는데, input값이 줄줄이 들어오는 상황이 아니므로 굳이 쓰지 않아도 무방하다.

링크 https://www.acmicpc.net/problem/1294 난이도 플래티넘2 풀이 cmp_to_key를 좀 더 딥하게 사용해보는 문제를 찾아보다가 발견한 문제다. 핵심 아이디어는, 처음에 cmp_to_key로 제일 먼저 위치한 문자열 내의 문자를 하나씩 빼주면서 그때마다 다시 한 번 cmp_to_key를 진행하는 것이다. 매번 이렇게 진행하는 것이 답인 이유는, 단어를 어떻게 잘라야 하는지에 대한 설명이 없으므로(문제에서는 적절히 쪼갠다고 했으므로, 완전히 임의라고 봐야한다) 결국 모든 케이스마다 제일 앞에 나오는 값을 넣음으로써 해결할 수밖에 없기 때문이다. 아이디어가 문제였을 뿐.. 구현은 어렵지 않았다. temp라는 빈 문자열을 두고 cmp_to_key로 sort한 arr에 대해 첫번째..

링크 https://www.acmicpc.net/problem/16496 난이도 플래티넘5 풀이 functools 모듈의 cmp_to_key를 사용했다. 이 cmp_to_key는, 람다로는 불가능한 두 연산값들끼리의 비교를 할 때 유용하게 사용할 수 있다. 우선 문제 자체에 대해서는 그냥 수들을 이어붙여서 최댓값을 만들기만 하면 되는 문제였는데, 어떻게 최댓값을 만드는지를 생각하기가 어려운 문제였다고 생각한다. 결론부터 이야기하면 직접 두 숫자 a, b를 ab, ba 형태로 붙여봤을 때 값이 더 큰 경우에 해당하는 숫자가 앞으로 오도록 정렬 기준을 설정하면 된다. 그리고 이 ab와 ba의 크기를 비교하는 것을 cmp_to_key로 할 수 있다. arr내의 두 값을 이어 붙인 값이 클수록 앞으로 위치하게 ..

링크 https://www.acmicpc.net/problem/2589 난이도(solved.ac 참고) 골드5 풀이 n과 m이 각각 50까지밖에 안되는 것을 보고 브루트포스로 해도 되겠다는 생각이 들었다. 우선 아이디어는 각 위치별로 가장 먼 곳까지 가는 숫자를 찾아야 하기 때문에 L일 때마다 BFS를 실행하고 이중 배열을 초기화하여 최대값을 갱신해가는 것인데, 일반적인 BFS로만 풀면 PyPy3으로만 통과할 수 있다. 코드에도 있듯이, 좌우 혹은 상하가 모두 L이라면 그 자리는 가장자리가 아니기 때문에 탐색을 넘김으로써 불필요한 배열 재선언 및 BFS의 실행을 방지할 수 있다.

링크 https://www.acmicpc.net/problem/15591 난이도(solved.ac 참고) 골드5 풀이 BFS 문제이다. 그래프 탐색 문제를 너무 오랜만에 풀어서 갈피를 못잡았다. 인접 그래프 먼저 만들어주고, 노드 방문 여부를 확인하기 위해 visited 배열을 선언해줬으며, 큐에 처음으로 들어갈 값에는 유사도가 존재하지 않으므로 갱신해주기 위해 float('inf')를 넣었다. pop한 값을 기준으로 그래프의 인접 값을 탐색하면서 유사도를 더 낮은 값으로 갱신해주며, 그 갱신한 유사도가 K보다 클 경우에는 큐에 (새로운 노드, 새로운 유사도)를 넣어주고, 방문 처리한다음 갯수에 해당하는 result의 값을 1 더해준다.

링크 https://www.acmicpc.net/problem/15655 난이도(solved.ac 참고) 실버3 풀이 s에 숫자 하나씩을 넣은 뒤 그 길이가 m이 된다면 우선 result에 넣는다. result라는 배열을 하나 더 만든 이유는 숫자의 순서만 바뀌었을 경우에는 중복으로 들어갈 수 없다는 점을 고려해야 했기 때문이다. (1 7이 들어간 후 7 1이 들어가지 못하게 하기 위함) 기본적인 백트래킹 문제였다. 이전에는 N과 M 시리즈를 전부 순열, 조합, 중복순열, 중복조합으로 풀었다가 정도가 아님을 체감하고 백트래킹으로 다시 풀었다.

링크 https://www.acmicpc.net/problem/13702 난이도(solved.ac 참고) 실버3 풀이 이분탐색 문제인데, 매번 루프를 돌 때마다 해당 mid 값으로 몇 명을 줄 수 있는지를 계산한 뒤(10행) 그 값이 사람 수(K)보다 작다면 점점 용량을 줄이며 반대로 사람 수보다 크거나 같을 경우에는 result값에 그 용량을 대입한 뒤 점점 용량을 키워가는 방식으로 진행한다.