ProblemSolving

1\. 문제 파악 ‘Skeletons’ 문제 해결에 있어서 가장 중요한 부분은 문제 상황이 무엇인지 이해하는 과정이다. 영문으로 작성된 문제이고, 문제의 설명부에 미사여구가 많이 포함되어 있기 때문이다.복수의 마을이 존재하고, 각 마을은 단-방향의 길로 연결될 수 있다

  IEEE 754 표준을 사용해 실수를 취급하는 C++에서는 IEEE 754의 부동소수점 표기법과 이진수의 특성에 의해 실수 비교 시 위와 같은 코드의 사용이 필요하다.  일반적으로 32비트 크기 실수 자료형은 정확도가 높지 않으므로, 3D 모델링과 같이 상대적으로

  PS 공부의 바이블 중 하나인 '알고리즘 문제 해결 전략 세트'에서는 아래와 같은 'PS 시 하기 쉬운 실수들'에 대해 정리해놓았다. 이는 분명 앞으로 PS 뿐만 아니라 모든 유형의 코딩을 함에 있어서 충분히 도움이 될만한 사항이라 판단해 Velog에 한 번 더 정

  PS나 현업에서 특정한 문제를 해결할 때, 주어진 시간 제한을 엄격히 지키는 것이 중요하다. 학부 알고리즘 수업에서 다양한 시간 복잡도 관련 이론과 분석 방법에 대해 배웠지만, 사실 이를 실제 문제에 정확하게 적용하기란 쉽지 않다. 이때, (특히나 PS 문제 해결에

  학부 알고리즘 수업에서 Problem의 분류에 대해서 자세히 배운 바 있다. 해당 수업에서는 NP-Easy, Reduction과 관련된 각 종 Theorem과 그 proofs들에 대해서도 자세히 다루었지만, 본인의 앞으로의 커리어에 있어서 P와 NP에 대한 명확한

  학부 알고리즘 수업 때 학기말 공부의 주된 내용은 Greedy Algorithm에서의 Proof of Optimality와 Dynamic Programming에서의 Principle of Optimality였다. 이를 국문으로 옮기면, 전자는 '정당성 증명'이라고

  '알고리즘 문제 해결 전략 세트'의 Brute-Force 소개란에서 제시하고 있는 아래의 소스 코드는 재귀호출을 이용해 'n개의 원소 중 m개를 택하는 모든 조합을 출력하는' recursive한 알고리즘을 보여주고 있다.  매우 손쉬운 코드이고, 익숙한 코드이지만,

1\. 문제 내용  안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에,

문제   H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나

문제  대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과

문제  너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a

문제  가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니

문제  와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, \* 나 ? 와 같은 특수 문자를 포함한다.  와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때

문제  세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

문제  666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈

문제  N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.입력  첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.출력  첫째 줄

문제  수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.산술평균 : N개의 수들의 합을 N으로 나눈 값중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그

문제  수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과

문제  N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력  첫째 줄에 N이 주어진다. (1 ≤ N < 15)출력  첫째 줄에 퀸 N개를

문제  N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.  우리는 수와 수 사이에 연산자를 하나씩 넣

문제 링크 : 백준 2580번 - 스도쿠  본 문제는 기초적인 Backtracking(Backtracing) 문제이다. DFS적인 흐름의 탐색 함수를 구성해, 정답이 발견되는 경우, 그 순간 함수의 동작을 멈추고 정답을 출력하면 된다.  본인은 본 문제의 알고리즘을 일

문제 링크 : 백준 2579번 - 계단 오르기  본 문제는 아주 기초적인 DP 문제이다. 기초 문제임에도 포스팅을 하는 이유는, 본인이 4번 제출해서 3번을 틀렸기 때문이다(부끄럽다..)  본 문제의 핵심은 다음과 같다.계단 i의 점수와, i를 포함한 i까지의 누적 스

백준 2565번 - 전깃줄

문제 링크백준 9251번 - LCS  백준 9251번 LCS 문제는 Dynamic Programming적 시선을 키우기 아주 좋은 문제 중 하나이다. 과거 학부 알고리즘 수업에서 다룬 바 있는 Edit Distance 문제와 아주 유사한 접근 방식을 취하고 있다. DP

문제 링크백준 12865번 - 평범한 배낭  학부 알고리즘 수업에서 0/1 Knapsack Problem에 대해 그렇게 자주 다루었음에도 불구하고 첫 번째 시도에서는 풀이에 실패하였다. 가장 큰 이유는, Dynamic Programming에 쓰이는 배열을 1차원으로 구

문제 링크 백준 1931번 - 회의실 배정 해결 전략   문제의 설명을 읽어보면 본 문제는 Dynamic Programming이나 Greedy Algorithm으로 다룰 수 있겠다는 느낌이 바로 든다. 그리고 좀 더 세세하게 문제 상황을 관찰해보면 어렵지 않게 Greedy Algorithm으로 해결할 수 있겠다는 감이 온다.   사실,...

문제 링크 백준 13305번 - 주유소 해결 전략   알고리즘 문제를 풀 때는 "최대한 복잡하지 않게 생각해보기"가 매우 중요하다. 아무리 어려운(예를 들어 백준에서 다이아몬드 티어) 문제라도 그 아이디어를 떠올리는 것은 어려울지 몰라도 아이디어의 구현 과정

문제 링크백준 11051번 - 이항 계수 2  대부분의 대학교 학부 컴퓨터공학과 1학년 과정에서는 이산 수학, 이산 구조, Discrete Structure에 대해 학습한다. 본인 역시 해당 과목 수강 과정에서 매우매우 자주 사용하였던 공식이 하나 있는데, 그 공식이

문제 링크백준 10828번 - 스택  사실, 이 문제는 정말 쉬운 문제이고, 사실상 취업 시의 코딩 테스트엔 이런 수준의 문제는 출제되지 않을 가능성이 높다. 그럼에도 불구하고 본인이 이 문제를 포스팅하는 것은, 초심자 프로그래머들에게, 본인 역시 아직 고수는 결코 아

문제 링크백준 4949번 - 균형잡힌 세상  본 문제를 풀다가 막힌 사람의 90% 이상은 아마 문자열 입력 때문이었을 것이다. 사실 문제 해결을 위한 Algorithm은 어렵지 않게 떠올릴 수 있다. Stack을 사용해야한다는 것을 말이다. 스택의 'Top에서만 삽입/

문제 링크백준 18258번 - 큐 2  본 문제는 며칠 전 포스팅했던 BOJ - 10828 스택 해결 전략 (C++) 게시글과 같은 유형의 문제이다.  그 때와 마찬가지로, 물론 vector stl이나 list stl을 이용해서 간단히 해결할 수 있겠지만, 그러한 자료

문제 링크백준 1966번 - 프린터 큐  본 문제는 쉬운 문제이다. 다만, 구현 측면에서 중요한 스킬이 있어 포스팅하기로 했다. 우선, 문제를 해결하는 알고리즘적 측면에서는, 직관적으로 해결하면 된다. 선형 자료구조의 맨 앞 요소보다 우선순위가 높은 요소가 있으면 맨

문제 링크백준 1021번 - 회전하는 큐  본 포스팅은 반성문(?)과 같은 포스팅이다. 문제 자체는 맞추긴 했는데, deque stl 대신 list stl을 사용해서 괜시리 더 복잡한 프로그래밍을 자초했다는 것을 잊지말자는 취지이다.  list stl은 인덱싱이 안된다

문제 링크백준 5430번 - AC  본 문제의 해결 아이디어를 떠올리는 것은 사실 그다지 어렵지 않다. 오히려 이 문제는 알고리즘적 사고가 중요하다기보다는 구현 스킬과 입출력 방식들의 속도 차이 이해가 더 중요한 문제이다.  우선, 문제 해결 알고리즘은 간단하다. 함수

문제 링크백준 1629번 - 곱셈  본 문제는 "똑같은 결과를 내는 중복되는 재귀호출은 값을 기억하는 방식으로 처리하는 것이 바람직하다."라는 교훈을 얻을 수 있는 문제이다.  그 이유를 설명하기에 앞서, 본인은 최초 시도에서 이 문제를 해결하지 못했는데, 그 이유는

문제 링크백준 11401번 - 이항 계수 3  본 문제는 상당히 난이도가 있는 문제로, 학부 이산 수학에서 배우는 개념들을 여럿 기억하고 있어야 해결할 수 있는 문제이다. 만약 인터넷 서칭이 불가능한 코딩 테스트에서 이러한 문제를 맞딱뜨린다면 해결이 쉽지 않을 수 있다

문제 링크백준 10830번 - 행렬 제곱  이 문제는 행렬의 성질을 알고 있으면 그닥 어렵지 않게 풀 수 있다. 우선, 입력이 최대 1천억까지 가능하므로, 본능적으로 이 문제는 Divide & Conquer 문제임을 알 수 있다. 행렬의 제곱을 분할 정복하기 위한 기반

문제 링크백준 11444번 - 피보나치 수 6  문제의 n 입력이 1,000,000,000,000,000,000까지 가능하다. 이는 long long에만 들어갈 수 있는 정수이므로, long long으로 변수를 다뤄야 한다.  피보나치 수를 다루는 전통적인 방법들을 떠

문제 링크백준 6549번 - 히스토그램에서 가장 큰 직사각형  정말 아쉽다. 정답에 거의 다 와놓고선, 결국 디테일한 부분을 캐치하지 못해서 서너시간을 해결하지 못한채 전전긍긍했다ㅠㅠ 문제 해결의 퍼센티지를 매기면 초반 10~20분만에 90%를 해놓고서 나머지 10%를

문제 링크백준 10816번 - 숫자 카드 2  문제를 처음 딱 보면, 입력받은 수들을 배열로 저장하고, 배열을 Nondecreasing Order로 정렬한 다음, Binary Search(또는 Quick or Merge Sort)로 각 Target을 찾되, 찾은 요소를

문제 링크백준 1654번 - 랜선 자르기  본 문제를 처음 봤을 때 본인이 떠올린 '가장 직관적인 Idea'는 다음과 같았다.1) 입력받는 랜선들의 길이를 leni라고 배열 처리를 할 시, 그중에서 최소값 min_L을 기억해놓는다.2) 그 최소값부터 1까지 min_L값

