알고리즘 공부

최근에 함께자라기를 읽고나서 느끼는 바가 있어 알고리즘 공부 방법을 조금 변경해보려고 한다. 그동안에 반복 숙달하면 자연스럽게 잘하게 되리라는 막연한 생각으로 하루에 한 문제씩 푸는 식으로 공부를 해왔는데 문제를 많이 접할 수는 있겠으나 딱히 문제해결 능력이 나아지고

개념 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 다양한 문제를 접해보고 풀어보는 것이 좋다. 문제를 해결하기 위한 점화식을 찾아낸 후 점화식을 차례로 구해나가면서 답을 알아내는 형태의 알고리즘 DP 푸는 과정 테이블 정의

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수의 개수를

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.먼저, 공연이 시작하기 전에 각각의 곡이 시작하기

무한 수열 A는 다음과 같다.A0 = 1Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.점화식이 이미 주어져 있는 골드5치고는 쉬운 문제다.그래서 만만하게 보고 for문을 돌면서 dp값을 채우는 로직을

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.참가자 여러분도 궁금하지요?안 궁금함? 15ㄱ테이블 정의dpi = i번째 자리의 1 or 5로 구성된 15의 배수의 갯

한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조먼저 들어간 요소가 나중에 나오는 구조FILO원소추가가 O(1)원소제거가 O(1)제일 상단의 원소 확인이 O(1)제일 상단이 아닌 나머지 원소들의 확인/변경이 ‘원칙적’으로 불가능스택문제를 보면 원소의 추가, 제거, 상

도시에는 N개의 빌딩이 있다.빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1,

ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스

지금 가장 최적인 답을 근시안적으로 택하는 알고리즘관찰을 통해 탐색의 범위를 줄이는 알고리즘관찰을 통해 탐색범위를 줄이는 방법을 고안한다.탐색범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.구현해서 문제를 통과한다.관찰을 통해 탐색범위를 줄이는 방법을 고

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1 2 3 42 3 4 53 4

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘1부터 N까지의 합을 구하는 함수를 한 번 짜보자!어떤 문제를 재귀로 풀겠다는 것은 귀납적 방식으로 해결하겠다는 의미이다. 귀납적 방식은 우리가 일반적으로 알고 있는 상식과 큰 차이가 있다.도미노가 1 >

평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.중앙대학교와 자신의 길이 맞지 않다고 생

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종

아래의 문제들을 접하고 풀어보았다. 강의 전체적으로 문제에 대한 설명과 괄호쌍 문제를 어떻게 풀면 좋은지 설명만 있어서 딱히 정리할 건 없었다. boj - 2504 더 코드를 간결하고 깔끔하게 짤 수도 있을 거 같은데 스택의 구조를 파악하는게 우선이라고 생각해서 돌아

문제 풀이 분할정복, 재귀문제다. 현재의 row, col 그리고 n값을 받아와 row부터 row + n , col부터 col+n 까지의 movies 값 전체가 하나로 일치하는지 검사하고 일치한다면 그 값을 반환해주고 아니라면 순서대로 2사분면 , 1사분면, 3사분면,

주어진 정사각형을 4분할 하려면 초기값 r, c에서 아래와 같이 n//2를 더해가면 그림에서 주어진 순서대로 시작인덱스를 구할 수 있다.1\. r, c2\. r, c + n//23\. r +n//2, c4\. r+n//2, c+n//2구한 시작인덱스를 토대로 길이값 n

문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘선택지가 주어지는 게임을 예로 들면 선택지 별로 결과가 달라진다고 하면 돌아가서 두번째, 세번째 선택지를 다시 선택해볼 것이다. 이런식으로 모든 경우를 다 훑어보게 된다.상당한 구현력을 필요로하고 실수하

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.전설카드레

이 문제는 주어진 입력의 갯수도 8개로 상당히 작고 cctv를 돌려서 얻을 수 있는 가능한 모든 상황을 고려해야하는 문제이므로 백트래킹으로 풀 수 있다.cctv를 어떻게 효율적으로 잘 돌릴 것인가, 재귀함수의 로직을 어떻게 짤 것인가 이 두가지만 잘 고려하면 풀 수 있

