본문 바로가기

분류 전체보기

 (386)
[boj] 백준 12856 평범한 배낭 - 동적 프로그래밍 [문제] https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net [풀이] 0/1 knapsack 문제로 잘 알려져있는 동적 프로그래밍 대표 문제이다. 물건을 쪼갤 수 있는 경우 greedy로 풀지만 0/1로 나눌 수 없다면 동적 프로그래밍으로 해결한다. dp[i][j] 배열은 i 번째만큼의 물건을 배낭에 넣을 수 있고, j 만큼의 무게를 견딜 수 있다고 할 때 배낭에 있는 물건들의 최대..
[boj] 백준 14500 테트로미노 - dfs, 브루트포스 [문제] https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net [풀이] 처음에는 dfs 문제구나 싶어서 단순하게 풀었다가 뒤늦게 ㅜ 모양의 테트로미노가 dfs로 불가능하다는 걸 깨달았다. 따라서 나머지는 depth가 4인 dfs로 해결하고, 예외인 ㅜ 모양에 대해 ㅜ, ㅗ, ㅏ, ㅓ 모두 고려해서 브루트포스로 조건을 걸어 해결하면 된다. [코드] #include #include #include #include using namespace::std; ..
[boj] 백준 3190 뱀 - 시뮬레이션 [문제] https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net [풀이] 시뮬레이션 문제로 주어진 조건을 잘 구현해내면 된다. 앞서 풀었던 로봇청소기와 같이 방향을 다루기 때문에 dx, dy 배열을 미리 선언해 놓고 사용하는 것이 좋다. push와 pop을 front, back 모두에서 할 수 있는 자료구조인 deque을 이용해 뱀의 머리와 꼬리 위치를 저장해두는 것이 키포인트다. visited 배열을 이용해 뱀이 현재 좌표에 위치해 있는지 표시해줬다. 주의..
[boj] 백준 14503 로봇 청소기 - 시뮬레이션 [문제] https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [풀이] 문제에 나온 구현 방식 그대로 시뮬레이션 코드를 짜되, 시간 초과가 나지 않도록 리팩토링 하는 과정이 필요했다. 청소가 가능하면 바로 그 방향으로 이동하여 청소를 계속하고(2-a) 청소가 불가능하면 다시 회전하여 탐색한다.(2-b) 네 방향을 모두 탐색할 동안 청소를 하지 못하는 경우에는(2-c) 후진을 한 위치가 벽인지 확인하고, 벽일 경우 while문을 빠져나와 종료된다.(..
[boj] 백준 15686 치킨배달 - DFS, 조합 [문제] https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [풀이] 치킨거리의 합을 가장 작게 만드는 m개의 치킨집을 선택해야 한다. 이는 곧 (1,2,3)을 선택하나 (2,1,3)을 선택하나 똑같기때문에 조합을 만든 후 비교해야 한다. 조합에 대해서는 dfs를 이용해 구현 가능하다. i 번째 치킨집이 조합에 포함되면 check[i]를 true로 바꿔주고 m개의 치킨집에 대한 조합이 완성될 때까지 반복한다. m개의 치킨집에 ..
[boj] 백준 10026 적록색약 - BFS [문제] https://www.acmicpc.net/problem/10026 [풀이] BFS 또는 DFS로 풀 수 있다. 이전 같은 유형의 문제와 비슷하게 같은 색의 약이 들어있는 구역에 대해서 queue에 집어넣어 모두 방문을 해주고, 방문하지 않은 다른 색의 약에 대해 count를 증가시켜주며 구역의 수를 구한다. 적록색 약의 경우 R과 G를 구분하지 못하므로 section 배열을 이 두 약이 같게 취급되도록 변경해준다. visited 배열 초기화하는 것 잊지 말 것! [코드] #include #include #include #include #include using namespace::std; int n; char section[100][100]; int dx[] = { 0, 0, 1, -1 }; ..
CH7(7.4). 구조 분해 선언과 component 선언 - 구조 분해를 사용하면 복합적인 값을 분해해서 여러 다른 변수를 한꺼번에 초기화할 수 있다. 내부에서 구조 분해 선언은 관례를 사용하는데, 각 변수를 초기화하기 위해 다음과 같이 componentN이라는 함수를 호출한다. val (a,b) = p ---> val a = p.component1() val b = p.component2() data 클래스의 주 생성자에 들어있는 프로퍼티에 대해서는 자동으로 componentN 함수가 만들어진다. 구조 분해 선언은 함수에서 여러 값을 반환하게 할 때 유용하다. data class NameComponents(val name:String, val extension: String) fun splitFilename(fullName:String): NameCompon..
[boj] 백준 9251 LCS - 동적프로그래밍 [문제] https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [풀이] 최장 공통 부분 수열이란 연속되어 있지 않아도 되는 공통된 문자열을 의미한다. 예를 들어, ACAYKP와 CAPCAK의 경우 ACAK가 연속되지는 않아도 공통된 문자열로 포함되어 있는 LCS다. LCS는 문자열 a,b가 있다고 했을 때, a를 기준으로 b 문자열을 비교해 나가면서 같은 문자인 경우 카운트해줘야 하므로 이전까지의 LCS ..

티스토리툴바