되면한다

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이전에 풀어봤던 문제인데, 백트래킹이랑 next_permutation을 이용한 순열 문제를 잘 못푸는 거 같아서 한번 더 풀고 정리했다. 1. 백트래킹 코드 arr = {1, 7, 9, 9} 이고 4개중 2개를 뽑는다고 가정하자. 이 때 {1, 9(첫번째)}, {1, 9(두번째)}는 같은 것이다. tmp를 설정해서 이번 순회에서의 arr[i]값을 저장하고, i가 1 증가했을 때, arr[i] (..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 들어온 연산자(+ + - x /)를 순서 상관없이 나열하는 것을 구현하는 게 핵심이다. 이를 위해 나는 백트래킹을 사용했지만, next_permutation을 사용하면 훨씬 간단하게 구현할 수 있을 것같다. 문제를 풀고 next_permutation을 다시 공부했는데, next_permutation이 순서 상관없는 순열이었다. 순서 상관 ..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 조건을 고려하여 정렬하는 문제이다. 1. 특징 1) 조건에 맞춰서 정렬 2. 구현 포인트 1) {1, 3, 3, 3, 2, 2, 2, 1, 1} 에서 마지막에 있는 1 두개도, 앞쪽에 1 1 1로 출력되어야한다. 다시말해 해당 수가 최초로 나온 위치를 기억할 필요가 있다. 이를 _map1에서 관리해준다. 이전에 나온적이 없는 수이면 (map에서 나온적이 없으면) cnt 값을 얻어서 _map1에 저장해준다. 나는 이 부분을 단순히 먼저 나오..

https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 간단한 정렬 문제인데, sort함수를 커스텀? 하는게 헷갈려서 정리했다. 사진은 https://www.youtube.com/watch?v=dq5t1woLJMw&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=16 에서 캡처했다. 1. 아래 사진에서 cmp 함수에 따르면, a가 b의 앞에 와야하는 경우는 b가 a보다 큰경우이다. 따라서 오름차순 정렬. cf) ..

https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 구현 아이디어를 떠올리지 못해서 못풀었다. 풀이는 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/13335.cpp 을 참고했다. 1. 특징 1) 구현 2. 구현 포인트 1) 다리의 칸별 무게를 배열로 저장함 2) 트럭의 이동을 진행할 때, 1번의 배열을 이..

https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 정사각형 4개를 이어 붙인 도형(테트로미노)를 회전, 대칭 시켜 보드(입력으로 받음) 위에 놓는다. 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력. 백준 18808 스티커붙이기와 비슷하게 구현하였다. 못풀어서 https://www.acmicpc.net/problem/20166 코드를 참고했다. 1. 특징 1) 백트래킹...? 재귀...? dfs...? 2) 해시 2. 삽질 포인트 1) 처음에 아래와 같은 코드로 작성했다. 문자열을 입력받으면, 각 좌표마다 돌면서 갈 수 있..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 입력값이 주어졌을 때, 2048 게임룰로 게임을 진행하고, 블록의 최댓값을 출력한다. 1. 특징 1) 백트래킹 2) 구현 2. 구현 포인트 1) 백트래킹: 문제 조건으로 최대 다섯번(좌,우, 상, 하)을 움직일 수 있다고 했다. 좌좌좌좌좌 -> 좌좌좌좌우-> ... -> 하하하하하. 이 경우를 찾아내기 위해 백트래킹을 사용했다. 2) 좌, 우, 상, 하로 움직였을 때:..

https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 스티커를 붙이는데 1) 위쪽 그리고 왼쪽 부터 붙인다 2) 스티커를 90도씩 회전할 수 있다 3) 붙일 곳이 없다면, 버린다. 못 풀어서 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/18808.cpp 를 참고했다. 1. 특징 1) 구현 2. 삽질 포인트 1) 회전 구현: 회전 구현 하는데 x, y좌표값이..