전체 글

[1388] 바닥 장식(C++)

문제 바로가기 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다. 이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다. 기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 방 바닥의 세로 크..

[2470] 두 용액(C++)

문제 바로가기 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고,..

[7795] 먹을 것인가 먹힐 것인가

문제 바로가기 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1. 두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M..

[1966] 프린터 큐

문제 바로가기 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 ..

[10974] 모든 순열(C++)

문제 바로가기 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 출력 첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다. 해결 방법 내 코드 // [10974] 모든 순열 // 브루트포스, 백트래킹 #include using namespace std; bool visited[8]; int n, arr[8], tmpArr[8]; void dfs(int idx, int depth) { if(depth == n) { for(int i = 0; i < n; i++) { cout

[삼성 SDS] 2022 하계 알고리즘 특강 사전테스트 후기

🌳 테스트 정보 ✅ 총 5문제 ✅ 시간제한 없음(일주일 동안 알아서 풀면된다. 일주일 내내 푸는 것도 가능. 단, 한 문제당 2~3시간 정도 사용하는 것을 추천한다고 한다.) ✅ 언어(3가지): C, C++, Java 1, 2번은 구현 문제였고 체감 난이도는 실버 1~2였다. 구현 방법은 어렵지 않았지만 잘못 짜면 시간 초과가 발생하거나 놓치는 부분이 발생하기 쉬운 그런.. 3번은 잘 기억이 안 난다. 아마 보고 넘겼던 듯하다. 4번은 어떻게 풀지 한참 고민했는데 나중에 보니 최소 환승 알고리즘이라고 해서 이미 이 자체로 유명한 알고리즘이 있었다. 백준에 비슷한 문제가 있으니 풀어보면 좋을 것 같다. 🥇 [2021] 최소 환승 경로 🥇 [5214] 환승 🥈 [16166] 서울의 지하철 5번은 건드리지도 ..

[프로그래머스] 타겟 넘버

문제 바로가기 해결 방법 내 코드 #include #include using namespace std; int answer = 0; void dfs(vector numbers, int target, int sum, int idx) { if(idx == numbers.size()) { if(sum == target) { answer++; } return; } dfs(numbers, target, sum + numbers[idx], idx + 1); dfs(numbers, target, sum - numbers[idx], idx + 1); } int solution(vector numbers, int target) { dfs(numbers, target, 0, 0); return answer; }

[20291] 파일 정리

🌿 문제 [20291] 파일 정리 🌿 해결 방법 이 문제의 핵심은 파일 이름은 필요없고 오로지 '.' 뒤의 확장자만 필요하다는 것. 그래서 입력을 받을 때부터 전체 파일명을 전체 저장할 필요없이 확장자만 저장하면 된다. string 으로 파일명을 입력받으면 확장자를 한번에 빠르게 구할 수 있는데, 먼저 find 함수를 사용해서 '.'이 몇번째 인덱스에 있는지 찾는다. s.find(".") 그 다음 substr 함수를 사용해서 '.' 이후의 문자열을 한번에 구한다. s.substr(s.find(".")+1) 이렇게 확장자를 구했으면 map에다가 차례대로 저장해주면 된다. map은 key값을 기준으로 자동 정렬이 되어있는데 그걸 깜빡하고 벡터를 추가한뒤에 또 정렬을 하느라 시간, 메모리 모두 엄청나게 나왔었..