복습 정리 노트

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2075번 : 'K번째 큰 수', 9658번 : '돌 게임 4', 11004번 : 'K번째 수'의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당합니다. 2075번 : K번째 큰 수 N×N개의 수가 입력될 때 K번째로 큰 수를 출력하는 문제입니다. 문제의 난이도가 Gold 티어이므로 매번 정렬해서 K번째 수를 찾으면 시간 초과가 나도록 설계되어 있을 확률이 높습니다. 따라서 정렬을 사용하기보다는 우선순위 큐를 활용하여 값이 입력될 때마다 N번째 값을 top에 유지시키도록 하여 답을 구해보겠습니다. #include using namespace std; int main(..

이 포스트는 개발환경 이클립스(Eclipse)를 활용하여 웹 프로그래밍을 간단하게 수행해보고 프로젝트를 배포해서 사이트에 돌아가는지까지 확인해보는 과정을 다루고 있습니다. [웹 사이트 만들기] 웹 호스팅하기, 도메인(내 주소) 생성, 페이지 만들기 이 포스트에서는 웹 사이트를 만들고(페이지 생성 및 도메인 생성 과정), 기초적인 페이지를 만들어 문구를 출력해보는 작업까지 진행하는 방법을 다루고 있습니다. 이 포스트에서 중점을 두는 restudycafe.tistory.com ↑ 먼저 이전 포스트에서 웹 호스팅을 받아서 페이지를 간단하게 파보는 과정까지를 거쳐보았기 때문에, 해당 과정에 대한 지식이 전무하신 분들은 해당 포스트를 참고해주시기 바랍니다. 이제 코딩을 할 수 있도록 이클립스를 설치하는 방법을 안..

이 포스트에서는 웹 사이트를 만들고(페이지 생성 및 도메인 생성 과정), 기초적인 페이지를 만들어 문구를 출력해보는 작업까지 진행하는 방법을 다루고 있습니다. 이 포스트에서 중점을 두는 부분은, 기본부터 차근차근 공부한다기보다는 "일단 내 손으로 직접 해보기"입니다. 왜냐하면 실제로 저도 처음 언어를 배울 때 배우는 사람의 입장에서 이론만 배우는 과정이 마음에 들지 않았고, 먼저 해보는 과정이 중요하다고 생각했기 때문입니다. 따라서 사용자에 따라 원하는 호스팅의 종류나 만들고자 하는 것들이 다를 수 있지만, 일단은 제가 하는 과정을 따라해보고 어느 정도 감이 잡히면 배운 것을 응용하여 자신이 원하는 기능을 구현해보는 방법을 추천합니다. 카페24 호스팅/웹호스팅 - Tomcat JSP호스팅 스트리밍 무료제..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14853번 : '동전 던지기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Diamond II에 해당하며, 문제를 풀이하기 위해 조합론에 대한 배경 지식이 필요합니다. 14853번 : 동전 던지기 14853번: 동전 던지기 구사과는 p의 확률로 앞면이 나오고, 1-p의 확률로 뒷면이 나오는 동전을 만드는 기계를 만들었다. 여기서 p는 0과 1사이의 수이다. 하지만, 이 기계에 확률 p를 설정할 수는 없다. 확률 p는 기계가 www.acmicpc.net [0, 1]에서 균등한 확률을 가지는 p와 q가 각각 동전 1과 동전 2를 던졌을 때 앞면이 나오는 확률이라고 했을 때, 동전 1을 n1번 던..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2629번 : '양팔저울', 2293번 : '동전 1', 7579번 : '앱' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP, 동적 계획법의 활용에 대한 이해가 필요합니다. 2629번 : 양팔저울 주어진 질량의 추들을 가지고 구슬의 무게를 확인할 수 있는지를 구하는 문제입니다. 점화식을 구해주면 dp로 쉽게 해결이 가능하므로, 관계식을 찾아봅시다. 예를 들어 a라는 질량을 i-1개의 추들로 측정이 가능했다고 가정해봅시다. 그러면 새로운 b라는 질량의 i번째 추를 가지고 새롭게 측정 가능한 질량은 b, a+b, |a-b|의 3가지입니다. (..

​이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1520번 : '내리막 길', 10942번 : '팰린드롬?' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP(동적 계획법)의 활용에 대한 이해가 필요합니다. 1520번 : 내리막 길 숫자로 주어진 N×M의 map이 주어지고 (0, 0)에서 더 작은 수로만 이동하여 (N, M)까지 이동한다고 할 때, 몇 가지의 경로가 존재하는지를 찾는 문제입니다. 단순한 DFS로 해결이 가능해보이며, 여기에 DP를 활용하여 경로의 수를 기록하면서 풀이하면 되는 문제입니다. #include #define MAX 500 using namespace std; int..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11066번 : '파일 합치기', 11049번 : '행렬 곱셈 순서' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP(동적 계획법)의 활용에 대한 이해가 필요합니다. 11066번 : 파일 합치기 파일을 합칠 때 인접한 두 덩어리를 합치는 비용은 두 덩어리의 파일 크기의 합일 때, 모든 파일을 하나로 합치도록 하는 최소 비용을 구하는 문제입니다. 당연하겠지만 입력 값들의 크기는 무작위로 주어질 수 있기 때문에 DP를 활용하여 배열에 모든 경우의 수를 기록해나가면서 연산 시간을 감소시키는 방법이 가장 무난한 풀이입니다. 따라서 cost[a][b..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11286번 : '절댓값 힙', 1655번 : '가운데를 말해요' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 각각 Silver I, Gold II 티어에 해당하며, 문제를 풀이하기 위해 우선순위 큐에 대한 이해가 필요합니다. 11286번 : 절댓값 힙 입력된 N에 대해 N개의 입력값이 주어지고, 입력값 x가 0인 경우는 배열에서 절댓값이 가장 작은 값을 (절댓값이 작은 값이 여러 개인 경우 가장 작은 값을) 출력하고, 0이 아닌 경우는 그 값을 배열에 저장하는 쿼리를 수행하는 프로그램을 작성하는 문제입니다. 당연하겠지만 매번 정렬을 하고 원소를 탐색하면 시간 초과가 발생하도록 설계가 되어..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2110번 : '공유기 설치', 1300번 : 'K번째 수' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 이분 탐색(Binary Search) 알고리즘에 대한 이해가 필요합니다. 2110번 : 공유기 설치 N개의 집의 좌표가 주어졌을 때, C개의 공유기를 최대한 거리가 서로 멀리 떨어지도록 설치했을 때 공유기 사이의 거리를 구하는 문제입니다. 언뜻 보기에는 고려해야 할 변수가 많기 때문에 공유기 간 최대 거리를 바로 구하는 알고리즘을 찾기 쉽지 않습니다. 그렇기 때문에 이런 경우에는 공유기의 거리 자체를 아무거나 잡고 시작하여 범위 내에서 이..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 10816번 : '숫자 카드 2', 1654번 : '랜선 자르기', 2805번 : '나무 자르기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 문제를 풀이하기 위해 이분 탐색 알고리즘에 대한 이해가 필요합니다. (다만 일부 문제는 이분 탐색으로 분류되어 있음에도 더 쉽게 풀이할 수 있는 방법이 있다면 이분 탐색 알고리즘을 사용하지 않고 풀이한 것도 있습니다.) 10816번 : 숫자 카드 2 N개의 수가 주어지고 그 다음 M개의 수가 주어질 때 각각의 수가 몇 개 있었는지를 찾아서 출력하는 문제입니다. 정렬을 해준 뒤 그 수가 몇 개 있는지 찾아주면 되는데, N..