백준 글 모음
총 41개의 글이 있습니다.
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.
17070번 - 파이프 옮기기 1
크기 N × N 격자에서 파이프를 이동시키는 경우의 수를 구하는 문제 파이프는 항상 2칸을 차지하며, 방향은 총 3가지 시작 상태는 (1,1) ~ (1,2) 가로 방향 파이프의 한쪽 끝이 (N, N) 에 도달하는 모든 경우의 수를 계산 처음 문제를 읽었을 때는 👉 그래프…
4256번 - 트리
이진 트리의 전위 순회(preorder) 결과와 중위 순회(inorder) 결과가 주어짐 두 순회 결과로 만들어지는 트리는 항상 유일 해당 트리의 후위 순회(postorder) 결과를 구하는 문제 노드 개수 n ≤ 1000 이 문제를 처음 봤을 때는 👉 트리를 직접 복구한…
14499번 - 주사위 굴리기
크기 N × M의 지도 위에서 주사위를 굴리는 시뮬레이션 문제 주사위는 동(1), 서(2), 북(3), 남(4) 방향으로 이동 이동할 때마다 이동이 유효할 때마다 주사위 윗면의 값 출력 지도를 벗어나는 명령은 무시 이 문제를 처음 봤을 때 가장 고민했던 부분은 👉 주사위…
15652번 - N과 M (4)
주어진 n과 m에 대해 1부터 n까지의 수로 이루어진 비내림차순 수열을 구하는 문제 수열은 m개의 숫자로 이루어져 있고, 같은 수를 여러 번 고를 수 있음 수열은 비내림차순이어야 하며, 사전 순으로 출력해야 함 이 문제는 백트래킹 기법을 사용하면 해결할 수 있다.
2195번 - 문자열 복사
원본 문자열 S가 주어진다. copy(s, p) 연산은 목표는 S를 이용해 문자열 P를 만드는 것 단, copy 함수 사용 횟수를 최소화해야 한다. 이 문제를 보자마자 문자열 메서드를 활용하면 충분히 해결할 수 있겠다고 생각했다. 처음에는 contains()를 사용하려 했지만,
24042번 - 횡단보도
N개의 지역(1번부터 N번까지)이 있고, 이들을 잇는 M개의 횡단보도가 있음 각 횡단보도는 1분간 파란불이 들어오고, M분 주기로 반복됨 i번째 입력은 i, i+M, i+2M, ...
10868번 - 최솟값
이 문제는 모의 코테를 하면서 세그먼트 트리라는 소리를 듣자마자 가볍게 패스했던 문제였다. 세그먼트 트리를 한번도 배워본적이 없어서 이번 기회에 새롭게 공부를 해봤다. 세그먼트 트리는 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데…
20293번 - 연료가 부족해
처음에는 간단한 dfs 문제라고 생각하고 dfs로 코드를 짰다 초기 위치에서 가지고 있는 연료(have)와 필요한 연료(need)를 둘 다 0으로 초기화하고, dfs로 탐색하면서 각 위치에 따라 have가 있다면 다음 위치로 이동하며 have를 1 차감하고, have가…
17182번 - 우주 탐사선
처음에는 그냥 플로이드로 모든 경로의 최단 거리를 구하고 각 위치에서 가지 않은 행성 중 최단 거리인 행성을 골라서 가는 방식으로 문제를 풀었다. 플로이드 함수 최단 거리 계산 근데 이건 아주 잘못된 접근이었다.
14863번 - 서울에서 경산까지
문제를 읽자마자 dp로 풀어야겠구나 라는 생각은 했는데, 어떻게 풀어야하나 고민을 했다. 근데 N과 K가 각각 최대 100과 100,000 이었기 때문에 2차원 배열로 해서 전체 탐색을 해도 시간 안에 충분히 할 수 있겠다 라는 생각이 들었다.
10159번 - 저울
무게가 서로 다른 N개의 물건이 있다. 일부 물건 쌍에 대한 저울의 결과를 가지고 있다. 각 물건에 대해 그 물건과 비교 결과 알 수 없는 물건의 개수 출력 백준을 대략 한달만에 푸는거라 재활 훈련 차 조금 쉬운 문제를 가져왔다. 처음에는 Union-Find로 풀어야하나?
2157번 - 여행
N개의 도시 중 M개 이하의 도시를 여행한다. 반드시 1번에서 시작해 N번에서 끝나야 한다. 오름차순으로 이동한다. 기내식 점수의 총합이 최대가 되도록 한다. 처음에 문제를 보고 bfs인가? dp인가? 약간 고민을 했다.
2011번 - 암호코드
A를 1, B를 2와 같이 Z까지 암호화를 한다. 암호화된 문장을 보고 해석할 수 있는 경우의 수를 구한다. 이 문제는 딱 보자마자 dp로 풀어야 겠구나 라는걸 알 수 있었다.
21606번 - 아침 산책
서현이는 아침 산책을 한다. N개의 장소를 N-1 개의 길의 트리로 나타낸다. 각 장소는 실내와 실외로 나눠진다. 시작점과 도착점은 실내로 해야한다. 경로의 중간에 실내가 있으면 안된다. 서로 다른 산책 경로가 몇 가지가 있을까?
11066번 - 파일 합치기
여러 개의 파일을 합쳐 하나의 파일을 만들려고 한다. 파일을 합치는 최소 비용을 구하라. 이 문제를 보자마자 우리가 알고리즘 시간에 배웠던 허프만 트리가 생각났다. 그래서 바로 우선순위 큐로 코드를 쉽게 짤 수 있었다.
12781 - PIZZA ALVOLOC
도윤이는 친구 3명과 함께 피자를 나눠 먹는다. 피자는 항상 볼록 다각형이다. 피자를 네등분해서 나눠 먹는다. 나누어진 피자가 4조각이 되는지 판단하자. 이 문제는 저번 시간에 발표했던 CCW를 활용하는 문제이다.
11758번 - CCW
3 점 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1 시계방향이면 -1 일직선이면 0 을 출력한다. 처음에는 이 문제를 보고 기울기를 활용해서 푸는거 아닌가? 라는 생각으로 접근했다.
10942번 - 팰린드롬?
홍준이가 자연수 N개를 칠판에 적는다. 명우에게 질문을 총 M번 한다. 질문은 두 정수 S, E (1 ≤ S ≤ E ≤ N)로 나타낸다. S번째 수부터 E번째 수까지 팰린드롬을 이루는지 확인한다.
11401번 - 이항 계수 3
자연수 N과 정수 K가 주어졌을 때 이항계수를 1,000,000,007로 나눈 나머지를 구해라 1 ≤ N ≤ 4,000,000 0 ≤ K ≤ N 이 문제는 알고리즘 시간때 배웠던 dp 알고리즘으로 풀면 되는 아주 간단한 문제 아닌가? 하고 신나게 바로 풀기 시작했다.
1655번 - 가운데를 말해요
N 개의 수를 외친다. 정수를 하나씩 외칠때마다 지금까지 말한 수 중 중간값을 말해야한다. 외친 수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말한다. 처음에는 그냥 막무가내로 정렬을 해서 가운데 출력하면 되는거 아닌가?
1956번 - 운동
V 개의 마을과 E 개의 도로로 구성된 도시가 있다. 도로를 따라 운동을 하기위한 경로를 찾는다. 사이클을 찾되 길이의 합이 최소가 되도록 한다. 경로를 찾을 수 없는 경우 -1을 출력한다.
4195번 - 친구 네트워크
어떤 사이트의 친구 관계가 생긴 순서대로 주어진다. 두 사람의 친구 네트워크에 몇 명이 있는지 구하라. 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에 친구 관계의 수 F ( ≤ 100,000) 가 주어진다.
1197번 - 최소 스패닝 트리
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하라 정점의 개수 V (1 ≤ V ≤ 10,000) 간선의 개수 E (1 ≤ E ≤ 100,000) E 개의 줄에 각 간선에 대한 정보 A, B, C 가 주어진다.
10830번 - 행렬 제곱
크기가 N * N인 행렬 A가 있다. A의 B제곱을 구하라. 각 원소를 1,000 으로 나눈 나머지를 출력한다. 2 ≤ N ≤ 5 1 ≤ B ≤ 100,000,000,000 옛날에 풀려고 문제를 읽었다가 B의 범위를 보고 바로 도망쳤던 문제이다.
1774번 - 우주신과의 교감
황선자씨는 N-1명의 우주신과 교감을 할 수 있다. 황선자씨나 우주신들이 연결된 통로 M개가 존재한다. 아직 연결되지 않은 우주신들이 연결되기 위해 필요한 통로의 최소 길이를 구하라 문제를 읽다가 재밌어 보여서 풀기 시작했는데 풀다 보니 얼마 전에 알고리즘 수업 시간에 배웠던…
17845번 - 수강 과목
첫줄에 최대 공부시간 N, 과목수 K가 주어진다. K개의 줄에 중요도, 필요한 공부시간이 주어진다. 공부 시간의 한계를 초과하지 않으며 과목의 중요도 합이 최대가 되도록 선택해서 수강하자.
2186번 - 문자판
알파벳 문자가 한칸에 하나씩 적혀있는 NxM크기의 문자판이 있다. 임의의 칸에서 시작하여 상하좌우 K개의 칸까지 이동하며 문자를 모은다. 반드시 한 칸 이상 이동하며, 같은 자리에 머물 수 없다. 같은 칸을 여러 번 방문할 수 있다.
23631번 - 진심 좌우 반복뛰기
진심 좌우 반복뛰기한 거리의 총합이 Nm이상이면 “대머리”가 된다 진심 좌우 반복뛰기는 처음 x=0에서 시작 오른쪽으로 Km 뛴 다음 방향을 바꾼다. 대머리가 되지 않기 위해 (N-1)m만큼만 뛴다.
1446번 - 지름길
지름길의 개수 N, 고속도로의 길이 D가 주어진다 N은 12 이하인 양의 정수 D는 10,000보다 작거나 같은 자연수 N개의 지름길의 시작위치, 도착위치, 길이가 주어진다. D까지 이동하기 위한 거리의 최솟값을 구하라 이 문제는 딱 봐도 다익스트라로 푸는 문제인 것 같다.
10819번 - 차이를 최대로
N개의 정수가 주어진다. 정수의 순서를 바꿔서 아래 식의 최댓값을 구하라 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 이 문제는 오랜만에 자바로 알고리즘 과제를 하려고 하니 머리가 하얘져서 자바로 백준을 좀 풀어봐야겠다는…
11657번 - 타임머신
N개의 도시가 있다. 한 도시에서 출발해 다른 도시에 도착하는 버스 M개가 있다. 각 버스는 A,B,C로 나타낸다. A-시작도시, B-도착도시, C-걸리는 시간 C는 양수가 아닐 수 있다.
16234번 - 인구 이동
NxN크기의 땅 한칸마다 나라가 존재한다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라는 연합이 된다. 위의 조건에 해당하는 모든 나라가 연합이 되었다면 그 연합은 인구이동을 한다.
2096번 - 내려가기
n줄에 0이상 9이하의 숫자가 세개씩 적혀있다. 첫줄에서 가장 마지막줄까지 이동하면서 세가지 숫자 중 하나를 고른다. 마지막 줄에서 얻을 수 있는 최대 점수, 최소 점수를 구해라 이 문제는 dp로 풀 수 있겠다고 생각했다.
5525번 - IOIOI
n+1개의 I와 n개의 O로 이루어진 문자열이 있다. (IOIOI…) I,O로 이루언진 문자열 S가 주어졌을 때, S안에 위의 문자열이 몇번 포함되어 있는지 구해라 위 코드는 50점을 받았다.
N과 M(9) next_permutation풀이
순열을 구해주는 c++의 라이브러리 순열은 다들 아시니 넘어가겠습니다. next_permutaion이 어떻게 작동하는가? next_permuation은 두개의 인자를 받는데 첫번째 인자는 순열을 구할 배열의 시작 주소(iterator), 두번째 인자는 끝나는…
1987번 - 알파벳
보드의 각 칸에는 알파벳이 있음 주변의 네 칸 중 다른 칸으로 이동한다. 새로 이동한 칸은 지금까지 지나온 알파벳이 아니어야 함. 최대로 갈 수 있는 칸 수 구하기 이 문제는 간단하게 DFS로 풀 수 있겠다고 생각했다. 위 코드는 아쉽게도 바로 틀렸다고 한다. 이유가 무엇일까?
12865번 - 평범한 배낭
이 문제는 앞에서 블록 함께 쌓기를 풀면서 배웠던 배낭 문제 알고리즘을 사용하면 간단하게 풀 수 있는 문제였다.