문제 링크백준 14425번 - 문자열 집합  본 문제를 보자마자 우리는 Search의 대상과 Search의 주체가 모두 10,000개이기 때문에, 문자열 비교까지 고려하면 시간 제한 내에 Naive한 방식으로는 해결할 수 없음을 어렵지 않게 알 수 있다.  이럴 때는,

문제 링크백준 2477번 - 참외밭  본인은 이 문제를 처음 보았을 때, 매우 쉬운 문제일 것이라 생각하고 접근했다가 두 번이나 틀리는 낭패를 보았다. 사실 쉬운 문제는 맞다. 허나, 가볍게 생각해선 답안을 도출하기 어려운 문제이기도 하다.  처음엔, 입력에서 동서/남

문제 링크백준 1004번 - 어린 왕자  문제를 읽다 보면, 문제의 조건(ex. 경계가 맞닿거나 ~)이 아래와 같은 아이디어를 유도하고 있음을 금새 알아챌 수 있다.출발지와 도착지를 포함하지 않는 원들은 모두 삭제해도 상관 없다.즉, 각 행성과 출발지/도착지 간의 거리

문제 링크백준 11659번 - 구간 합 구하기4  본인의 PS 실력이 여전히 많이 부족함을 느낀다. CS 이론이나, 시간을 오래 투자해야하는 깊이 있는 학부 프로젝트에는 참 잘한다고 느끼는데, PS에 있어서는 늘 자신감이 떨어진다. 극복하자.  이런 얘기를 하는 이유는

