시리즈

알고리즘

1.알고리즘 문제해결 전략 Chapter 08 - TRIPATHCNT (C++)

예제: 삼각형 위의 최대 경로 개수 세기 >문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. > >이...

2019년 11월 26일

2.알고리즘 문제해결 전략 Chapter 08 - ASYMTILING(C++)

예제: 비대칭 타일링 >문제 image.png 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 좌우 대칭이어서는 안 됩니다. 위 그림은 2 * 5 크기의 직사각형을 채우는 비대칭 타일링 방법 6가지를 보여줍니다. 다음의 2가지는 ...

2019년 12월 2일

3.알고리즘 문제해결 전략 Chapter 08 - POLY(C++)

예제: 폴리오미노 >문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다...

2019년 12월 3일

4.백준 13460번 - 구슬탈출2(C++)

문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. > >보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍...

2019년 12월 8일

5.알고리즘 문제해결 전략 Chapter 06 - BOGGLE(C++)

예제: 보글 게임 >문제 vue image 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다...

2019년 12월 18일

6.Leet Code - 26. Remove Duplicates from Sorted Array(C++)

예제: Remove Duplicates from Sorted Array >문제 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. > >Do not allocate extra space...

2019년 12월 18일

7.알고리즘 문제해결 전략 Chapter 06 - PICNIC(C++)

예제: 소풍 >문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. > >각 학생들의 쌍에 대해 이들...

2019년 12월 22일

8.알고리즘 문제해결 전략 Chapter 06 - BOARDCOVER(C++)

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

2019년 12월 23일

9.알고리즘 문제해결 전략 Chapter 06 - QUADTREE(C++)

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

2019년 12월 25일

10.알고리즘 문제해결 전략 Chapter 18 - JOSEPHUS(C++)

예제: 조세푸스 문제 >문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방...

2019년 12월 30일

11.알고리즘 문제해결 전략 Chapter 08 - JUMPGAME(C++)

예제: 외발 뛰기 >문제 vue image 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만...

2019년 12월 30일

12.알고리즘 문제해결 전략 Chapter 19 - BRACKETS2(C++)

예제: 짝이 맞지 않는 괄호 >문제 Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he r...

2019년 12월 30일

13.알고리즘 문제해결 전략 Chapter 08 - TRIANGLEPATH(C++)

예제: 삼각형 위의 최대 경로 >문제 > >위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾...

2019년 12월 30일

14.알고리즘 문제해결 전략 Chapter 20 - NAMING(C++)

예제: 접두사/접미사 >문제 아주대에 사는 외수는 작명에 능하기로 유명해서 많은 부부들이 아주대로 몰려와서 태어나는 아이들의 이름을 지어달라고 한다. 부부들은 이름은 잘 짓는게 출세에 영향을 미친다고 생각을 하고 있으며, 따라서 좋은 이름을 지어 출세하기를 기원한다. 허나 게으른 외수에게 작명은 지루한 작업이다. 효율적으로 일을 하고자 궁리하던 차에 쉽지...

2020년 1월 1일

15.알고리즘 문제해결 전략 Chapter 08 - LIS(C++)

예제: 최대 증가 부분 수열 >문제 >어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. > >어떤 부분 수열이 순...

2020년 1월 1일

16.Leet Code - 21. Merge Two Sorted Lists(C++)

예제: Merge Two Sorted Lists >문제 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. > >Example: > 풀이 포인터를 사용하...

2020년 1월 1일

17.알고리즘 문제해결 전략 Chapter 20 - PALINDROMIZE(C++)

예제: 팰린드롬 만들기 >문제 >앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “an...

2020년 1월 5일

18.알고리즘 문제해결 전략 Chapter 08 - JLIS(C++)

예제: 합친 LIS >문제 >어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. > >두 개...

2020년 1월 5일

19.Leet Code - 28. Implement strStr()(C++)

예제: Implement strStr() >문제 Implement strStr(). > >Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. > >Example 1: > >Example 2: > >Clarification...

2020년 1월 6일

20.알고리즘 문제해결 전략 Chapter 08 - PI(C++)

예제: 원주율 외우기 >문제 >(주의: 이 문제는 TopCoder 의 번역 문제입니다.) > >가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55...

2020년 1월 6일

21.알고리즘 문제해결 전략 Chapter 08 - TILING2(C++)

예제: 타일링 방법의 수 세기 >2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. > >예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다. (알고스팟 홈페이지에 그림이 없어서, 임의로 3개만 그렸다. 8개 그리기는 귀찮았다!!) > >image.png > >경우의 수는 n이 커...

2020년 1월 8일

22.알고리즘 문제해결 전략 Chapter 21 - TRAVERSAL(C++)

예제: 트리 순회 순서 변경 >트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 순서가 존재하지 않습니다. 때문에 필요에 맞춰 순서를 정의해야 합니다. 이진 트리(binary tree)는 모든 노드에 왼쪽과 오른쪽, 최대 두 개의 자손이 있는 트리를 말하는데,...

2020년 1월 8일

23.알고리즘 문제해결 전략 Chapter 08 - SNAIL(C++)

예제: 장마가 찾아왔다 >깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. > >여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확...

