전체 글168 [백준] 4179번 불! www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 생각해낸 방식이 마음에 들어서 포스팅해놓으려한다. 방식은 조금 복잡한데 옛날에 풀었던 것보다 시간이 1/4정도 줄었다. 큐를 하나만 이용해서 풀었다. 말로 어떻게 풀어야될지 잘 모르겠는데 시간에 따른 J와 F를 J1,J2,J3... 과 F1,F2,F3...로 표현하겠다. 1. 처음 큐에 F1F1J1과 같이 F를 앞에 J를 제일 뒤에 넣어준다. (불을 먼저 번지게 하고 사람이 움직이는게 더 간단하다.. 2021. 3. 13. [백준] 1600 말이 되고픈 원숭이 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 아이디어는 어렵지 않은데 코드로 구현해내는 방식이 어려웠다. cur.first.first 와 cur.first.second 에 각각 원숭이의 x, y좌표를 cur.second.first 와 cur.second.second에 각각 말처럼 이동한 횟수, 총이동 횟수를 저장하였다. BFS과정을 통해 진행되며 도착점(오른쪽 하단)에 최초로 도착하게 될 때, cur.second.second + 1의 값을.. 2021. 3. 10. [백준] 6198번 옥상 정원 꾸미기 www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 꼭 기억해놓으면 좋을 것 같은 방식이다. 스택에서 말고도 여기저기 많이 쓰여서 몇번 찾아서 다시 봤는데도 암기가 잘 안되서 그냥 외우겠다는 마인드로 정리한다. 아이디어는 다음과 같다. (스택함수가 아닌 배열을 스택식으로 사용했다.) 여러개의 건물이 있을 때 N번째의 건물을 볼 수 있는 것은 N번째 이전의 건물 중 N번째보다 높은 건물만 N번째를 볼 수 있다. (같아도 안됨) 따라서 N번째 이전에 존재하는.. 2021. 3. 8. 스택 큐 덱 연결리스트에 개념자체가 쉬워서 나중에 보고 기억하기 쉽게 한줄로 정리 스택 = LIFO(Last In First Out) 큐 = FIFO(First In First Out) // 제일 앞과 뒤의 데이터 확인 가능 덱 = 앞뒤로 다 넣고 뺄 수 있음(자유로운 자료구조) 2021. 3. 8. [백준] 1406번 에디터 www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 연결 리스트의 기본 개념을 물어보는 문제였다. 처음 공부할때 커서의 위치가 너무 헷갈려서 힘들었던 기억이 난다. 그래서 메모장을 연상하면서 이해하기 위해 노력했다. 결과적으로 커서가 가리키는 칸이 a이고 뒤의 칸이 b라면 a의 뒤에, 즉 a와 b사이에 커서가 존재한다. (a|b) 또한, 커서가 가르키는 칸에 값이 없다면(문자열 끝의 다음 커서 값) 그 칸 자체가 커서라 생각하면 위처럼 이해할 수 있다. 배열 cu.. 2021. 3. 6. [백준] 3273번 두수의 합 www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 처음에 짰던 코드는 입력을 배열에 저장 후 2중 for문을 통해 O(N^2)으로 원소를 2개씩 조합하여 확인하는 것이었다. 검색을 통해 O(N)으로 처리한 방식이 인상적이였어서 개인적으로 남겨놓고 싶다. 1. 입력을 배열에 저장후 sort를 통해 배열을 오름차순으로 정리한다. 2. 2개의 커서를 배열의 시작값과 끝값에 존재시키고 반복문을 실행한다. 3. 2.. 2021. 3. 6. 이전 1 ··· 25 26 27 28 다음
