티스토리

개발 일지

검색하기

블로그 홈

개발 일지

minari0920.tistory.com/m

minari0920 님의 블로그 입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[프로그래머스] 실패율 (C++) 문제 설명전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담겨 있는 배열을 return 하도록 구현하는 문제이다.(실패율) = (스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수) / (스테이지에 도달한 플레이어 수)주요 로직1. 정렬 알고리즘 사용시간 복잡도가 O(NlogN)인 sort() 메서드를 사용하였다. cmp라는 비교함수를 매개 변수로 넣어 pair 에 대한 내림차순으로 정렬할 수 있도록 하였다. 2. 예외 생각히기원래는 아래와 같이 코드를 작성했었는데 5개의 TC에 대해서 실패가 떴다. 알고보니 num 값이 0이 되는 경우를 배제하여서 Divide.. 공감수 0 댓글수 0 2025. 4. 9.
[백준] 13567번 로봇 (C++) https://www.acmicpc.net/problem/13567 문제 설명(0,0)에서 동쪽을 향해 서있는 상태에서 n개의 명령어가 들어온다,TURN 0 : 왼쪽으로 90도 회전TURN 1 : 오른쪽으로 90도 회전MOVE d : d만큼 이동n개의 명령어를 다 수행한 후에 좌표를 출력하면 된다. 만일 m*m 격자판을 벗어난다면 -1을 출력한다 주요 로직1. 단순 구현이다주의할 점은 왼쪽 상단이 (0,0)이 아니라는 왼쪽 하단이 (0,0)이라는 점이다 정답 코드#include using namespace std;string str;bool flag = true;int m,n,y,x,k,d,ans=-1;int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};bool check(in.. 공감수 0 댓글수 0 2025. 1. 22.
[백준] 2096번 내려가기 (C++) https://www.acmicpc.net/problem/2096문제 설명n개의 줄에 세 개의 숫자가 주어진다. (i,j)가 이동할 수 있는 경로는 (i+1,j-1) 또는 (i+1,j) 또는 (i+1,j+1)로만 가능하다. 첫 줄에서부터 마지막 줄로 이동할 때 얻을 수 있는 최대 점수와 최저 점수를 구하는 문제이 주요 로직1. dp문제이다2. 메모리가 4MB이기 때문에 모든 입력을 다 받고 나서 계산하는 것보다는 입력값 한줄을 받고 나서 그 때 그때 계산해야 한다. 정답 코드#include using namespace std;int n,tmp1, tmp2;int input[4], mn[4], mx[4];int main(){ ios_base::sync_with_stdio(false); cin.tie(NUL.. 공감수 0 댓글수 0 2025. 1. 19.
[백준] 9095번 1,2,3 더하기 https://www.acmicpc.net/problem/9095 문제 설명t개의 테스트 케이스가 주어진다.각 테스트 케이스마다 n이 주어지는데 이때 1,2,3을 가지고 n을 만들 수 있는 경우의 수를 출력하면 된다 주요 로직1. 점화식 찾기 (dp[i] = dp[i-1] + dp[i-2] + dp[i-3]) 정답 코드#include using namespace std;int t,n;int arr[15];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; arr[1] = 1, arr[2] = 2, arr[3] = 4; for(int i=4; i> n; cout 공감수 2 댓글수 0 2025. 1. 14.
[백준] 10026번 적록색약 (C++) https://www.acmicpc.net/problem/10026문제 설명n*n 크기의 배열이 주어진다.각 배열의 칸에는 R,G,B 중 하나의 값이 들어가 있는데, 적록 색약인 경우에는 R과 G를 구분하지 못해 한 색으로 본다. 가로 세로로 연결된 같은 색끼리 모여있는 것들이 적록색약과 적록색약이 아닌 사람이 봤을때 몇개인지 개수를 출력하는 문제이다. 주요 로직1. 그래프 탐색 문제이다dfs로 같은 색이면 계속해서 탐색하도록 코드를 구성했다 정답 코드#include using namespace std;int n;string str;int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};int arr[104][104], brr[104][104], visited[104][104];vo.. 공감수 0 댓글수 0 2025. 1. 13.
[백준] 4863번 섬의 개수 (C++) https://www.acmicpc.net/problem/4963 문제 설명각 테스트 케이스마다 w와 h가 주어진다. w * h 크기의 배열이 주어지는데, 1은 땅을, 0은 바다를 의미한다.땅은 가로, 세로, 대각선으로 움직일 수 있다. 각 테스트 케이스별로 연결된 땅의 개수를 구하는 문제이다.마지막 테스트 케이스이라면 w와 h값으로 0이 주어진다 주요 로직1. 그래프 탐색 문제이다각 테스트 케이스마다 visited배열을 0으로 초기화하고 깊이 우선 탐색으로 배열을 탐색한다 정답 코드#include using namespace std;int w,h, arr[55][55], visited[55][55];int dy[8] = {-1,-1,0,1,1,1,0,-1}, dx[8] = {0,1,1,1,0,-1,-.. 공감수 0 댓글수 0 2025. 1. 12.
[백준] 2230번 수 고르기 (C++) https://www.acmicpc.net/problem/2230 문제 설명n개의 정수로 이루어진 수열이 주어진다.이 수열 중 두 수를 골랐을 때 그 차이가 M이상이면서 제일 작은 경우를 구하는 문제이다. 주요 로직1. 투 포인터수열을 정렬한 다음에 i와 j를 선언해 탐색하면서 최적의 값을 찾아 낸다 2. 최솟값 설정 - 1,000,000,000 정답 코드#include using namespace std;int n,m,x;vector v;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for(int i=0; i> x; v.push_back(x); } sort(v.begin(), v.. 공감수 0 댓글수 0 2025. 1. 5.
[백준] 2661번 좋은 수열 (C++) https://www.acmicpc.net/problem/2661 문제 설명좋은 수열이란 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열을 뜻한다.예를 들어 33, 32121323 은 나쁜 수열이고 32, 32123은 좋은 수열이다.길이가 n인 좋은 수열들을 찾아 그 중 가장 작은 수를 출력한다 주요 로직1. 백트래킹1,2,3 중 숫자 하나씩을 추가하면서 현 상황에서 좋은 수열인지 확인을 하고 아니라면 stop, 맞다면 계속 탐색한다. 2. n의 범위처음에 go(int num, int size)로 num을 string이 아닌 int로 설정했었다. n의 범위가 80이하이기 때문에 80자리의 수까지 탐색할 수 있어야 하는 데 int는 약 20억 범위이기에 10자리까지만 탐색할 수 있다. 그.. 공감수 0 댓글수 0 2025. 1. 4.
[백준] 11660번 구간 합 구하기5 (C++) https://www.acmicpc.net/problem/11660 문제 설명2차원 배열이 주어졌을 때, (y1,x1)부터 (y2,x2)까지의 합을 구하는 문제이다. 주요 로직1. 누적합을 사용하는 것이다.n의 범위가 1024까지이기에 이중 for문을 사용해서 문제를 풀면 시간 초과가 발생한다 i행 j열의 누적합 구하기pfix[i][j]는 1행부터 i행까지, 1열부터 j열까지의 모든 수의 합을 구한 값이다.pfix[i][j] = pfix[i-1][j] + pfix[i][j-1] - pfix[i-1][j-1] + arr[i][j]; (y1,x1)부터 (y2,x2)까지의 합 구하기pfix[y2][x2] - pfix[y1-1][x2] - pfix[y2][x1-1] + pfix[y1-1][x1-1] 정답 코드#.. 공감수 0 댓글수 0 2024. 12. 8.
[백준] 14889번 스타트와 링크 (C++) https://www.acmicpc.net/problem/14889 문제 설명n x n 배열이 주어졌을 때, 두 팀으로 나누어서 두 팀간의 능력치 차가 최소가 되는 경우를 출력하는 문제이다.i번째와 j번째가 같은 팀이 되었을 때 능력치는 S(i,j) + S(j,i)이다. 주요 로직1. 비트 마스킹이다.-> 두 팀을 나누는 모든 경우의 수를 따져야 하므로 비트마스킹으로 경우마다 두 팀의 인원이 같은지 확인하고 능력치를 구하면 된다. 정답 코드#include using namespace std;int n,ret=987654321,arr[24][24];int check(vector v){ int sum = 0; for(int i=0; i> n; for(int i=0; i> arr[i][j]; } } fo.. 공감수 0 댓글수 0 2024. 10. 21.
[백준] 3273번 두 수의 합 (C++) https://www.acmicpc.net/problem/3273 문제 설명n개의 숫자가 주어질 때 이 중 두개의 숫자를 뽑아 합이 x가 되도록 하는 경우가 총 몇 개인지를 출력하는 문제이다. 주요 로직1. 투포인터 문제이다-> n개의 숫자를 받아 정렬한 후, 두 개의 포인터로 탐색한다. 정답 코드#include using namespace std;int n,x,ret;vector v;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0; i> x; v.push_back(x); } cin >> x; sort(v.begin(), v.end()); int low=0, high=n.. 공감수 0 댓글수 0 2024. 10. 18.
[백준] 1644번 소수의 연속 (C++) https://www.acmicpc.net/problem/1644 문제 설명n이 주어질 때, 연속된 소수의 합으로 n이 만들어지는 경우의 수를 찾는 문제이다. 주요 로직1. 소수 찾는 로직-> 에라토스테네스의 체를 통해 소수를 찾는다. 2. 투 포인터로 경우의 수 찾는 로직-> 두개의 포인터인 i,j를 통해 합이 n이 되는 경우의 수를 찾는다. 정답 코드#include using namespace std;int n,ret;bool che[4000004];vector era(int n){ vector v; for(int i=2; i> n; vector v = era(n); int i=0,j=0; while(i 공감수 1 댓글수 2 2024. 10. 16.
[백준] 1931번 회의실 배정 (C++) https://www.acmicpc.net/problem/1931 문제 설명n개의 회의 시작 시간과 회의 끝나는 시간이 주어질 때, 최대로 사용할 수 있는 회의의 최대 개수를 출력하는 문제이다. 주요 로직1. 정렬이다.-> 회의가 끝나는 시간 기준으로 정렬을 해야한다. 정답 코드#include using namespace std;int n, s, e;vector> v;bool cmp(pair a, pair b){ if(a.second == b.second) return a.first > n; for(int i=0; i> s >> e; v.push_back({s,e}); } sort(v.begin(), v.end(), cmp); int cnt = 0; int time = 0; for(auto it .. 공감수 3 댓글수 1 2024. 10. 16.
[백준] 1781번 컵라면 (C++) https://www.acmicpc.net/problem/1781 문제 설명데드라인과 컵라면의 수가 주어졌을 때, 데드라인 내에 문제를 풀면 해당 컵라면을 받을 수 있다받을 수 있는 최대 컵라면의 수를 구하는 문제이다. 주요 로직1. 그리디 문제이기에 우선순위 큐를 통해 풀어야 한다.-> 오름차순의 우선순위 큐를 선언하여 하나씩 넣고 데드라인을 넘어서면 pop()한다. 정답 코드#include using namespace std;int n, d, c;vector> v;priority_queue, greater> pq;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0; i> d.. 공감수 0 댓글수 0 2024. 10. 15.
[백준] 9935번 문자열 폭발 (C++) https://www.acmicpc.net/problem/9935 문제 설명tmp1과 tmp2라는 문자열이 주어진다. 이 때, tmp1에 tmp2라는 문자열이 있으면 tmp1에서 사라진다. tmp1에 tmp2라는 문자열을 없앤 남아 있는 문자열을 출력하는 문제이다. 존재하지 않는 경우엔 "FRULA"라는 문자열을 출력한다. 주요 로직1. 문자열의 substr() 과 erase() 함수를 사용한다.-> tmp1의 i번째 문자가 tmp2의 마지막 문자와 동일한 경우에 substr() 함수로 확인해 tmp2 문자열이 있는 경우 삭제하도록 구현했다. 정답 코드#include using namespace std;char c;string tmp1, tmp2, str;int main(){ ios_base::syn.. 공감수 0 댓글수 0 2024. 10. 15.
[백준] 14729번 칠무해 (C++) https://www.acmicpc.net/problem/14729 문제 설명n개의 성적이 주어질 때, 하위 7명의 성적을 출력한다. 단, 오름차순으로 출력해야 한다. 주요 로직1. 정렬이다-> 단순하게 벡터를 이용해 정렬하는 방법도 있고, 우선순위 큐를 사용해 정렬하는 방법도 있다. 정답 코드- 코드 1 : 단순하게 vector만을 사용해서 정렬한 경우이다.#include using namespace std;int n;double x;vector v; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0; i> x; v.push_back(x); } sort(v.begin().. 공감수 5 댓글수 5 2024. 10. 14.
[백준] 7569번 토마토 (C++) https://www.acmicpc.net/problem/7569문제 설명h개의 n X m의 배열이 주어졌을 때, 토마토가 며칠이 지나면 다 익게 되는지 최소 일수를 구하는 문제이다.익은 토마토는 하루가 지나면 위, 아래, 왼쪽, 오른쪽, 앞, 뒤에 있는 토마토에 영향을 주어 그 토마토를 익게 한다. 주요 로직1. 최소 일수를 구하는 문제이기에 bfs로 풀어야 한다. 정답 코드#include using namespace std;struct A{ int a,b,c;};int n,m,h;vector v;int arr[104][104][104], visited[104][104][104];int dx[6] = {0,0,1,0,0,-1}, dy[6] = {0,1,0,0,-1,0}, dz[6] = {-1,0,0,.. 공감수 3 댓글수 2 2024. 10. 11.
[백준] 7576번 토마토 (C++) https://www.acmicpc.net/problem/7576 문제 설명n X m의 배열이 주어졌을 때, 토마토가 언제쯤 다 익을지 계산하는 문제이다. 익은 토마토는 상하좌우로 영향을 주기에 하루가 지나면 상하좌우에 있는 익지 않은 토마토가 익는다.토마토가 며칠이 지나면 모두 다 익는지, 그 최소 일수를 구하는 문제이다. 주요 로직1. 최소 일수를 구하기 때문에 bfs로 풀어야한다.정답 코드#include using namespace std;int n,m;vector> v;int arr[1004][1004], visited[1004][1004];int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};int main(){ ios_base::sync_with_stdio(false);.. 공감수 4 댓글수 1 2024. 10. 10.
[백준] 2667번 단지번호 붙이기 (C++) https://www.acmicpc.net/problem/2667 문제 설명n x n 배열이 주어졌을 때, 연결된 컴포넌트를 찾는 문제이다. 주요 로직1. 연결된 컴포넌트를 찾는다.-> 리턴타입이 int인 dfs를 사용한다. 정답 코드#include using namespace std;int n,cnt;string str;vector v;int arr[30][30], visited[30][30];int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};int dfs(int y, int x){ int num = 1; visited[y][x] = 1; for(int i=0; i n || nx > n) continue; if(arr[ny][nx] == 0 || visited[ny][n.. 공감수 4 댓글수 1 2024. 10. 9.
[백준] 11724번 연결 요소의 개수 (C++) https://www.acmicpc.net/problem/11724 문제 설명정점의 개수(n)과 간선의 개수(m)이 주어졌을 때 다음 m개의 줄에 간선의 양 끝점이 주어진다. 연결된 컴포넌트의 개수를 구하는 문제이다. 주요 로직1. dfs로 푼다-> 연결된 컴포넌트의 개수를 찾으면 된다. 정답 코드#include using namespace std;int n,m,a,b,ret;int visited[1004];vector arr[1004];void dfs(int a){ visited[a] = 1; for(auto it : arr[a]){ if(visited[it]) continue; dfs(it); }}int main(){ ios_base::sync_with_stdio(false); cin.tie(NU.. 공감수 5 댓글수 4 2024. 10. 8.
[백준] 1743번 음식물 피하기 (C++) https://www.acmicpc.net/problem/1743 문제 설명세로(n), 가로(m), 쓰레기의 개수(k)가 주어질 때 다음 k개의 줄만큼 쓰레기의 위치가 주어진다. 쓰레기 중에서 인접한 가장 큰 쓰레기의 크기를 구하는 문제이다. 주요 로직1. BFS를 사용-> 한 음식물의 위치로부터 상하좌우를 확인해서 쓰레기의 크기를 알아낸다 정답 코드#include using namespace std;int n,m,k,ret,y,x;vector> v;int adj[103][103], visited[103][103];int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};int bfs(int y, int x){ int cnt = 1; queue> q; q.push({y,x}); vis.. 공감수 0 댓글수 0 2024. 10. 8.
[백준] 1260번 DFS와 BFS (C++) https://www.acmicpc.net/problem/1260문제 설명그래프의 정점과 간선이 주어진 경우에 대해서 해당 그래프를 DFS로 탐색한 순서, BFS로 탐색한 순서를 출력하는 문제이다. 주요 로직1. DFS 로직 (수도코드 ver)dfs(int here){ visited[here] = true; for(int there : adj[here]){ if(visited[there]) continue; dfs(there); }}2. BFS 로직 (수도 코드 ver)bfs(int here){ visited[here] = true; q.push(here); while(q.size()){ int a = q.front(); q.pop(); .. 공감수 3 댓글수 1 2024. 10. 7.
[백준] 14469번 소가 길을 건너간 이유 3 (C++) https://www.acmicpc.net/problem/14469 문제 설명n 마리의 소가 주어질 때, 각 소의 도착 시간과 검문 시간이 주어진다.모든 소가 검문을 다 마치는 최소 시간을 구하는 문제이다. 주요 로직1. 도착 시간을 기준으로 소 검문을 시작한다.-> sort() 함수를 사용해 빨리 도착한 순으로 정렬해 검문을 한다. 정답 코드#include using namespace std;int n,a,b;vector> v;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0; i> a >> b; v.push_back({a,b}); } sort(v.begin(), v... 공감수 5 댓글수 1 2024. 9. 27.
[백준] 2109번 순회 강연 (C++) https://www.acmicpc.net/problem/2109 문제 설명대학에서 p만큼의 강연료를 지불할테니 d일 이내에 와서 강연을 해달라는 조건이다.최대한 많은 돈을 벌 수 있게끔 구하는 문제이다. 주요 로직1. 강연료를 기준으로 방문할 대학을 고른다.-> sort() 함수를 이용해 강연료를 내림차순으로 정렬한다. 정답 코드#include using namespace std;int n,d,p,ret;bool arr[10004];vector> v;bool cmp(pair a, pair b){ return a.first > b.first;}int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; f.. 공감수 0 댓글수 0 2024. 9. 25.
[백준] 14405번 피카츄 (C++) https://www.acmicpc.net/problem/14405문제 설명입력받은 문자열이 "pi", "ka", "chu" 이 세 개의 문자열으로 연결되어 있으면 YES 그렇지 않으면 NO를 출력한다. 주요 로직1. 문자열의 특정 부분을 추출하기-> substr()함수를 사용해 문자열의 2~3자리를 추출해 원하는 문자열이 존재하는지 확인한다.정답 코드#include using namespace std;bool flag = true;string str;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> str; for(int i=0; i 공감수 0 댓글수 0 2024. 9. 23.
[백준] 2234번 성곽 (C++) https://www.acmicpc.net/problem/2234 문제 설명 m*n 형태의 숫자를 입력을 받는다.각 숫자는 0에서 15 사이의 숫자로 구성되어 있고, 이 숫자는 벽의 위치를 나타낸다.서쪽에 벽이 있을때 1, 북쪽 에 벽이 있을때 2, 동쪽 에 벽이 있을때 4, 남쪽 에 벽이 있을때 8이 더해져있다.이 성에 있는 방의 개수, 가장 넓은 방의 크기, 하나 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하면 된다.주요 로직1. dfs를 사용해 방의 개수와 각 방의 넓이를 구한다.-> 입력 받은 숫자를 비트마스킹을 통해 벽이 있는 곳은 탐색하지 못하도록 구현한다. 2. 벽 하나를 제거했을 때 얻을 수 있는 가장 넓은 방의 크기를 찾는다.-> visited[][] 배열에 단순히 1,0 으로.. 공감수 0 댓글수 0 2024. 9. 21.
[백준] 1094번 막대 (C++) https://www.acmicpc.net/problem/1094문제 설명64cm짜리 막대기를 반으로 잘라가면서 내가 원하는 길이로 만들려고 한다.이때 조각난 막대기를 붙여 원하는 길이로 만들 때 조각난 막대기 수를 구하는 문제이다. 주요 로직1. 비트 마스킹을 사용해서 푼다.64, 32, 16, 8, 4, 2, 1 이런식으로 줄기 때문에 비트마스킹을 사용해 총 몇 개의 1을 가지고 있는지 확인하면 된다. 정답 코드#include using namespace std;int x, val;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> x; for(int i=0; i 공감수 0 댓글수 0 2024. 9. 21.
[백준] 19942번 다이어트 (C++) https://www.acmicpc.net/problem/19942 문제 설명입력으로 식재료 표가 제공되었을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾는 문제이다. 주요 로직1. 최소 비용을 찾아야 한다.-> 완전탐색을 이용해 모든 집합을 다 찾고 각각의 집합의 경우에 대한 비용을 구한 후 최소 비용을 찾는다2. 최소 비용인 경우의 집합 구하기-> map이라는 자료 구조를 사용해서 모든 집합의 경우를 다 저장해 둔 후, 최소 비용의 경우에 대해서만 정렬을 해서 첫 값을 뽑도록 구현했다. 정답 코드#include using namespace std;struct A{ int a,b,c,d,e;};int n,a,b,c,d,e,ret=987654321;int arr[4];vector v;.. 공감수 4 댓글수 0 2024. 9. 16.
[백준] 15686번 치킨배달 (C++) https://www.acmicpc.net/problem/15686 문제 설명- 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리- 도시의 치킨 거리 : 모든 집의 치킨 거리치킨 집과 집의 위치가 주어질 때, m개의 치킨집을 선택해서 도시의 치킨 거리가 가장 작게 나오는 경우를 골라 출력하기 주요 로직1. 최대 m개의 치킨집을 선택해야 한다.- 조합을 이용해서 m개의 치킨집을 선택해서 vector vList에다가 저장을 해두었다.2. 치킨집과 집의 거리(치킨거리)를 구해서 다 더한 후, 가장 작은 값을 출력해야한다- 집 한 곳과 m개의 치킨집 하나하나를 다 비교해서 최솟값을 구하도록 구현했다.* 조합 코드 (void combi) 는 외워두기 정답 코드#include using namespace std.. 공감수 3 댓글수 1 2024. 9. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.