2020년 1월 9일

24.Leet Code - 38. Count and Say(C++)

예제: Count and Say >문제 The count-and-say sequence is the sequence of integers with the first five terms as following: > >1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read of...

2020년 1월 13일

25.알고리즘 문제해결 전략 Chapter 23 - RUNNINGMEDIAN(C++)

예제: 변화하는 중간값 >한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다. > >한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습...

2020년 1월 14일

26.Leet Code - 53. Maximum Subarray(C++)

예제: Maximum Subarray >문제 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. > >Example: > >Follow up: >`If you ha...

2020년 1월 14일

27.Leet Code - 58. Length of Last Word(C++)

예제: Length of Last Word >문제 Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop ...

2020년 1월 19일

28.Leet Code - 66. Plus One(C++)

예제: Plus One >문제 Share Given a non-empty array of digits representing a non-negative integer, plus one to the integer. > >The digits are stored such that the most significant digit is at the head of ...

2020년 1월 19일

29.Leet Code - 67. Add Binary(C++)

예제: Add Binary >문제 Given two binary strings, return their sum (also a binary string). > >The input strings are both non-empty and contains only characters 1 or 0. > >Example 1: > >Example 2: > 풀이 이진...

2020년 1월 20일

30.알고리즘 문제해결 전략 Chapter 09 - TICTACTOE(C++)

예제: 틱택토 >틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다. > 게임은 항상 x부터 시작합니다. > >틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두...

2020년 1월 21일

31.알고리즘 문제해결 전략 Chapter 28 - DICTIONARY(C++)

예제: 고대어 사전 >아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, ...

2020년 1월 25일

32.알고리즘 문제해결 전략 Chapter 09 - NUMBERGAME(C++)

예제: 숫자 게임 >n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다. > >- 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다. 게임판에 두 개 ...

2020년 1월 27일

33.Leet Code - 70. Climbing Stairs(C++)

예제: Climbing Stairs >문제 You are climbing a stair case. It takes n steps to reach to the top. > >Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? > >Not...

2020년 1월 27일

34.Leet Code - 100. Same Tree(C++)

예제: Same Tree >문제 Given two binary trees, write a function to check if they are the same or not. > >Two binary trees are considered the same if they are structurally identical and the nodes have the ...

2020년 1월 29일

35.알고리즘 문제해결 전략 Chapter 28 - WORDCHAIN(C++)

예제: 단어 제한 끝말잇기 >끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사...

2020년 2월 2일

36.Leet Code - 88. Merge Sorted Array(C++)

예제: Merge Sorted Array >문제 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. > >NOTE: >- The number of elements initialized in nums1 and nums2 are m and n r...

2020년 2월 2일

37.Leet Code - 101. Symmetric Tree(C++)

예제: Symmetric Tree >문제 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). > >For example, this binary tree [1,2,2,3,4,4,3] is symmetric: > >image.png >But ...

2020년 2월 2일

38.Leet Code - 112. Path Sum(C++)

예제: Path Sum >문제 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. > >Note: >A leaf is a node with n...

2020년 2월 3일

39.알고리즘 문제해결 전략 Chapter 10 - MATCHORDER(C++)

예제: 출전 순서 정하기 >전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다. 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다. 각 팀의 감독은 대회 전날, 주최측에 각 선수를 출전시킬 순서를 알려 주어야 합니다...

2020년 2월 4일

40.알고리즘 문제해결 전략 Chapter 10 - LUNCHBOX(C++)

예제: 도시락 데우기 >After suffering from the deficit in summer camp, Ainu7 decided to supply lunch boxes instead of eating outside for Algospot.com winter camp. > >He contacted the famous packed lunch compan...

2020년 2월 5일

41.알고리즘 문제해결 전략 Chapter 30 - ROUTING(C++)

예제: 신호 라우팅 >image.png >위 그림은 여러 개의 컴퓨터들과 각 컴퓨터들을 잇는 회선을 나타냅니다. 각 회선들은 각각 품질이 다르며, 각 회선을 지날 때마다 신호에 있던 노이즈가 증폭될 수 있습니다. 각 회선에 쓰여 있는 글자는 해당 회선을 지날 때 노이즈가 몇 배 증폭되는가를 보여줍니다. 특정 컴퓨터에서 다른 컴퓨터로 메시지를 보내고 싶습니다...

2020년 2월 9일

42.Leet Code - 107. Binary Tree Level Order Traversal II(C++)

예제: Binary Tree Level Order Traversal II >문제 Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). > >For e...

2020년 2월 9일

43.Leet Code - 108. Convert Sorted Array to Binary Search Tree(C++)

예제: Convert Sorted Array to Binary Search Tree >문제 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. > >For this problem, a height-balanced binary tre...

2020년 2월 9일

44.백준 15685번 - 드래곤 커브(C++)

문제드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.시작 점시작 방향세대0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하

2020년 2월 10일

45.Leet Code - 119. Pascal's Triangle II(C++)

문제Given a non-negative index k where k ≤ 33, return the k'th index row of the Pascal's triangle.Note that the row index starts from 0.In Pascal's tria

2020년 2월 11일