📁문제 풀이/🧩Baekjoon

[JAVA] 백준 16926 배열 돌리기 1 | 구현

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 문제 해결 포인트 - 구현 문제 - 사각형을 한 겹(?)씩 방문하며 전부 돌린다. => 이 수행을 R번 - 각 사각형을 돌릴 때 왼쪽 위의 값을 따로 저장 하고 각 면에 대해 for문을 돌린다. - 윗줄, 오른쪽줄, 아래줄, 왼쪽줄을 돌림으로써 왼쪽 위 값..

[JAVA] 백준 2493 탑 | Stack

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 해결 포인트 - Stack을 이용해 먼저 쌓인 값 중 (가장 가까운) 본인보다 큰 값 찾기 1. Stack이 비어 있는지 아닌지 판별 2. 비어있다면 0 출력 & 본인 push VS 비어있지 않다면 Stack에서 본인보다 큰 값을 찾을 때까지 pop 3. 본인보다 큰 값을 찾았다면 출력하고 본인 push 4. 1 ~ 3 반복 작성 코드 imp..

[JAVA] 백준 12891 DNA 비밀번호 | 슬라이딩 윈도우

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 문제 해결 포인트 - 슬라이딩 윈도우 알고리즘을 이용하여 고정된 크기의 구간 결과를 계산 - 단순 반복문을 통해 매번 문자열의 특정 구간 발생한 문자 개수를 세면 시간 초과 발생 - P 길이만큼 각 문자의 발생 횟수를 카운트 하여 저장한다 - 0부터 N-P까지 한칸씩 이동하면서 해당 구간 앞 문자열은 제거, 가장 뒤 문자열 한..

[JAVA] 백준 2961 도영이가 만든 맛있는 음식

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 문제 해결 포인트 - DFS, 완전 탐색 - 신맛과 쓴맛을 저장한 배열을 하나씩 방문하며 넣을지 안 넣을지 확인한다 - 모든 음식을 넣을지 안 넣을지 확인하였을 때, 쓴맛과 신맛의 차이가 answer보다 작다면 answer를 업데이트 - 완전 탐색 후 answer를 출력 작성 코드 import java.util.*; import..

[Python] 백준 1654 랜선 자르기 | 이진 탐색 | 시간 초과

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 해결 포인트 - N의 범위가 크므로 이진탐색으로 풀이해야 한다. - 길이가 가장 긴 랜선을 end값, 0을 start값으로 두고 중간 값으로 mid를 선언한다. - start와 end가 교차되는 지점에서 종료하는 while문을 작성하여 최대 길이를 찾는다. - mid를 기준으로 모든 랜선 별 생성되는 랜선 개수를 모..

[Python] 백준 9655 돌 게임 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 해결 포인트 - DP(다이나믹 프로그래밍) - 기록을 위한 dp 배열 : 0은 SK, 1은 CY를 의미 - N이 1일 때 : SK N이 2일 때 : SK -> CY N이 3일 때 : SK 또는 SK -> CY -> SK 이므로 결론적으로 SK N이 4일 때 : 1일 때 결과와 다른 사람 또는 3일 때 결과와 다른 사람, 결론적으로 CY ...... - 점화식 N이 4이상일 때, ai = (ai-1 + 1) % 2 또는 ai = (ai-3 + 1) % 2 작성 코드 ..

[Python] 백준 2579 계단 오르기 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 해결 포인트 - 최대 300개 계단의 점수를 기록할 배열 미리 선언 - 계단 별 점수 기록 배열과 dp 기록을 저장할 배열 2개 필요 - 계단 1 : 본인 점수 계단 2 : 계단 1 + 본인 점수 계단 3 : max(계단 1 + 본인 , 계단 2 + 본인) - 점화식 : max( 본인 이전 계단 밟고 본인 , 본인 이전 계단 밟지 않고 본인) ai = ma..

[Python] 백준 1966 프린터 큐

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 해결 포인트 - 자료구조 큐 - 순서를 나타내는 두개의 변수를 잘 구분하여 인지하여야한다. * 남은 우선순위 중 최대값이므로 출력하는 순서 * 초기 큐의 각 문서 순서 - 큐에 (중요도, 위치) 값을 삽입한다. 위치값을 삽입하는 이유는 M과 비교하여 찾는 문서인지 확인하기 위함 - 초기 큐를 내림차순으로 정렬한다. 매번 큐의 최대값을 구하는 것보다..

[Python] 백준 16953 A -> B | 그리디 알고리즘 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 해결 포인트 - 그리디 알고리즘, BFS - 입력 값에 대해서 두개의 연산을 연쇄적으로 수행함으로 모든 경우의 수 확인 - 원하는 값이 발견되면 출력 후 즉시 종료( 가장 먼저 발견되는 연산 횟수가 가장 작은 연산이므로) : 그리디 - 연산 값이 타켓 값보다 크다면 해당 서브 트리에 대해서 더이상 탐색하지 않도록 한다. 작성 코드 from collections import deque a, b = map(int, input().split()) que = deque() #..