문제 문제 바로가기> BOJ 11057번: 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 아래와 같은 규칙을 가지므로, 점화식이 dp[i][j] = (dp[i][j-1] + dp[i-1][j])%DIV 이다! #include #define MAX 1001 #define DIV 10007 using namespace std; int N; int dp[MAX][11]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0)..

1학년 때 JAVA를 처음 배우고, 2학년 이후로는 JAVA를 쓸 일이 거의 없었던 것 같다. (그래도 1학년 때 나름 JAVA 공부 열심히 해뒀음 ㅎ) 현업에서는 JAVA를 많이 사용한다고 하니,,, SSAFY 입과 전에 열심히 복습해 보겠어 😎 (if, for, while 문 같은 내용은 정리하지 않았다! java 적인 것? 위주로 정리했다.) JAVA 객체 지향적 언어 (↔ 절차 지향적 언어) write once run anywhere (동일한 프로그램이 운영체제 가리지 않고 실행) * WROA - 현대에는 자바뿐만 아니라 대부분의 프로그래밍 언어가 이를 일부분에서 모두 지원 객체지향 프로그래밍 Object-Oriented Programming 로직을 상태(state)와 행위(behave)로 이루어..

문제 문제 바로가기> BOJ 5014번: 스타트링크 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 BFS를 사용해서 푸는 문제였다! #include #include #define MAX 1000001 using namespace std; int F, S, G, U, D; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> F >> S >> G >> U >> D; visited[S] = true; queue q; q.push(..

동기화 vs 비동기화1. 동기화(Synchronous) 동시에 일어나서, 결과가 그 자리에서 주어짐설계가 매우 간단하고 직관적결과가 주어질 때까지 아무것도 못하고 대기해야 함2. 비동기화(Asynchronous)동시에 일어나지 않아서, 결과가 그자리에서 주어지지 않음동기화보다 복잡함결과가 주어지는데 시간이 걸리지만, 그 동안 다른 작업을 할 수 있어서 자원을 효율적으로 사용할 수 있음 Race Condition: 여러 프로세스들이 동시에 데이터에 접근할 때 어떤 순서로 접근하느냐에 따라 결과 값이 달라질 수 있는 상황 공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있음Race condition을 막고, 일관성을 유지하기 위해 협력 프로세스 간의 실행 순서..

문제 문제 바로가기> BOJ 16236번: 아기상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제의 요구사항에 따라 구현해 주면 된다. 설명은 주석으로 자세히 적어 놓았다! 이런 문제는 물고기 먹은 처리, 상어 정보 update 등을 잊지 않고 해주는 게 중요한 것 같다. 문제를 풀 때, 알고 있으면 도움이 되는 개념은 다음과 같다! ✔️ operator 재정의 ✔️ 구조체 정의 ✔️ 그래프 탐색 C++ #include #include #include #define MAX 21 using n..

문제 문제 바로가기> BOJ 1806번: 부분합 1806번: 부분합 첫째 줄에 N (10 ≤ N > N >> S; for(int i=0; i> num[i]; } void solution(){..

문제 문제 바로가기> BOJ 1253번: 좋다 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 정렬 후 두 포인터를 이용하여 "좋은" 수를 찾을 수 있다. * 서로 다른 두 수의 합은 해당 수를 사용해서 만들어지면 안된다! #include #include #define MAX 2001 using namespace std; int N; int num[MAX]; void input(){ cin >> N; for(int i=0; i> num[i]; } void solution(){ sort(num, num+N); // 정렬 int ans..

문제 문제 바로가기> BOJ 2887번: 행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 MST를 만드는 문제이다. 다만, 메모리 초과 방지를 위해 정렬을 사용하여 O(N2)이 아닌, O(3N)개의 비용 후보만 가지도록 해야한다! #include #include #include #include #define MAX 100001 using namespace std; vector X, Y, Z; struct edge{ int a, b, dist; bool opera..

문제 문제 바로가기> BOJ 5430번: AC 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 덱에 들어갈 숫자의 길이가 1 이상일 수 있다. (0 T; while(T--){ string p; cin >> p; int size; cin >> size; string arr; cin >> arr; deque dq; string num = ""; for(int i=1; i

문제 문제 바로가기> BOJ 13549번: 숨바꼭질 3 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 순간이동을 하는데는 시간이 소요되지 않으므로, 해당 위치에 최단 거리로 도착할 수 있도록, 시간을 업데이트해 줄 필요가 있다! #include #include #define MAX 100001 using namespace std; int N, K; int visit_time[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.ti..

문제 문제 바로가기> BOJ 1697번: 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 기존의 방문한 지점을 제외하고, 이동할 수 있는 총 3가지 방법으로 이동하면서 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 찾아주면 된다! #include #include #define MAX 100001 using namespace std; int N, K; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.t..

문제 문제 바로가기> BOJ 2294번: 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 dp[j] : 가치의 합 j를 만드는 데 사용한 동전의 최소 개수 1. j == coin[i] 인 경우, 동전 하나만으로 j를 만들 수 있으므로, dp[j] = 1 2. j > coin[i] 인 경우, 해당 동전을 사용해서 더 적은 동전으로 j를 만들 수 있는지, dp[j] = min(dp[j], dp[j-coin[i]]+1) #include #define INF 9876543..

문제 문제 바로가기> BOJ 2293번: 동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2차원 배열로 풀면 메모리 초과가 발생하므로 1차원 배열로 풀어야 한다. i원 동전을 사용하여 j원을 만들 때 j-coin[i]의 누적합만 알면 되므로 1차원 배열로 풀 수 있다. #include #define MAX 101 #define MAX_K 10001 using namespace std; int n, k; int coin[MAX], dp[MAX_K]; void input(){ cin >> n >> k..

면접관에게 극찬 받는 PT 면접 발표 방법 위 영상을 토대로 PT 면접 준비하는 방법을 정리해 보겠다. PT 면접을 주요 평가 요소 출제 유형 1. 문제 해결형 ~한 상황에서 ~걸 해결/제안/극복해 보세요. 2. 주제 설명형 (특히 이공계) A에 대해 설명해보세요. 3. 시사 관련 ~한 사회적 이슈에 대한 견해를 밝혀보세요. PT 면접 구조 안녕하십니까. 지원자 000입니다. 저는 ~한 주제에 대해 발표를 진행하고자 합니다. (면접의 과정으로서도 굉장히 진지하게 이 질문에 대한 답을 구하기 위해서 노력을 했지만 또 한편으로는 제가 현직자의 입장에서 회사와 관련된 중요한 이슈를 해결한다라는 굉장히 큰 책임감을 가지고 이 문제를 풀어냈습니다.) 발표 내용은 크게 네 가지로 구분해서 면접관님게 말씀드리고자 합..

Union-Find Disjoint set (서로 중복되지 않는 부분 집합들로 나눠진 원소 정보를 저장/조작하는 자료구조)을 표현할 때 사용하는 알고리즘으로, 두 node가 같은 집합에 속하는지 판별할 때 유용하게 사용할 수 있다! 구현 1. 초기화 다음과 같이 모든 값이 자기 자신을 가리키도록 초기화해준다! 모든 값이 자기 집합의 대표값?이 되는 것이다. 처음에는 각 집합의 원소가 하나니까 어찌보면 당연한 일이다. int root[1000001]; for(int i=1; i>n>>m; for(int i=0; ioper>>a>>b; if(oper == 0) union_(a, b); else if(find_(a)==find_(b)) cout