알고리즘 자체에서 크게 설명할 건 없고 문제를 해결하는 예시를 몇개 보면 쓰임새를 파악하기 좋다.투포인터는 배열에서 원래 이중 for문으로 O(N\*\*2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이분탐색 문제를 투포인터 문제로 해결할 수

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘시작하는 칸을 큐에 넣고 방문했다는 표시를 남김큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행해당 칸을 이전에 방문했다면 아무것도 하지 않고 처음으로 방문했다면 방문했다는 표시를

키에 대응대는 값을 저장하는 자료구조이다. 다른 자료구조들을 보면 특정 연산은 빠른 반면 특정 연산은 느린 상황이 나오게 마련인데 해시는 모든게 O(1)이다.해시자료구조에서는 해시함수라는 것이 쓰인다. 해시함수는 마치 카드번호 16자리에서 뒷 4자리만 배열의 인덱스로

문제 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로

혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터

연습문제boj-11728이 코드는 머지소트의 조각코드라고 볼 수 있다. 이제 재귀를 통해서 머지소트를 구현해보자.38, 21, 21, 21 이라는 나이가 담긴 배열이 있다고 했을 때 정렬을 하면 21 21 21 38로 21에 해당하는 수들은 어디에 위치해도 정렬되어 있

각 숫자가 나온 횟수를 저장하고 그 횟수만큼 배열에 넣어주면 된다.간단하다는 장점이 있지만 메모리 제한이 512mb라고 해도 int기준으로 1.2억인 배열밖에 잡을 수 없기 때문에 이렇게 크기가 큰 배열에는 카운팅 소트를 써먹을 수가 없다. 수의 범위가 어느정도 한정적

각 노드의 자식이 2개 이하인 트리를 이진 트리라고 한다.왼쪽 서브 트리의 모든 값은 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진트리를 이진 검색트리라고 한다.이진검색트리를 활용하면 insert, erase, find, update를 모두 O

이번에 일요일 문제를 풀어보니 내가 진짜 그래프나 도형문제에서 엄청 약하고 겁을 먹는다는 사실을 알게됐다. 도형 문제도 많이 풀어봐야겠다.boj-6502그림을 그려보니 원안에 4각형이 들어오려면 사각형을 관통하는 대각선의 길이가 원의 지름보다 작으면 피자를 식탁위에 놓

그래프란 정점과 간선으로 이루어진 자료구조각 정점에 대해 간선으로 연결된 이웃한 정점의 개수가 차수이다.그래프는 네비게이션에서 최단경로 찾기 혹은 구글같은 검색엔진에서 랭킹 정하기와 같이 원소 사이의 연결관계를 설정해야하는 상황에서 유용하게 활용될 수 있는 자료구조그래

그래프를 배운 후 트리를 다시 보면 간선과 정점으로 이루어진 자료구조로 그래프의 특별한 한 종류임을 알 수 있다.기억해두면 좋은 정의는 아래와 같다.트리는 무방향이면서 사이클이 없는 연결 그래프이다.임의의 두 점을 연결하는 simple path(정점이 중복해서 나오지

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어

실생활에서 가장 찾기 쉬운 예시는 교과 이수 제도이다. 대학교에는 선수과목이 있는 과목들이 있다. 예를들어 프로그래밍1을 들어야 프로그래밍2를 들을 수 있는 것처럼.만약 이런 선수과목이 있는 여러 과목들이 주어졌을 때 모든 과목을 수강하고 싶다면 어떤 순서로 과목을 들

문제 다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다. 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세

신장트리란 주어진 방향성이 없는 그래프틔 부분 그래프들 중에서 모든 정점을 포함하는 트리를 의미한다.최소신장트리란 신장트리 중에서 간선의 합이 최소인 트리를 말한다.간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택현재 선택한 간선이 정점 u, v를 연결

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음,

모든 정점 쌍 사이의 최단거리를 구하는 알고리즘아래와 같은 테이블처럼 모든 정점 쌍 사이의 최단거리를 구해주는 알고리즘이다.무방향 그래프, 방향 그래프에 상관없이 사용할 수 있는 알고리즘이다. 간선값이 음수여도 알고리즘은 잘 동작하지만 음수인 사이클이 있으면 문제가 생

상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고

하나의 시작점으로 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘(음수 간선이 있다면사용할 수 없다.)플로이드 알고리즘을 떠올려보면 모든 정점 쌍 사이의 최단거리를 구하는 알고리즘이고 음수 간선에도 사용할 수 있기 때문에 기능을 플로이드가 더 좋다

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한

아래와 같이 A안에 B가 있는지 확인하는 알고리즘이다.A = o, r, o, n, d, o, n, t, i, s, sB = n, t, ikmp를 모르는 이 상태에서 B가 A안에 있음을 어떻게 확인할 수 있을까? A를 순회하면서 B와 매칭되는지 검사하면 찾을 수 있다.이

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비

친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로

gif via giphy트라이 - 바킹독 유튜브BFS 연습문제 boj-10026오늘 집중이 안되도 차분하게 명상하고 다시 집중하려고 노력한 나를 칭찬해주고 싶다.✻ 바킹독님 조언우선 연습문제를 충실히 푼다. (답지 없이)solved.ac 설정을 끄고 실버3 ~ 골드3

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.지훈이와 불은 매 분마다 한칸씩 수평또는 수직

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?BFS를 단순하게 4방향으로 돌리는게 아니라 나이트의 이동방향을 설정 해

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 <그

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열고른 수열은 오름차순이어야 한다.백트래킹으로 구하는 조합의 오름차순을 구하기

https://www.acmicpc.net/problem/15664https://www.acmicpc.net/problem/15665https://www.acmicpc.net/problem/15666N과 M 시리즈 문제는 백트래킹 코드를 손에

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서

문자열을 효율적으로 처리하기 위한 트리 자료구조시간 - 단어S를 삽입/탐색/삭제할 때 O(len(S))공간 - 문자열을 그냥 배열에 저장하는 것 보다 최대 4X글자의 종류 배 만큼 더 사용한다.(메모리 사용량에서 병목이 될 수 있음)이론적으로 생각할 때 이진검색트리는

뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진

문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형

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