문제 링크백준 10986번 - 나머지 합  본 문제는 컴퓨터공학과 학부 과정에서 '이산 수학'을 배운 이라면 반드시 한 번 이상은 들어봤을 '모듈러 연산 관련 공식'을 사용하면 해결할 수 있는 문제이다. 본인은 최초 풀이 시도에서 해당 공식을 떠올리지 못해 해결하지 못

문제 링크백준 2110번 - 공유기 설치  본 문제는 전형적인 Binary Search 응용 문제로, 이분 탐색을 요구하는 상황임을 인식하는 것은 어렵지 않다. 다만, 그 구현에 있어서 약간의 센스가 필요한 문제이다. 가장 핵심적인 Tip은 아래와 같은 사실을 인지하는

문제 링크백준 1300번 - k번째 수  본 문제는 꽤나 까다로운 문제이다. 문제의 해결 Idea를 찾기만 한다면 어렵지 않게 해결할 수 있지만, 그 Idea를 찾는 과정에 '함정으로 빠지기 쉬운 유혹'이 많기 때문이다.  문제를 읽어보고, 몇 가지 예제를 분석하다보면

문제 링크백준 12015번 - 가장 긴 증가하는 부분 수열 2  본 문제는 BOJ에서 상당히 유명한 문제 유형인 LIS(Longest Increasing Sequence)의 두 번째 문제이다. 기본 LIS 문제들은 두 가지 타입으로 풀이법이 나뉜다. 문제 조건에 의해

문제 링크백준 1655번 - 가운데를 말해요  본 문제는 해결 Idea를 찾는 것이 꽤나 Tricky하다. 문제를 처음 보자마자 떠오르는 가장 Naive한 풀이법은 다음과 같을 것이다.매 입력마다 정렬해서 중간값을 찾을까?  허나, 이는 N이 100,000임을 고려했을