난이도: Lv.3유형: BFS/DFS해결 여부: 한번 틀리고 해결 아이디어BFS/DFS 형태로 다음 단어 탐색하면서 지워나간다.오답 이유 혹은 알게 된것아이디어 자체는 맞았으나 문법에서 한군데 틀려서 보고 고쳐야 했다.words = [i for i in words if i != temp] 라고 했다가 틀렸다. words=[i for i in words if i not in temp] 라고 해야 했다. temp 는 리스트니까 무조건 저렇게 해야했는데 아예 자료형이 다르니까 != 는 당연히 True뜨고 무한루프 걸려서 틀림여기서 시간 개선하려면 from collections import deque 한 후에 deque에다가 집어넣고 popleft() 쓰는게 더 시간이 빠르다고 한다. 그리고 set()이 Li..
Algorithm/BFS,DFS
난이도: Lv.2유형: BFS/DFS해결 여부: 통과아이디어경우의 수를 BFS 써서 풀어라 이거 같은데 나는 어 그냥 쌩으로 풀어버렸다. 복잡도는 차이가 없어서..?오답 이유 혹은 알게 된것처음에 빠른 방법 없나 DP나 부분합 고민해봤는데 그냥 모든 경우의 수 다하는 수밖에 없다고 생각했다.sort 후 rfind와 find 써서 최종 제출하려 했으나 문자열이 아닌 그냥 리스트에서는 find를 지원 안하는 것도 있고 아 걍 count쓰면 편하겠다 싶어서 count로 쉽게 풀어버렸다이 방식으로 한건 대충 case 크기 보았을떄 2^20 이면 대충 1000 * 1000 이니까 메모리 약 100만칸 . 파이썬 배열 한칸에 36byte로 약 40Mb. 만약 범위가 25개면 메모리초과 오류가 날 거라고 했다.그래서..
난이도: Lv.2유형: DFS/BFS해결 여부:오답아이디어2차원 배열에서 목적지까지 가는 최단거리 숫자 쓰는 간단한 문제오답 이유 혹은 알게 된것이전에 풀었떤 문제 응용하는 것과 비슷했다. 근데 일부분에서 걸려서 오래걸렸다.파이썬에는 NUll 대신 None을 쓴다는 점. 그리고 배열 값이 자동으로 0으로 초기화 된다는 점 때문에 초기화에 좀 걸렸다. 무엇보다 2차원 배열 하는과정에서 또 현기증 도져서 dx,dy 잘못더해서 찾는데 걸렸다. 만약에 성능을 높이고 싶으면 collections에서 deque 쓰는게 list에서 pop() 보다 deque popleft() 성능이 좋다고 한다. 여담으로 이런 코드로 통과받는 미친놈도 있었다. eq 로 object == ? 들어갈때 쓸 수 있는 코드같다. 파이썬 더..
난이도: Lv.2유형: bfs / dfs해결 여부:오답아이디어2차원 리스트에서 인접한 값들의 합을 리스트로 뽑아라 라는 문제다. 문제 자체는 간단하다.. 오답 이유 혹은 알게 된것파이썬으로 bfs 하는 문제에 대한 자각이 없어서 for문으로 아래방향, 오른쪽 방향으로 쭉 돌리면 되겠지 생각했다가 그렇지 않은 모양도 있다는 걸 깨달았다.처음에는 똑같은 2차원 리스트를 하나 더만들어서 방문여부를 확인하려 했다. 근데 그냥 방문하면서 해당 위치를 'X'로 바꾸는게 공간복잡도 적으로도 훨씬 효율적이었다. 2차원 배열의 합은 numpy 모듈사실 문제 자체에 주어진건 1차원 배열이고 그 안의 문자열이라서 따로 처리를 해주어야 했다. 그냥 arr[i][j] 이런식으로 문자열 바꾸려고 하면 에러가 났다. maps = ..
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net C++로 작성한 백준 문제 7569번 토마토에 대한 문제 풀이다. 골드 5 문제로 그래프 이론, 그래프 탐색, 너비 우선 탐색이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 ..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net C++로 작성한 백준 문제 7576번 토마토에 대한 문제 풀이다. 골드 5 문제로 그래프 이론, 그래프 탐색, 너비 우선 탐색이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net C++로 작성한 백준 문제 1697번 숨바꼭질에 대한 문제 풀이다. 실버 1 문제로 ~이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net C++로 작성한 백준 문제 2667번 단지번호 붙이기에 대한 문제 풀이다. 실버 1 문제로 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서..
