빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 16926(파이썬) - 배열 돌리기 1

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 이 문제는 간단한 구현 문제였다. 배열을 돌리거나 할 때 중요한 점은 하나의 temp 변수를 만들어주고 처음 시작할 때 값을 넣어준 뒤, 배열을 돌리다 보면 비어있는 배열이 생기는데 그때 temp변수 안에 저장해두었던 값을 빈 배열에 넣어주면 된다. 까다로웠던 점은 안에 있는 배열도 돌려줘야 하기 때문인..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 16198(파이썬) - 에너지 모으기

https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 이 문제는 일고나서 아 DFS로 풀어야겠다 라고 생각했다. 최대 입력값도 작고, 생각 해봤을 때, 한 경로로 깊이 들어가서 값을 저장하고, 또 다른 한 경로로 깊이 들어간 뒤 값을 저장해서 비교를 통해 갱신해가면서 풀면 된다고 생각했다. DFS로 방향을 잡은 뒤 부터는 수월했지만 문제 조건을 보면 data[i] 를 계산 뒤에 삭제 하라고 했는데, 삭제를 하고 DFS 재귀를 실행시켜준 뒤, 다..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 14226(파이썬) - 이모티콘

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 이 문제는 처음 보고 그리디인가...? 했는데 그리디가 불가능한 문제였다. 그리디를 사용해도 되나..? 하는 문제들을 보면 거의 BFS나 DP 문제인 거 같다. 문제를 읽어보면 최단시간을 구해야 하는데 '최단'이라는 키워드가 나오면 BFS를 생각해보는 게 좋은 거 같다. BFS로 풀어봐야지 했는데 감이 오질 않았었는데 현재 화면의 이모티콘 개수와 클립보드에 있는 이모티콘 개수를 각각 처리하는 방법을..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1987(파이썬) - 알파벳

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 보고 이 문제야말로 DFS를 이용하는 문제다 라고 생각했다. 근데 생각해보니까 BFS로도 풀 수 있다ㅎㅎ 여기서 중요한점은 맨 처음에 리스트를 하나만들어서 알파벳이 사용됐을 경우 리스트에 넣어서 만약에 DFS함수안에서 다음 탐색 x,y좌표에 리스트에 있는 알파벳이 없을 경우 DFS 재귀를 돌렸는데 이렇게 하니까 시간초과가 발생하였다. 생각한 방법은 알파벳을 아스키코드를 이용해서 ..