🤔 PS(Problem Solving)/백준(BOJ)

[백준/java] 15651 - N과 M (3)

문제 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 코드

[백준/java] 15649 - N과 M (1)

문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 코드() *가 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 11657 - 타임머신

문제 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 분류 : 벨만-포드 알고리즘 최단거리 찾기 + 음의 가중치 이므로 벨만포드 알고리즘을 사용합니다. 코드(O((n^2)*m) *O((n^2)*m이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 1012번 - 유기농 배추

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 풀이 분류 : 그래프, DFS 1. 밭을 나타낼 int 2차배열, 방문체크할 bool 2차배열을 선언합니다. 2. field[0][0] ~ field[M-1][N-1] 까지 for문으로 돌면서,..

[백준/c++] 11729번 - 하노이 탑 이동 순서

문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 풀이 분류 : 분할 정복 주어진 예제로 하노이의 탑 원리를 생각해봅니다. (1)원판의 갯수가 1개일 경우 -하나뿐이므로 3번기둥으로 바로 옮깁니다. 1 3 (2)원판의 갯수가 2개일 ..

[백준/c++] 1107번 - 리모컨

문제 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 풀이 분류 : 완전탐색, 수학 코드(O(nm)) *O(nm)이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 10819번 - 차이를 최대로

문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 분류 : 완전탐색 무작위로 나열된 수열에서 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 위 식의 최댓값을 구하는 문제입니다. 1. algorithm헤더의 next_permutation함수를 사용하여 무작위의 수열을 만듭니다. 2. 무작위로 만들어진 수열에 위의 식을 대입하여, 가장 큰 값이 나올때마다 최댓값을 갱신해줍니다. 코드(O(n+1)!) *O(n+1)!이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 10610번 - 30

문제 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는 www.acmicpc.net 풀이 분류 : 그리디 30의 배수이면서, 최대인 값을 찾아야 합니다. 1.30의 배수는 끝자리가 무조건 0으로, 입력값에 0이 있는지 확인합니다.(없으면 -1 출력) 2.자리수를 내림차순으로 정렬합니..

[백준/c++] 10971번 - 외판원 순회2

문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이 분류 : 완전탐색+dfs 코드(O(n)?) *O(n)이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 1525번 - 퍼즐

문제 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 분류 : 완전탐색 0만 3x3 위치로 옮기는게 아니라, 퍼즐판까지 1 2 3 4 5 6 7 8 0 순으로 맞춰야 하는 것이 이 문제의 핵심이었습니다. + bfs 결국 입력값을 123456780의 순서로 만들수 있는지를 체크하면 되었습니다. 1. 입력값을 string 문자열로 초기화하되, 0은 9로 치환해줍니다. 2. 처음 입력받은 문자열을 큐에 넣어줍니다. 3. 큐에서 pop한 문자열에서 9의 위치를 찾고, 9와 상하좌우를 스왑합니다. 4. 스왑으로 새로 만들어진 string문자열이, 캐시의 key로 이미 등록되어있는지 체크합니..