백준
백준 2655번 : 가장높은탑
https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net 아이디어가 어렵진 않아서 풀 순 있었지만 재귀로 구현하는데 시간이 오래 걸렸던 문제다. N개의 벽돌은 각각 높이와 서로 다른 넓이의 정사각형 밑면을 갖고 있고 무게도 모두 다르다. 이 벽돌들을 차례차례 쌓아올려서 가장 높은 탑을 만드려고 한다. 벽돌을 쌓기 위해서는 밑에 있는 블록보다 위에 있는 블록의 무게가 가벼워야하고, 밑면의 넓이도 작아야한다. 탑을 가장 높게 쌓아올렸을때 사용한 벽돌의 ..
백준 9251번 : LCS
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 접근 방법을 생각하지 못해 해답을 보고 푼 문제이다. 주어진 두 문자열의 부분 수열 중, 공통으로 들어있는 가장 긴 부분 수열의 길이를 구하는 문제다. 처음 떠오른 생각은 두 문자열의 부분 수열을 모두 구하고 비교하려고 했다. 문자열의 길이가 최대 1000이기 때문에 당연히 불가능하지만 이 방법밖에 머릿속에 떠오르지 않았다. 다이내믹 프로그래밍의 메모이..
백준 12865번 : 평범한 배낭
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 다이나믹 프로그래밍의 기본 유형이라고 할 수 있는 문제이지만, 2차원 리스트를 이용한 메모이제이션을 생각하는 과정과 사소한 실수로 푸는데 시간이 많이 소요됐다. 문제를 요약하면 N개의 물건은 각각 무게와 가치를 갖고 있는데, 주어진 배낭의 용량(K)을 넘지 않게 물건을 넣어서 배낭 안에 들어있는 물건들의 가치의 합을 최대로 만드는 ..
백준 1766번 : 문제집
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬의 개념을 알고, 이 문제에 적용할 수 있으면 쉽게 풀 수 있는 문제였다. 총 N개의 문제가 있고 문제는 1번부터 N번까지 난이도를 기준으로 오름차순 정렬돼있다. N개의 모든 문제를 풀되, 가장 쉬운 문제(번호가 낮은 문제)부터 풀어야 하지만 어떤 문제는 그 문제보다 선행되어 풀어야 하는 문제가 존재한다. 즉 선행 문제를 풀기 전엔 해당 문제를 풀 수 없다...
백준 4195번 : 친구 네트워크
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 처음 접해본 Union-Find 문제였다. 문제를 간단히 요악하면 두 사람의 이름이 입력으로 주어질 때 각 사람이 가진 친구들을 합한 수를 출력하는 문제이다. 예를 들어 A와 B가 입력으로 주어지면 그때부터 A와 B는 친구 관계를 맺게되고, A와 B가 친구가 되는 순간 A의 친구는 B의 친구가 되고, B의 친구는 A의 친구가 된다. 그 상태에서 A와 B가 가진 친구들의 수를 구해야 하는..
백준 1991번 : 트리 순회
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진 트리에서 전위, 중위, 후위순회를 코드로 구현하는 문제이다. 각 순회는 자식을 가진 특정 노드에서, 부모 노드가 방문되는 순서에 따른 분류이다. 전위 순회 : 부모 노드를 가장 먼저 방문하고 왼쪽 자식, 오른쪽 자식 순서대로 방문한다. (parent → left → right) 중위 순회 : 왼쪽 자식을 먼저 방문하고 부모 노드, 오른쪽 자식 순서대로 방문한다. (left → pa..
백준 1715번 : 카드 정렬하기
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net N개 만큼의 카드묶음이 있으며 이들 중 2개를 골라 1개의 카드묶음으로 만드는 작업을 수행할 수 있고 최종적으로 N개의 카드묶음을 1개의 카드묶음으로 만드려고 한다. 2개의 카드묶음을 합칠 때에는 각 카드묶음에 있는 카드 수를 합한 만큼 비교를 수행하는데, 비교 횟수를 최소화하려고 한다. 이때 최소화된 비교 횟수를 구하는 문제이다. 전형적인 그리디 알고리즘 유형이다. N개의 카드묶음..
백준 OJ 시스템 언어별 정보
원문 링크 https://help.acmicpc.net/language/info 언어 정보 section .data input: db "%d %d",0 output: db "%d",10,0 a: times 4 db 0 b: times 4 db 0 section .text global main extern scanf extern printf main: push rbp mov rdi, input lea rsi, [a] lea rdx, [b] mov rax, 0 call scanf mov rax, [a] mov rbx, [b] add rax, rbx help.acmicpc.net Python 3 언어 번호: 28 컴파일: python3 -c "import py_compile; py_compile.compile..
백준 22871번 : 징검다리(large)
https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색 카테고리 문제를 풀다가 접하게 된 문제다. 연산시간 때문에 하루종일 이 문제만 붙잡고 고민했다. 최적화 하려는 변수가 M이라면 보통 이분탐색 문제는 O(log M) 시간안에 해결이 가능하거나 그 보다 오래 걸리더라도 주어진 시간 안에 해결이 가능했다. 관련하여 문제를 풀면서 고민한 것들을 글에 풀어서 써보겠다. N개의 징검다리..
백준 3079번 : 입국심사
https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 2110번에서 알게된 내용들을 적용해서 생각보다 쉽게 푼 문제다. M명의 사람들은 입국하기위해 입국심사를 받는다. 심사대는 총 N개가 있고 심사대마다 심사에 소요되는 시간이 정해져있다. M명의 사람들을 모두 통과시키는 최소한의 시간을 구하는 문제이다. 앞서 푼 문제에서 배운 이분 탐색의 요령을 그대로 적용했다. 구하려는 값은 시간이기 때문에 가능한 범위 안에서 조건(시간 안에 사람들..