스타트와 링크
문제: 스타트와 링크 (백준 14889번) 구조 분석 해당 문제의 경우 처음에 배열 또는 벡터로 문제를 풀어야 하는지 고민했다. 백터로 능력치를 저장하고 이를 sort하고 다시 나누는 것은 그러나 항상 optimal한 값을 출력할 것 같지 않았다. 그래서 고민하다가 힌트를 ...
Tag
- c/c++ 27
- map 10
- dfs 9
- bfs 7
- intro 6
- LLVM 6
- dynamic-programming 5
- github 4
- math 4
- greedy 4
- string 4
- back-tracking 4
- setting 3
- vector 3
- sort 3
- brute-force 3
- brute-froce 3
- priority_queue 3
- heap 3
- md 2
- git 2
- graph 2
- geometry 2
- tree 2
- queue 2
- jekyll 1
- c/c+ 1
- LCS 1
- priority-queue 1
- deque 1
c/c++
연산자 끼워넣기
문제: 연산자 끼워넣기 (백준 14888번) 구조 분석 해당 문제는 수학 문제처럼 보일 수 있으나 조건을 잘 살펴보면 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.라는 말이 있다. 즉, 이는 backtracking문제이며 이는 dfs를 이용해서 쉽게 풀 수 있다. ...
로봇 청소기
문제: 로봇 청소기 (백준 14503번) 구조 분석 해당 문제는 로봇 청소기의 움직임을 구현하는 문제로 후진을 하는 움직임을 back tracking으로 구현해야 하는 dfs문제이다. 이런 구조의 문제는 dfs를 재귀함수로 구현하는 것이 더 쉽고 간단하다. 풀이 방법 우선 ...
테트로미노
문제: 테트로미노 구조 분석 해당 문제는 지금까지 열심히 풀었던 전형적인 보드판 위의 구현문제이다. 이는 brute force를 이용해 매 칸을 탐색하며 해당 칸을 시점으로 하는 테트리스 블록의 점수 중 최대값을 구하는 문제로 4칸짜리 테트리스 블록을 구현하기 위해 dfs를 ...
퇴사
문제: 퇴사 (백준 14501) 구조 분석 최근에 계속 시뮬레이션/구현 문제만 풀다가 간단한 형태의 문제를 봐서 신났다. 그런데 처음에 문제를 봤을 때 어? 스케줄링? 그러면 전형적인 greedy 문제구나! 해서 풀었다가 막혀서 당황했다. 해당 문제는 최대한 많은 스케줄을 잡...
시험 감독
문제: 시험 감독 (백준 13458번) 풀이 방법 해당 문제는 매우 간단한 수학 및 사칙연산 문제이므로 구조분석할 필요없이 바로 풀면 된다. 우선 vector를 이용하여 각 고사실 별 인원을 입력받고 주감독관 1명을 배치 후 부감독관을 나누기와 modulo 연산을 통해서 배치...
뱀
문제: 뱀 (백준 3190번) 구조 분석 해당 문제는 단순 구현 문제이다. 보드에 사과의 위치를 입력 받고 뱀을 움직이며 조건에 따라 게임을 중단하는 간단한 형태의 문제이나 구현하는데 있어서 생각할 조건이 많고 까다로워 풀이를 할 때 헷갈리지 않게 잘 해야 한다. 풀이 방법...
2048 (Easy)
문제: 2048 Easy (백준 12100번) 구조 분석 처음 이 문제를 보고 드는 생각은 bfs 또는 dfs를 이용할 수 있겠다는 것이었다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록의 수를 출력하는 문제였기 때문에 dfs를 이용해야겠다고 생각했다. 그런데 dfs의...
구슬 탈출 2
문제: 구슬 탈출 2 (백준 13460번) 구조 분석 해당 문제를 처음 봤을 때 매우 당황스러웠다. 겉보기에는 이전에 풀어봤던 연구소 (백준 14502번) 문제와 매우 유사했다. 이전에 풀었던 연구소 문제는 map이 주어지고 바이러스가 퍼져나가는 조건이어서 보자마자 bfs를 ...
최소 힙
문제: 최소 힙 (백준 1927번) 구조 분석 최대 힙 문제와 마찬가지로 stl의 priority queue를 이용하여 힙을 구현하는 문제이다. 풀이 방법 최대 힙: 내림차순 정렬 최소 힙: 오름차순 정렬 Priority queue에는 오름차순과 내림차순같은 정렬 기...
최대 힙
문제: 최대 힙 (백준 11279번) 구조 분석 해당 문제는 heap이라는 자료구조를 구현하는 문제이다. 이는 기본적인 자료구조로 c++의 stl에서 제공하는 priority_queue를 이용하면 매우 쉽게 풀 수 있다. 풀이 방법 내림차순 정렬을 위해서는 max heap을...
절댓값 힙
문제: 절댓값 힙 (백준 11286번) 구조 분석 해당 문제 역시 priority queue를 이용하여 heap을 구현하는 문제이다. 다만 이전의 오름차순이나 내림차순 이외의 조건이 붙어서 해당 조건을 위한 비교연산자를 생성해줘야 한다. 풀이 방법 비교 연산자를 활용하여 p...
트리의 부모 찾기
문제: 트리의 부모 찾기 (백준 11725번) 구조 분석 해당 문제를 처음 접하고 매우 당황했다. 지금까지는 트리문제는 트리구조를 만들고 이를 순회하며 탐색하는 경우만 접했기 때문에 루트노드와 자식노드가 정해져있지 않은 트리를 어떻게 만들어야 할 지 감이 안왔기 때문이다. 우...
트리 순회
문제: 트리 순회 (백준 1991번) 구조 분석 해당 문제는 전형적인 tree문제이다. 이는 tree 순회문제로 자료구조의 기본이 되는 내용이다. 트리를 순회하는 방법은 다음과 같다. pre order: (root) (left) (right) 순서로 순회 in order: (...
어린 왕자
문제: 어린 왕자 (백준 1004번) 풀이 방법 이는 이전의 터렛 문제와 매우 흡사하다. 다만 터렛 문제에서는 두 원 사이의 모든 관계를 다뤘다면 해당 문제에서는 원과 점 사이의 관계를 다루는 문제이다. 점이 원 안에 있는 경우 행성계 진입/이탈이 일어나게 되므로 아래의 경...
터렛
문제: 터렛 (백준 1002번) 풀이 방법 Geometry 문제는 좌표평면을 떠올리며 풀어야 한다. 특지 중학교 고등학교 과정의 방정식 및 판정식을 기억하고 있으면 풀이에 도움이 된다. 해당 문제의 경우 두 원의 중점과 반지름이 주어진 상황에서 두 원의 교점의 개수를 구하는 ...
토마토
문제: 토마토 (백준 7576번) 구조 분석 이는 전형적인 BFS 문제이다. 익은 토마토부터 가까운 토마토를 방문하며 expand 시키며 모든 토마토가 익을 때까지 걸리는 날짜를 세면 된다. 풀이 방법 BFS로 문제를 풀면 된다. 특이하게 어려운 점은 없다. 코드 ```c...
미로 탐색
문졔: 미로 탐색 (백준 2178번) 구조 분석 도착지까지의 최소 칸 수를 세는 문제이므로 전형적인 BFS 문제이다. 해당 좌표와 탐색 depth를 저장하기 위해서 pair<pair<int,int>,int>형태로 노드를 저장해야 한다. 풀이 방법 BFS...
DFS와 BFS
문제: DFS와 BFS (백준 1260번) 구조 분석 정점의 개수와 간선의 개수를 입력받고 간선 정보를 입력한 뒤 해당 graph에 대해 DFS와 BFS를 실시하는 문제이다. 풀이 방법 DFS는 stack을 사용한다. 이때 주의할 점은 방문한 노드를 재방문 하지 않도록 설정해...
안전 영역
문제: 안전 영역 (백준 2468번) 구조 분석 해당 문제는 연구소(백준 14502번)문제와 매우 유사한 문제이다. 이는 해당 문제와 동일하게 두 가지 큰 알고리즘이 합쳐진 문제이다. 물이 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽,...
연구소
문제: 연구소 (백준 14502번) 구조 분석 해당 문제는 두 가지 큰 알고리즘이 합쳐진 문제이다. 문제의 제시문을 보고 아래의 알고리즘 유추를 할 수 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 이는 전형적인 BFS 문제이...
체스판 다시 칠하기
문제: 체스판 다시 칠하기 (백준 1018번) 구조 분석 처음 문제를 봤을 때, 이를 수학적으로만 풀려고 해서 어려웠다. 그러나 이러한 문제는 convolution 계산하듯이 8*8의 체스보드 프레임을 입력받은 이차원배열 위로 움직이면서 해당 8*8 보드 프레임 위에서의 다시...
단어 수학
문제: 단어 수학 (백준 1339번) 구조 분석 해당 문제는 마방진 문제이다. 알파벳이 주어지고 이에 각각 숫자를 대입하여 결과를 얻는 문제인데 처음에는 이 문제를 어떻게 풀지 고민은 많이 했다. 최대 10개의 알파벳이 주어지므로 각각 알파벳에 0~9까지 숫자를 모두 대입해보는...
보석 도둑
문제: 보석 도둑 (백준 1202번) 구조 분석 구조는 전형적인 greedy 알고리즘이었다. 일반적인 greedy fractional knapsack 문제에서 가방이 여러개 있는 문제여서 가장 작은 가방에 가장 비싼 보석부터 넣는 방식으로 알고리즘을 작성하면 된다. 코드 ``...
회의실 배정
문제: 회의실 배정 (백준 1931번) 구조 분석 전형적인 Greedy algoritm 문제이다. 해당 문제의 풀이 방법은 각 회의를 먼저 끝나는 순서대로 나열을 한 뒤 앞에서부터 고르면 되는 것이다. 알고리즘 자체는 매우 간단하며 쉽게 풀리도록 연습해야 한다. 코드 ```c...
LCS
문제: LCS (백준 9251번) 구조 분석 처음 LCS를 들어봤다면 매우 생소한 문제일 것이다. LCS가 무엇인지부터 알아봐야 한다. 1. LCS(Longest Common Substring, 최대 공통 부분 문자열) -연속하는 공통 부분 찾기 -ACAYKP ...
다리 놓기
문제: 다리 놓기 (백준 1010번) 구조 분석 문제를 처음 보고 드는 생각은 “아! 조합 문제이구나!” 였다. 그런데 문제 카테고리가 dynamic programming이어서 우선 dynamic programming으로 풀어보려고 했다. 조합 문제를 dynamic progr...
map
로봇 청소기
문제: 로봇 청소기 (백준 14503번) 구조 분석 해당 문제는 로봇 청소기의 움직임을 구현하는 문제로 후진을 하는 움직임을 back tracking으로 구현해야 하는 dfs문제이다. 이런 구조의 문제는 dfs를 재귀함수로 구현하는 것이 더 쉽고 간단하다. 풀이 방법 우선 ...
테트로미노
문제: 테트로미노 구조 분석 해당 문제는 지금까지 열심히 풀었던 전형적인 보드판 위의 구현문제이다. 이는 brute force를 이용해 매 칸을 탐색하며 해당 칸을 시점으로 하는 테트리스 블록의 점수 중 최대값을 구하는 문제로 4칸짜리 테트리스 블록을 구현하기 위해 dfs를 ...
뱀
문제: 뱀 (백준 3190번) 구조 분석 해당 문제는 단순 구현 문제이다. 보드에 사과의 위치를 입력 받고 뱀을 움직이며 조건에 따라 게임을 중단하는 간단한 형태의 문제이나 구현하는데 있어서 생각할 조건이 많고 까다로워 풀이를 할 때 헷갈리지 않게 잘 해야 한다. 풀이 방법...
2048 (Easy)
문제: 2048 Easy (백준 12100번) 구조 분석 처음 이 문제를 보고 드는 생각은 bfs 또는 dfs를 이용할 수 있겠다는 것이었다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록의 수를 출력하는 문제였기 때문에 dfs를 이용해야겠다고 생각했다. 그런데 dfs의...
구슬 탈출 2
문제: 구슬 탈출 2 (백준 13460번) 구조 분석 해당 문제를 처음 봤을 때 매우 당황스러웠다. 겉보기에는 이전에 풀어봤던 연구소 (백준 14502번) 문제와 매우 유사했다. 이전에 풀었던 연구소 문제는 map이 주어지고 바이러스가 퍼져나가는 조건이어서 보자마자 bfs를 ...
토마토
문제: 토마토 (백준 7576번) 구조 분석 이는 전형적인 BFS 문제이다. 익은 토마토부터 가까운 토마토를 방문하며 expand 시키며 모든 토마토가 익을 때까지 걸리는 날짜를 세면 된다. 풀이 방법 BFS로 문제를 풀면 된다. 특이하게 어려운 점은 없다. 코드 ```c...
미로 탐색
문졔: 미로 탐색 (백준 2178번) 구조 분석 도착지까지의 최소 칸 수를 세는 문제이므로 전형적인 BFS 문제이다. 해당 좌표와 탐색 depth를 저장하기 위해서 pair<pair<int,int>,int>형태로 노드를 저장해야 한다. 풀이 방법 BFS...
안전 영역
문제: 안전 영역 (백준 2468번) 구조 분석 해당 문제는 연구소(백준 14502번)문제와 매우 유사한 문제이다. 이는 해당 문제와 동일하게 두 가지 큰 알고리즘이 합쳐진 문제이다. 물이 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽,...
연구소
문제: 연구소 (백준 14502번) 구조 분석 해당 문제는 두 가지 큰 알고리즘이 합쳐진 문제이다. 문제의 제시문을 보고 아래의 알고리즘 유추를 할 수 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 이는 전형적인 BFS 문제이...
체스판 다시 칠하기
문제: 체스판 다시 칠하기 (백준 1018번) 구조 분석 처음 문제를 봤을 때, 이를 수학적으로만 풀려고 해서 어려웠다. 그러나 이러한 문제는 convolution 계산하듯이 8*8의 체스보드 프레임을 입력받은 이차원배열 위로 움직이면서 해당 8*8 보드 프레임 위에서의 다시...
dfs
스타트와 링크
문제: 스타트와 링크 (백준 14889번) 구조 분석 해당 문제의 경우 처음에 배열 또는 벡터로 문제를 풀어야 하는지 고민했다. 백터로 능력치를 저장하고 이를 sort하고 다시 나누는 것은 그러나 항상 optimal한 값을 출력할 것 같지 않았다. 그래서 고민하다가 힌트를 ...
연산자 끼워넣기
문제: 연산자 끼워넣기 (백준 14888번) 구조 분석 해당 문제는 수학 문제처럼 보일 수 있으나 조건을 잘 살펴보면 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.라는 말이 있다. 즉, 이는 backtracking문제이며 이는 dfs를 이용해서 쉽게 풀 수 있다. ...
로봇 청소기
문제: 로봇 청소기 (백준 14503번) 구조 분석 해당 문제는 로봇 청소기의 움직임을 구현하는 문제로 후진을 하는 움직임을 back tracking으로 구현해야 하는 dfs문제이다. 이런 구조의 문제는 dfs를 재귀함수로 구현하는 것이 더 쉽고 간단하다. 풀이 방법 우선 ...
테트로미노
문제: 테트로미노 구조 분석 해당 문제는 지금까지 열심히 풀었던 전형적인 보드판 위의 구현문제이다. 이는 brute force를 이용해 매 칸을 탐색하며 해당 칸을 시점으로 하는 테트리스 블록의 점수 중 최대값을 구하는 문제로 4칸짜리 테트리스 블록을 구현하기 위해 dfs를 ...
2048 (Easy)
문제: 2048 Easy (백준 12100번) 구조 분석 처음 이 문제를 보고 드는 생각은 bfs 또는 dfs를 이용할 수 있겠다는 것이었다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록의 수를 출력하는 문제였기 때문에 dfs를 이용해야겠다고 생각했다. 그런데 dfs의...
트리의 부모 찾기
문제: 트리의 부모 찾기 (백준 11725번) 구조 분석 해당 문제를 처음 접하고 매우 당황했다. 지금까지는 트리문제는 트리구조를 만들고 이를 순회하며 탐색하는 경우만 접했기 때문에 루트노드와 자식노드가 정해져있지 않은 트리를 어떻게 만들어야 할 지 감이 안왔기 때문이다. 우...
DFS와 BFS
문제: DFS와 BFS (백준 1260번) 구조 분석 정점의 개수와 간선의 개수를 입력받고 간선 정보를 입력한 뒤 해당 graph에 대해 DFS와 BFS를 실시하는 문제이다. 풀이 방법 DFS는 stack을 사용한다. 이때 주의할 점은 방문한 노드를 재방문 하지 않도록 설정해...
안전 영역
문제: 안전 영역 (백준 2468번) 구조 분석 해당 문제는 연구소(백준 14502번)문제와 매우 유사한 문제이다. 이는 해당 문제와 동일하게 두 가지 큰 알고리즘이 합쳐진 문제이다. 물이 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽,...
연구소
문제: 연구소 (백준 14502번) 구조 분석 해당 문제는 두 가지 큰 알고리즘이 합쳐진 문제이다. 문제의 제시문을 보고 아래의 알고리즘 유추를 할 수 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 이는 전형적인 BFS 문제이...
bfs
구슬 탈출 2
문제: 구슬 탈출 2 (백준 13460번) 구조 분석 해당 문제를 처음 봤을 때 매우 당황스러웠다. 겉보기에는 이전에 풀어봤던 연구소 (백준 14502번) 문제와 매우 유사했다. 이전에 풀었던 연구소 문제는 map이 주어지고 바이러스가 퍼져나가는 조건이어서 보자마자 bfs를 ...
트리의 부모 찾기
문제: 트리의 부모 찾기 (백준 11725번) 구조 분석 해당 문제를 처음 접하고 매우 당황했다. 지금까지는 트리문제는 트리구조를 만들고 이를 순회하며 탐색하는 경우만 접했기 때문에 루트노드와 자식노드가 정해져있지 않은 트리를 어떻게 만들어야 할 지 감이 안왔기 때문이다. 우...
토마토
문제: 토마토 (백준 7576번) 구조 분석 이는 전형적인 BFS 문제이다. 익은 토마토부터 가까운 토마토를 방문하며 expand 시키며 모든 토마토가 익을 때까지 걸리는 날짜를 세면 된다. 풀이 방법 BFS로 문제를 풀면 된다. 특이하게 어려운 점은 없다. 코드 ```c...
미로 탐색
문졔: 미로 탐색 (백준 2178번) 구조 분석 도착지까지의 최소 칸 수를 세는 문제이므로 전형적인 BFS 문제이다. 해당 좌표와 탐색 depth를 저장하기 위해서 pair<pair<int,int>,int>형태로 노드를 저장해야 한다. 풀이 방법 BFS...
DFS와 BFS
문제: DFS와 BFS (백준 1260번) 구조 분석 정점의 개수와 간선의 개수를 입력받고 간선 정보를 입력한 뒤 해당 graph에 대해 DFS와 BFS를 실시하는 문제이다. 풀이 방법 DFS는 stack을 사용한다. 이때 주의할 점은 방문한 노드를 재방문 하지 않도록 설정해...
안전 영역
문제: 안전 영역 (백준 2468번) 구조 분석 해당 문제는 연구소(백준 14502번)문제와 매우 유사한 문제이다. 이는 해당 문제와 동일하게 두 가지 큰 알고리즘이 합쳐진 문제이다. 물이 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽,...
연구소
문제: 연구소 (백준 14502번) 구조 분석 해당 문제는 두 가지 큰 알고리즘이 합쳐진 문제이다. 문제의 제시문을 보고 아래의 알고리즘 유추를 할 수 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 이는 전형적인 BFS 문제이...
intro
CASS LAB 학부연구생 INTRO
포스팅 목표 해당 포스팅은 2021년 여름방학동안 학부연구생을 하며 교육받은 내용들을 복습하고 정리하기 위함이다. 학부연구생 활동을 하면서 주로 컴파일러 optimization 기법들을 공부하고, LLVM, OpenCL, TVM을 이용하여 간단한 실습을 진행하는 활동을 했다.
졸업프로젝트 주제 선정2
논문 분석 Accurate Multivariate Stock Movement Prediction via Data-Axis Transformer with Multi-Level Contexts의 내용을 바탕으로 한 인공지능 주가 예측에 대한 정리. 문제 설정 주가 정보를 바탕으로 오...
졸업프로젝트 주제 선정1
주제: AI를 이용한 주가예측 AI의 금융 응용은 매우 중요한 부분으로 떠오른다. 왜냐하면 금융 분야에는 매우 큰 데이터 셋이 있으며 충분히 자극이 되는 흥미가 있고, 또한 성공 시 막대한 보상을 얻을 수 있기 때문이다. Q1. 주식 시장이 예측이 가능한가? 충분히 예측이 가능하...
졸업프로젝트 INTRO
포스팅 목표 해당 포스팅은 졸업프로젝트 진행 및 관련 지식을 기록하기 위함이다. 포스팅 계획 졸업프로젝트 진행 졸업프로젝트 계획 및 진행상황 기록 Background Knowledge 기록 졸업프로젝트 진행에 필요한 전공지식 및 논문 기록
백준 INTRO
포스팅 목표 해당 포스팅은 백준 문제 풀이 및 복기를 위함이다. 포스팅 계획 백준 문제 백준 문제와 영역을 정리 소스 코드 백준 문제 풀이 코드 정리 정리 해당 문제의 접근법 및 주의점 정리
알고리즘 INTRO
포스팅 목표 해당 포스팅은 알고리즘 별 풀이 및 접근법을 정리하기 위함이다.
LLVM
LLVM Optimization (6)
실습 5 [실습 5]에서는 IR 레벨에서 명령어의 위치를 변경하고 메모리 명령어의 종속성 관계에 대해 파악한다. 일반적으로 산술 연산 명령어와는 다르게 메모리 명령어(load/store)의 종속 관계는 컴파일러 입장에서 알기 어렵다. 예를 들어 X주소에서 값을 읽는 명령어 load...
LLVM Optimization (5)
실습 4 [실습 4]에서는 [실습 3]을 바탕으로 전체 명령어 중 특정 종류의 명령어에 접근하여 새로운 명령어를 생성하고, 기존의 명령어를 삭제하고, 새로운 명령어로 기존의 명령어를 대체하는 작업을 수행한다. 명령어 생성 LLVM에서는 명령어를 생성하기 위해 llvm::IRBui...
LLVM Optimization (4)
실습 3 [실습 3]에서는 프로그램 내 특정 명령어의 수를 세어 출력하는 간단한 정적 프로파일러를 생성한다. LLVM 6.0.1 기준으로 LLVM IR에는 총 64개의 명령어 Opcode가 있으며 자주 사용되는 명령어는 아래와 같다. BinaryOperator: add, su...
LLVM Optimization (3)
실습 2 [실습 2]에서는 LLVM의 기본적인 module 구조를 이해하고, IR 내의 명렬어들을 C++ iterator를 사용하여 순회 및 출력을 한다. llvm::Module -> llvm::Function -> llvm::BasicBlock -> llvm...
LLVM Optimization (2)
실습 1 [실습 1]에서는 clang, llvm-as, llvm-dis, llc 등의 툴을 사용하여 소스 코드 (*.c) 를 IR 코드 (*.bc, *.ll)로 이를 다시 바이너리 코드로 컴파일 하는 방법을 익힌다. clang: LLVM IR 기반 컴파일러로 C,C++ 등 다...
LLVM Optimization (1)
LLVM 이란? LLVM은 컴파일러를 위한 라이브러리 및 Tool Chain 모음므로써, 컴파일러(clang), 링커(llc), 디버거(ldb)등 다양한 서브 프로젝트들을 가지고 있다. LLVM은 LLVM IR이라는 Intemediate Representation을 사용하는데, S...
dynamic-programming
퇴사
문제: 퇴사 (백준 14501) 구조 분석 최근에 계속 시뮬레이션/구현 문제만 풀다가 간단한 형태의 문제를 봐서 신났다. 그런데 처음에 문제를 봤을 때 어? 스케줄링? 그러면 전형적인 greedy 문제구나! 해서 풀었다가 막혀서 당황했다. 해당 문제는 최대한 많은 스케줄을 잡...
LCS
문제: LCS (백준 9251번) 구조 분석 처음 LCS를 들어봤다면 매우 생소한 문제일 것이다. LCS가 무엇인지부터 알아봐야 한다. 1. LCS(Longest Common Substring, 최대 공통 부분 문자열) -연속하는 공통 부분 찾기 -ACAYKP ...
다리 놓기
문제: 다리 놓기 (백준 1010번) 구조 분석 문제를 처음 보고 드는 생각은 “아! 조합 문제이구나!” 였다. 그런데 문제 카테고리가 dynamic programming이어서 우선 dynamic programming으로 풀어보려고 했다. 조합 문제를 dynamic progr...
계단 오르기
문제: 계단 오르기 (백준 2579번) 문제 입력 및 출력 구조 분석 해당 문제는 전형적인 dynamic programming 문제이다. Dynamic programming을 이용하고자 한 근거는 다음과 같다. n번째 계단에서의 점수를 dp(n)이라고 하자. dp(...
Dynamic Programming
Dynamic Programming (동적 계획법) 이란? 주어진 problem을 작은 subproblem으로 나눠 푼 다음 이를 통해 최종 답을 얻는 방식 이를 충족하기 위해서는 다음의 조건이 필요하다. 주어진 problem을 작은 규모의 subproblem으로 나눌 수 있...
github
Git Flow 시작하기
Git Flow git-flow는 브랜치 모델을 쉽게 사용할 수 있도록 한 git의 확장이다. 여기에는 메인 브랜치 (master, develop)과 보조 브랜치 (feature, release, hotfix)가 있다. 1. Master Branch: 제품으로 출시될 수 있는 브랜...
깃헙 잔디가 안 심어진다고?
문제 Commit은 되는데 잔디가 없을때 나의 경우 repository 생성을 할 때는 잔디가 정상적으로 심어졌다. 그래서 문제가 없는 줄 알았지만 최근에 github 잔디에 관심을 가지게 되면서 내 잔디를 확인해보니.. 텅 비어있었다. 그래서 문제를 확인해본 결과 git에 등...
깃헙 블로그 생성 및 포스팅 하는법
깃헙 블로그 생성하기 0. 준비 사항 Github에 미리 회원가입을 합니다. Github Pages를 이용하는 이유는 markdown을 이용하여 간단하게 포스팅을 할 수 있고, 아래와 같이 코드를 보기 좋게 넣을 수 있다는 장점 때문입니다. printf("Wellcome to m...
깃헙 블로그에 이미지 삽입하기
이미지 업로드 1. 업로드할 이미지를 복사한다. 업로드하고 싶은 이미지 자체를 복사해준다. 2. 아무 Github repository에 들어가 Issue 작성 페이지를 연다. 3. 복사한 이미지를 붙여넣기 하면 markdown용 이미지 링크가 생성된다. 해당 Issue는 이...
math
시험 감독
문제: 시험 감독 (백준 13458번) 풀이 방법 해당 문제는 매우 간단한 수학 및 사칙연산 문제이므로 구조분석할 필요없이 바로 풀면 된다. 우선 vector를 이용하여 각 고사실 별 인원을 입력받고 주감독관 1명을 배치 후 부감독관을 나누기와 modulo 연산을 통해서 배치...
어린 왕자
문제: 어린 왕자 (백준 1004번) 풀이 방법 이는 이전의 터렛 문제와 매우 흡사하다. 다만 터렛 문제에서는 두 원 사이의 모든 관계를 다뤘다면 해당 문제에서는 원과 점 사이의 관계를 다루는 문제이다. 점이 원 안에 있는 경우 행성계 진입/이탈이 일어나게 되므로 아래의 경...
터렛
문제: 터렛 (백준 1002번) 풀이 방법 Geometry 문제는 좌표평면을 떠올리며 풀어야 한다. 특지 중학교 고등학교 과정의 방정식 및 판정식을 기억하고 있으면 풀이에 도움이 된다. 해당 문제의 경우 두 원의 중점과 반지름이 주어진 상황에서 두 원의 교점의 개수를 구하는 ...
다리 놓기
문제: 다리 놓기 (백준 1010번) 구조 분석 문제를 처음 보고 드는 생각은 “아! 조합 문제이구나!” 였다. 그런데 문제 카테고리가 dynamic programming이어서 우선 dynamic programming으로 풀어보려고 했다. 조합 문제를 dynamic progr...
greedy
단어 수학
문제: 단어 수학 (백준 1339번) 구조 분석 해당 문제는 마방진 문제이다. 알파벳이 주어지고 이에 각각 숫자를 대입하여 결과를 얻는 문제인데 처음에는 이 문제를 어떻게 풀지 고민은 많이 했다. 최대 10개의 알파벳이 주어지므로 각각 알파벳에 0~9까지 숫자를 모두 대입해보는...
보석 도둑
문제: 보석 도둑 (백준 1202번) 구조 분석 구조는 전형적인 greedy 알고리즘이었다. 일반적인 greedy fractional knapsack 문제에서 가방이 여러개 있는 문제여서 가장 작은 가방에 가장 비싼 보석부터 넣는 방식으로 알고리즘을 작성하면 된다. 코드 ``...
회의실 배정
문제: 회의실 배정 (백준 1931번) 구조 분석 전형적인 Greedy algoritm 문제이다. 해당 문제의 풀이 방법은 각 회의를 먼저 끝나는 순서대로 나열을 한 뒤 앞에서부터 고르면 되는 것이다. 알고리즘 자체는 매우 간단하며 쉽게 풀리도록 연습해야 한다. 코드 ```c...
Greedy Algorithm
Greedy Algorithm이란? Greedy algorithm이란 이후의 상황을 고려하지 않고 각 단계에서 최선의 선택을 하는 알고리즘이다. 이는 dynamic programming이 너무 많은 일을 한다고 판단하는 것에서 시작한 알고리즘이다. 그러나 이는 local maxim...
string
트리 순회
문제: 트리 순회 (백준 1991번) 구조 분석 해당 문제는 전형적인 tree문제이다. 이는 tree 순회문제로 자료구조의 기본이 되는 내용이다. 트리를 순회하는 방법은 다음과 같다. pre order: (root) (left) (right) 순서로 순회 in order: (...
체스판 다시 칠하기
문제: 체스판 다시 칠하기 (백준 1018번) 구조 분석 처음 문제를 봤을 때, 이를 수학적으로만 풀려고 해서 어려웠다. 그러나 이러한 문제는 convolution 계산하듯이 8*8의 체스보드 프레임을 입력받은 이차원배열 위로 움직이면서 해당 8*8 보드 프레임 위에서의 다시...
단어 수학
문제: 단어 수학 (백준 1339번) 구조 분석 해당 문제는 마방진 문제이다. 알파벳이 주어지고 이에 각각 숫자를 대입하여 결과를 얻는 문제인데 처음에는 이 문제를 어떻게 풀지 고민은 많이 했다. 최대 10개의 알파벳이 주어지므로 각각 알파벳에 0~9까지 숫자를 모두 대입해보는...
LCS
문제: LCS (백준 9251번) 구조 분석 처음 LCS를 들어봤다면 매우 생소한 문제일 것이다. LCS가 무엇인지부터 알아봐야 한다. 1. LCS(Longest Common Substring, 최대 공통 부분 문자열) -연속하는 공통 부분 찾기 -ACAYKP ...
back-tracking
스타트와 링크
문제: 스타트와 링크 (백준 14889번) 구조 분석 해당 문제의 경우 처음에 배열 또는 벡터로 문제를 풀어야 하는지 고민했다. 백터로 능력치를 저장하고 이를 sort하고 다시 나누는 것은 그러나 항상 optimal한 값을 출력할 것 같지 않았다. 그래서 고민하다가 힌트를 ...
연산자 끼워넣기
문제: 연산자 끼워넣기 (백준 14888번) 구조 분석 해당 문제는 수학 문제처럼 보일 수 있으나 조건을 잘 살펴보면 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.라는 말이 있다. 즉, 이는 backtracking문제이며 이는 dfs를 이용해서 쉽게 풀 수 있다. ...
로봇 청소기
문제: 로봇 청소기 (백준 14503번) 구조 분석 해당 문제는 로봇 청소기의 움직임을 구현하는 문제로 후진을 하는 움직임을 back tracking으로 구현해야 하는 dfs문제이다. 이런 구조의 문제는 dfs를 재귀함수로 구현하는 것이 더 쉽고 간단하다. 풀이 방법 우선 ...
2048 (Easy)
문제: 2048 Easy (백준 12100번) 구조 분석 처음 이 문제를 보고 드는 생각은 bfs 또는 dfs를 이용할 수 있겠다는 것이었다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록의 수를 출력하는 문제였기 때문에 dfs를 이용해야겠다고 생각했다. 그런데 dfs의...
setting
Git Flow 시작하기
Git Flow git-flow는 브랜치 모델을 쉽게 사용할 수 있도록 한 git의 확장이다. 여기에는 메인 브랜치 (master, develop)과 보조 브랜치 (feature, release, hotfix)가 있다. 1. Master Branch: 제품으로 출시될 수 있는 브랜...
연구실 서버 접속 및 환경 구축 0
Remote Desktop 이번 졸업프로젝트를 진행하면서 Remote Desktop을 이용하게 되었다. 이번에는 윈도우 서버를 할당받았는데 RDP를 이용하게 되었다. 이는 마이크로소프트에서 제작한 그래픽 공유 프로토콜이며 인터넷 연결을 통해 원격 PC에 연결할 수 있다. 다운로드...
깃헙 잔디가 안 심어진다고?
문제 Commit은 되는데 잔디가 없을때 나의 경우 repository 생성을 할 때는 잔디가 정상적으로 심어졌다. 그래서 문제가 없는 줄 알았지만 최근에 github 잔디에 관심을 가지게 되면서 내 잔디를 확인해보니.. 텅 비어있었다. 그래서 문제를 확인해본 결과 git에 등...
vector
트리의 부모 찾기
문제: 트리의 부모 찾기 (백준 11725번) 구조 분석 해당 문제를 처음 접하고 매우 당황했다. 지금까지는 트리문제는 트리구조를 만들고 이를 순회하며 탐색하는 경우만 접했기 때문에 루트노드와 자식노드가 정해져있지 않은 트리를 어떻게 만들어야 할 지 감이 안왔기 때문이다. 우...
트리 순회
문제: 트리 순회 (백준 1991번) 구조 분석 해당 문제는 전형적인 tree문제이다. 이는 tree 순회문제로 자료구조의 기본이 되는 내용이다. 트리를 순회하는 방법은 다음과 같다. pre order: (root) (left) (right) 순서로 순회 in order: (...
회의실 배정
문제: 회의실 배정 (백준 1931번) 구조 분석 전형적인 Greedy algoritm 문제이다. 해당 문제의 풀이 방법은 각 회의를 먼저 끝나는 순서대로 나열을 한 뒤 앞에서부터 고르면 되는 것이다. 알고리즘 자체는 매우 간단하며 쉽게 풀리도록 연습해야 한다. 코드 ```c...
sort
단어 수학
문제: 단어 수학 (백준 1339번) 구조 분석 해당 문제는 마방진 문제이다. 알파벳이 주어지고 이에 각각 숫자를 대입하여 결과를 얻는 문제인데 처음에는 이 문제를 어떻게 풀지 고민은 많이 했다. 최대 10개의 알파벳이 주어지므로 각각 알파벳에 0~9까지 숫자를 모두 대입해보는...
보석 도둑
문제: 보석 도둑 (백준 1202번) 구조 분석 구조는 전형적인 greedy 알고리즘이었다. 일반적인 greedy fractional knapsack 문제에서 가방이 여러개 있는 문제여서 가장 작은 가방에 가장 비싼 보석부터 넣는 방식으로 알고리즘을 작성하면 된다. 코드 ``...
회의실 배정
문제: 회의실 배정 (백준 1931번) 구조 분석 전형적인 Greedy algoritm 문제이다. 해당 문제의 풀이 방법은 각 회의를 먼저 끝나는 순서대로 나열을 한 뒤 앞에서부터 고르면 되는 것이다. 알고리즘 자체는 매우 간단하며 쉽게 풀리도록 연습해야 한다. 코드 ```c...
brute-force
테트로미노
문제: 테트로미노 구조 분석 해당 문제는 지금까지 열심히 풀었던 전형적인 보드판 위의 구현문제이다. 이는 brute force를 이용해 매 칸을 탐색하며 해당 칸을 시점으로 하는 테트리스 블록의 점수 중 최대값을 구하는 문제로 4칸짜리 테트리스 블록을 구현하기 위해 dfs를 ...
2048 (Easy)
문제: 2048 Easy (백준 12100번) 구조 분석 처음 이 문제를 보고 드는 생각은 bfs 또는 dfs를 이용할 수 있겠다는 것이었다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록의 수를 출력하는 문제였기 때문에 dfs를 이용해야겠다고 생각했다. 그런데 dfs의...
Brute Force
Brute Force (브루트 포스) 란? Brute force란 모든 경우를 다 확인하는 방법이다. 이는 완전탐색 알고리즘으로 100% 정답을 얻을 수 있는 알고리즘이다. 이를 더 효율적으로 구현하기 위해서는 자료 탐색 시 알고리즘을 잘 설계하여 특정 구조로 탐색을 실시하는 것이...
brute-froce
안전 영역
문제: 안전 영역 (백준 2468번) 구조 분석 해당 문제는 연구소(백준 14502번)문제와 매우 유사한 문제이다. 이는 해당 문제와 동일하게 두 가지 큰 알고리즘이 합쳐진 문제이다. 물이 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽,...
연구소
문제: 연구소 (백준 14502번) 구조 분석 해당 문제는 두 가지 큰 알고리즘이 합쳐진 문제이다. 문제의 제시문을 보고 아래의 알고리즘 유추를 할 수 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 이는 전형적인 BFS 문제이...
체스판 다시 칠하기
문제: 체스판 다시 칠하기 (백준 1018번) 구조 분석 처음 문제를 봤을 때, 이를 수학적으로만 풀려고 해서 어려웠다. 그러나 이러한 문제는 convolution 계산하듯이 8*8의 체스보드 프레임을 입력받은 이차원배열 위로 움직이면서 해당 8*8 보드 프레임 위에서의 다시...
priority_queue
최소 힙
문제: 최소 힙 (백준 1927번) 구조 분석 최대 힙 문제와 마찬가지로 stl의 priority queue를 이용하여 힙을 구현하는 문제이다. 풀이 방법 최대 힙: 내림차순 정렬 최소 힙: 오름차순 정렬 Priority queue에는 오름차순과 내림차순같은 정렬 기...
최대 힙
문제: 최대 힙 (백준 11279번) 구조 분석 해당 문제는 heap이라는 자료구조를 구현하는 문제이다. 이는 기본적인 자료구조로 c++의 stl에서 제공하는 priority_queue를 이용하면 매우 쉽게 풀 수 있다. 풀이 방법 내림차순 정렬을 위해서는 max heap을...
절댓값 힙
문제: 절댓값 힙 (백준 11286번) 구조 분석 해당 문제 역시 priority queue를 이용하여 heap을 구현하는 문제이다. 다만 이전의 오름차순이나 내림차순 이외의 조건이 붙어서 해당 조건을 위한 비교연산자를 생성해줘야 한다. 풀이 방법 비교 연산자를 활용하여 p...
heap
최소 힙
문제: 최소 힙 (백준 1927번) 구조 분석 최대 힙 문제와 마찬가지로 stl의 priority queue를 이용하여 힙을 구현하는 문제이다. 풀이 방법 최대 힙: 내림차순 정렬 최소 힙: 오름차순 정렬 Priority queue에는 오름차순과 내림차순같은 정렬 기...
최대 힙
문제: 최대 힙 (백준 11279번) 구조 분석 해당 문제는 heap이라는 자료구조를 구현하는 문제이다. 이는 기본적인 자료구조로 c++의 stl에서 제공하는 priority_queue를 이용하면 매우 쉽게 풀 수 있다. 풀이 방법 내림차순 정렬을 위해서는 max heap을...
절댓값 힙
문제: 절댓값 힙 (백준 11286번) 구조 분석 해당 문제 역시 priority queue를 이용하여 heap을 구현하는 문제이다. 다만 이전의 오름차순이나 내림차순 이외의 조건이 붙어서 해당 조건을 위한 비교연산자를 생성해줘야 한다. 풀이 방법 비교 연산자를 활용하여 p...
md
깃헙 블로그 생성 및 포스팅 하는법
깃헙 블로그 생성하기 0. 준비 사항 Github에 미리 회원가입을 합니다. Github Pages를 이용하는 이유는 markdown을 이용하여 간단하게 포스팅을 할 수 있고, 아래와 같이 코드를 보기 좋게 넣을 수 있다는 장점 때문입니다. printf("Wellcome to m...
깃헙 블로그에 이미지 삽입하기
이미지 업로드 1. 업로드할 이미지를 복사한다. 업로드하고 싶은 이미지 자체를 복사해준다. 2. 아무 Github repository에 들어가 Issue 작성 페이지를 연다. 3. 복사한 이미지를 붙여넣기 하면 markdown용 이미지 링크가 생성된다. 해당 Issue는 이...
git
Git Flow 시작하기
Git Flow git-flow는 브랜치 모델을 쉽게 사용할 수 있도록 한 git의 확장이다. 여기에는 메인 브랜치 (master, develop)과 보조 브랜치 (feature, release, hotfix)가 있다. 1. Master Branch: 제품으로 출시될 수 있는 브랜...
깃헙 잔디가 안 심어진다고?
문제 Commit은 되는데 잔디가 없을때 나의 경우 repository 생성을 할 때는 잔디가 정상적으로 심어졌다. 그래서 문제가 없는 줄 알았지만 최근에 github 잔디에 관심을 가지게 되면서 내 잔디를 확인해보니.. 텅 비어있었다. 그래서 문제를 확인해본 결과 git에 등...
graph
DFS와 BFS
문제: DFS와 BFS (백준 1260번) 구조 분석 정점의 개수와 간선의 개수를 입력받고 간선 정보를 입력한 뒤 해당 graph에 대해 DFS와 BFS를 실시하는 문제이다. 풀이 방법 DFS는 stack을 사용한다. 이때 주의할 점은 방문한 노드를 재방문 하지 않도록 설정해...
Graph
Graph 이론 알고리즘 BFS/DFS 와 같은 알고리즘과 더불어 최단 경로 문제도 그래프 알고리즘의 한 유형이다. 문제에서 서로 다른 개체가 연결되어 있다는 힌트를 보면 그래프 알고리즘을 생각해야 한다. Graph Algorithm 그래프 문제는 두 가지 방법을 이용하여 구현한...
geometry
어린 왕자
문제: 어린 왕자 (백준 1004번) 풀이 방법 이는 이전의 터렛 문제와 매우 흡사하다. 다만 터렛 문제에서는 두 원 사이의 모든 관계를 다뤘다면 해당 문제에서는 원과 점 사이의 관계를 다루는 문제이다. 점이 원 안에 있는 경우 행성계 진입/이탈이 일어나게 되므로 아래의 경...
터렛
문제: 터렛 (백준 1002번) 풀이 방법 Geometry 문제는 좌표평면을 떠올리며 풀어야 한다. 특지 중학교 고등학교 과정의 방정식 및 판정식을 기억하고 있으면 풀이에 도움이 된다. 해당 문제의 경우 두 원의 중점과 반지름이 주어진 상황에서 두 원의 교점의 개수를 구하는 ...
tree
트리의 부모 찾기
문제: 트리의 부모 찾기 (백준 11725번) 구조 분석 해당 문제를 처음 접하고 매우 당황했다. 지금까지는 트리문제는 트리구조를 만들고 이를 순회하며 탐색하는 경우만 접했기 때문에 루트노드와 자식노드가 정해져있지 않은 트리를 어떻게 만들어야 할 지 감이 안왔기 때문이다. 우...
트리 순회
문제: 트리 순회 (백준 1991번) 구조 분석 해당 문제는 전형적인 tree문제이다. 이는 tree 순회문제로 자료구조의 기본이 되는 내용이다. 트리를 순회하는 방법은 다음과 같다. pre order: (root) (left) (right) 순서로 순회 in order: (...
queue
뱀
문제: 뱀 (백준 3190번) 구조 분석 해당 문제는 단순 구현 문제이다. 보드에 사과의 위치를 입력 받고 뱀을 움직이며 조건에 따라 게임을 중단하는 간단한 형태의 문제이나 구현하는데 있어서 생각할 조건이 많고 까다로워 풀이를 할 때 헷갈리지 않게 잘 해야 한다. 풀이 방법...
구슬 탈출 2
문제: 구슬 탈출 2 (백준 13460번) 구조 분석 해당 문제를 처음 봤을 때 매우 당황스러웠다. 겉보기에는 이전에 풀어봤던 연구소 (백준 14502번) 문제와 매우 유사했다. 이전에 풀었던 연구소 문제는 map이 주어지고 바이러스가 퍼져나가는 조건이어서 보자마자 bfs를 ...
jekyll
깃헙 블로그 생성 및 포스팅 하는법
깃헙 블로그 생성하기 0. 준비 사항 Github에 미리 회원가입을 합니다. Github Pages를 이용하는 이유는 markdown을 이용하여 간단하게 포스팅을 할 수 있고, 아래와 같이 코드를 보기 좋게 넣을 수 있다는 장점 때문입니다. printf("Wellcome to m...
c/c+
계단 오르기
문제: 계단 오르기 (백준 2579번) 문제 입력 및 출력 구조 분석 해당 문제는 전형적인 dynamic programming 문제이다. Dynamic programming을 이용하고자 한 근거는 다음과 같다. n번째 계단에서의 점수를 dp(n)이라고 하자. dp(...
LCS
LCS
문제: LCS (백준 9251번) 구조 분석 처음 LCS를 들어봤다면 매우 생소한 문제일 것이다. LCS가 무엇인지부터 알아봐야 한다. 1. LCS(Longest Common Substring, 최대 공통 부분 문자열) -연속하는 공통 부분 찾기 -ACAYKP ...
priority-queue
보석 도둑
문제: 보석 도둑 (백준 1202번) 구조 분석 구조는 전형적인 greedy 알고리즘이었다. 일반적인 greedy fractional knapsack 문제에서 가방이 여러개 있는 문제여서 가장 작은 가방에 가장 비싼 보석부터 넣는 방식으로 알고리즘을 작성하면 된다. 코드 ``...
deque
뱀
문제: 뱀 (백준 3190번) 구조 분석 해당 문제는 단순 구현 문제이다. 보드에 사과의 위치를 입력 받고 뱀을 움직이며 조건에 따라 게임을 중단하는 간단한 형태의 문제이나 구현하는데 있어서 생각할 조건이 많고 까다로워 풀이를 할 때 헷갈리지 않게 잘 해야 한다. 풀이 방법...