Door

결과값이 같더라도 최적화 여부에 따라서 좋은 프로그램인지 아닌지가 갈립니다. 컴퓨터는 한정된 용량을 가지고 있기 때문에 용량을 최대한 적게 먹도록 최적화를 시킨다면 컴퓨터입장에서는 부담이 덜합니다. 그런데, 일각에서는 이렇게 주장합니다. "이제 컴퓨터 용량도 충분히 커졌고 CPU GPU 등의 속도도 빨라졌는데 굳이 최적화가 의미가 있나?" 물론 어느정도는 일리가 있지만 그럼에도 프로그램 최적화는 여전히 중요합니다. 이게 왜 중요할까요? 대한민국 민속놀이. 스타크래프트를 볼까요? 여러분들이 2030라인이라면 초중고 컴퓨터 시간에 선생님 몰래 스타 한판은 해보셨을 겁니다. 그 당시 낡은 학교 컴퓨터실에서는 메이플,카트같은 게임은 돌아갈리가 없었지만 스타크래프트는 문제없이 돌아갔습니다. 스타에 있는 근거리 통..

노베이스도 이해하는 공학이야기 2022. 5. 16. 19:50

https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 이 문제에서 핵심은 어떻게 바람이 퍼지는 걸 구현해낼 것인가입니다. 이 아이디어를 구하기 위해 한참 고민하다가 구글링으로 아이디어를 얻었습니다. 여기서 중요한 부분은 ㄱ벽과 ㄴ벽에 대한 부분입니다. 사실, 벽만 따로 구하면 '이거 별거없는데?' 라고 생각이 들지만 저 벽때문에 상당히 스트레스를 받습니다. 먼저 q에 첫 온풍기 발사위치를 넣어줍니다. 그리고 pop을 시킨 다음에 중간 위 아래 각각을..

알고리즘 공부 2022. 4. 11. 23:24

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 이 문제는 이름 그대로 사람을 낚는 문제. 정답률이 25%이하인 문제치고 문제에서 요구하는 것이 어렵지 않아 보였습니다. 저도 요구하는 걸 다 나열해보고 '별거 아니네' 하고 넘어갔다가 시간초과가 떠서 참 애를 먹었습니다. 풀다보니깐 최적화라는 관점에서 문제를 공부하게 되었습니다. 구현할 건 크게 3가지 1. 낚시왕이 이동 2. 현재 위치한 열에서 가장 땅에 가까운 상어를 포획..

알고리즘 공부 2022. 4. 10. 23:19

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net easy하다는 문제명과 달리 그렇지 못한 문제. 이 문제는 DFS로 접근합니다. 상하좌우로 움직이는 경우가 있고 각각을 총 5번 움직이면 최대를 구합니다. https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-15683%EB%B2%88-%EA%B0%90%EC%8B%9C%ED%8C%8C%EC%9D%B4%EC%8D%AC..

알고리즘 공부 2022. 4. 10. 18:27

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 저같은 경우에는 문제 예시는 다 풀었는데 제출해보니 시간초과로 헤매여서 인터넷의 도움을 받았습니다. 이 문제에서 풀어야할 것은 1. 바이러스 활성화시킬 케이스 구하기 2. 각각의 케이스별로 바이러스 활성화시키고 몇 초 걸리는지 계산하기 3. 그 중 최솟값 구하기 1은 백트레킹도 가능하지만 저는 이런 류의 문제에 대해서 바로 combination이 떠올랐습니다. 2022.03.24 - [알고리즘 공부] - ..

알고리즘 공부 2022. 4. 4. 00:03

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 뱀이 움직이는 걸 표현하는 문제입니다. 여기서 구현할 포인트는 뱀의 몸통과 이동시의 뱀의 몸통입니다. 저는 이걸 구현하기 위해 deque의 appendleft와 pop을 사용했습니다. deque에서 맨 앞이 머리쪽이고 맨 뒤가 꼬리라고 놓고 생각했습니다. 문제를 읽어보면 사과가 있으면 머리만 움직이고 사과가 없으면 꼬리가 위치한 칸을 비워준다고 되있습니다. 사과가 있던 없던 움직이면 deque앞에 app..

알고리즘 공부 2022. 4. 3. 21:41

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 우선 그림을 보자마자 이게 뭔가 싶은 문제입니다. 보통 길찾기문제라면 좌표평면이라든가 사각형좌표로 많이 있는데 이건 뭐지... 싶었던 문제. 말을 움직이는 케이스는 dfs로 풀면 됩니다. 2022.03.06 - [알고리즘 공부] - [백준 14888번] 연산자 끼워넣기 [백준 14888번] 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ ..

알고리즘 공부 2022. 4. 2. 11:18

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제의 예제4를 쭉 캡처해봤습니다. 이 문제를 풀 때 해결해야할 포인트 1. 원판돌리기 2. 같은 거 지워주기 3. 평균구한 후 더하거나 뺴기 1은 문제 경험이 있다면 비교적 간단합니다. '어떻게 리스트를 돌리지? 으...복잡해' 물론 리스트를 직접 돌려도 괜찮지만 실수를 간혹하실 수 있습니다. 그래서 간단하게 원판을 deque로 받은 이후에 rotate()를 사용했습니다. 물론 ..

알고리즘 공부 2022. 3. 29. 21:59