티스토리

기록을

검색하기

블로그 홈

기록을

hugssy.tistory.com/m

알고리즘, Java 백엔드 기술을 익히고 기록합니다.

구독자: 1

방명록 방문하기

주요 글 목록

다익스트라 - 함께여행 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 11. 18.
C++ 알고리즘 체크리스트 #include using namespace std; bool cmp(int a, int b) { //정렬 //return a > b; if (a > b) return true; else return false; } void vectorPrac(){ //벡터 vector v; v.push_back(0); v.push_back(1); v.push_back(-1); sort(v.begin(), v.end(), cmp); //정렬 함수 사용자 정의 for (int i = 0; i < v.size(); i++) { cout 공감수 0 댓글수 0 2021. 10. 16.
프로그래머스: N개의 최소공배수(C++) https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 최소공배수(LCM), 최대공약수(GCD) 활용 문제이다. #include using namespace std; long long gcd(int a, int b){ long long c; while(b != 0){ c = a % b; a = b; b = c; } return a; } long long lcm(int a, .. 공감수 0 댓글수 0 2021. 10. 6.
백준 1717번: 집합의 표현(C++) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 전형적인 Union-Find 문제이다. 또는 분리 집합 유형이라고 불린다. n이 포함된 집합을 나타내는 정수 배열로 r[n]을 사용하자. 먼저 0부터 n까지, r[n]을 자기 자신으로 초기화한다. 그리고 주어지는 명령에 따라서 union과 find를 구현한다. 0, a, b가 주어지면 a가 속한 곳을 b가 속한 곳으로 수정해준다. 가령, a가 속한 집합이 .. 공감수 0 댓글수 0 2021. 10. 6.
프로그래머스: 뉴스 클러스터링(C++) https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 먼저 map을 이용해서 {특정문자열, 존재하는 개수}의 형태로 주어지는 string에 대하여 map을 만들어준다. (코드에서 makeMap 함수) 만들기 전에, 대소문자는 구분하지 않는다는 조건을 처리하기 위해서 주어지는 문자열을 모두 소문자로 변환한다. 대문자로 변환해도 무관하다. 그리고 공집합인 경우를 처리한다. 교집합의 경우, 비어있는.. 공감수 0 댓글수 0 2021. 10. 6.
프로그래머스: 메뉴 리뉴얼 (C++) 문제 출처: https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 조합, map을 이용해서 풀이할 수 있다. 코스요리를 이루는 메뉴의 개수가 곧 조합으로 뽑아야 할 개수에 해당하기 때문에, 뽑아주고, 2명이상의 사람에게 가장 많이 뽑힌 메뉴들을 개수별로 벡터에 저장하고, 오름차순으로 사전순 정렬을 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23.. 공감수 0 댓글수 0 2021. 8. 22.
프로그래머스: 베스트앨범 (C++) 문제 링크는 아래와 같다. https://www.welcomekakao.com/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 | 프로그래머스 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 play www.welcomekakao.com 두 개의 map을 이용했으며, 하나.. 공감수 0 댓글수 0 2019. 10. 30.
백준 17472번: 다리만들기2 (C++) https://www.acmicpc.net/problem/17472 1. 섬마다 인덱스를 부여한다. (각각의 섬들을 구분한다.) 2. 모든 경우에 다리를 놓아본다.다리를 놓을 수 있는 조건에 맞춰서(길이 2이상) 3. 당연하게도 모든 섬을 최소의 간선으로 연결하는 경우, 간선의 수는 섬의 수 - 1이다. 하지만 다리마다 비용이 다 다르기 때문에, 많은 다리를 적은 비용을 놓고 연결하는 경우가 있을 것이다. 따라서 찾은 다리의 수가 k개라고 하고, 섬의 개수를 N개라고 한다면, 찾은 다리 k개 중에 (N-1개~K개)를 뽑아보고, 섬의 연결상태를 확인해서 모든 섬을 연결할 수 있는 경우에 답을 업데이트 해준다. 123456789101112131415161718192021222324252627282930313.. 공감수 0 댓글수 0 2019. 10. 19.
SWEA 2112: 보호 필름 (C++) https://swexpertacademy.com/main/solvingProblem/solvingProblem.do 0~ 최대 높이까지 조합으로 뽑아준다. 뽑은 row들에 대하여 모든 경우로 A와 B로 바꿔주고 검사하는 작업을 해주면 된다. #include #include using namespace std; int h, w, k, m[14][21], org[14][21], st = 0; bool used[14], findAns = false; vector v; void changeRow(int r, int val) { for (int j = 0; j < w; j++) m[r][j] = val; } void toOrg(int r) { for (int j = 0; j < w; j++) m[r][j] = .. 공감수 0 댓글수 0 2019. 10. 17.
SWEA 5650: 핀볼 게임 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo&categoryId=AWXRF8s6ezEDFAUo&categoryType=CODE 조건에 따라 공의 움직임을 구현해주면 된다. 출발 가능 지점에서 모든 방향으로 공을 출발시켜줬다. 웜홀의 위치는 STL map을 이용해서 기록했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192.. 공감수 0 댓글수 0 2019. 10. 17.
SWEA 1767: 프로세서 연결하기 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf 문제 조건에 따라서 이미 전원이 들어와있는 코어를 제외한 모든 코어를, 모든 경우로 전원을 연결시켜주면서 만족하는 경우를 찾아주면 된다. 다만, DFS를 진행할 때, 어떠 코어에서, 4방향 어디로도 연결할 수 없어도, 전원에 연결하지 않고 다음 코어에 대한 탐색을 이어갈 수 있도록 처리해야한다. 일반적인 백트래킹이나 DFS에 더해서, 어디에도 연결되지 않는 경우 이어서 탐색하도록 구현해주면 된다. 가령 1 2 3 4 의 코어가 있다고 가정하면, 2번이 어디에도 연결될 수 없더라도, 2번을 제외한 1 3 4가 모두 전원이 들어와서, 답안으로.. 공감수 0 댓글수 0 2019. 10. 17.
SWEA 5653:줄기세포배양 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo 영역의 범위가 주어지지 않지만, 안전한 영역으로 잡아줄 수 있다. k의 상한선이 주어지기 때문에. 그에 맞춰서 map을 잡아주고, 불필요한 탐색을 피하기 위해서 좌표 정보를 벡터에 저장해두고, 그 벡터를 이용해서 필요한 곳만 탐색한다. 구조체에는 활성이 지속되는 시간, 활성 시작 시간, 죽는 시간, 상태를 저장한다. 이 정보를 이용해서 다음과 같은 알고리즘을 구현한다. 1. 활성 상태에 있는 세포를 BFS해준다. 한 칸씩만 움직이기 때문에 새로 큐에 삽입하거나 할 필요가 없다. 사전에 필요한만큼 미리 큐에 넣어두고 돌리면 된다. 2. 활성.. 공감수 0 댓글수 0 2019. 10. 16.
SWEA 2117: 홈 방범 서비스 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu BFS를 이용해서 마름모를 만들어주며 탐색했다. 모든 집으로부터 돈을 다 받는 경우보다, 운용 비용이 더 많이 들어가는 순간 탐색을 멈췄다. 속도가 매우 느린데 단축할 수 있는 방법을 생각해봐야겠다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100.. 공감수 0 댓글수 0 2019. 10. 16.
SWEA 2382: 미생물 격리 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl 조건대로 시뮬레이션을 해주면 된다. 이동할 때, 이동한 개체와 앞으로 이동해야 하는 개체가 겹치는 처리를 하기 위해서 임시적으로 이차원 배열을 만들어서 이동할 때 사용했다. 이동 결과를 임시 배열에 저장해두고, 여러 개체가 들어있는 좌표를 처리해준 이후에, 원래의 map에 옮겨준다. 낚시왕, 나무재테크 문제와 비슷한 방식이 사용되었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 공감수 0 댓글수 0 2019. 10. 16.
SWEA 2383: 점심 식사시간 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&categoryId=AV5-BEE6AK0DFAVl&categoryType=CODE 초반에 정보들만 잘 잡아둔다면 DP를 이용해서 쉽게 해결할 수 있다. 먼저, 모든 사람과 모든 계단까지 소요 시간을 미리 저장해둔다. 다음으로 DFS를 이용해서 모든 경우에 대해서, 모든 사람에게 계단을 할당해준다. 이제 0번 계단에 배정된 사람과, 1번 계단에 배정된 사람이 있다. 각각 벡터에 담아서, 계단에 빠르게 도착하는 사람이 앞으로 오도록 정렬해준다. 생각해보면, 계단을 사용하는 사람이 3명 이하라면 아무도 기다리지 않고, 도착하자마자 바로 계단으로.. 공감수 0 댓글수 0 2019. 10. 15.
SWEA 4014: 활주로 건설 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=CODE 백준에 있는 경사로 문제와 동일하다. 행을 확인할 때는 우측으로 증가하는 경우와, 감소하는 경우를 찾고 불가능한 경우는 걸러낸다. 열을 확인할 때는 하단으로 증가, 감소 경우에 대해서 동일하게 검색한다. 이미 경사로를 건설한 곳에 또 경사로를 건설하지 않도록 해야한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758.. 공감수 0 댓글수 0 2019. 10. 15.
SWEA 2105: 디저트 카페 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu 대각선으로 좌표를 이동하도록 DFS를 구현해주면 된다. 그래프 문제를 풀이할 때 접해봤던 유형으로, 노드에서 사용되었던 숫자를 다시 사용하지 않으면서, 출발지점으로 되돌아가는 데에 필요한 이동 횟수를 구해주면 된다. 이 문제에서는 그러한 경우의 최솟값을 구해주면 되겠다. 그리고 사각형을 이루어야 한다는 것을 생각해서 구현해주면 되겟다. 이 부분은 코드의 주석으로 확인할 수 있다. DFS를 진행할 때, 일반적으로 방문했던 지점은 다시 방문하지 않도록 처리한다. 또한, 이 문제의 경우, 시작지점에서 사용했던 숫자는 무조건 사용했다는 처리가 되.. 공감수 0 댓글수 0 2019. 10. 15.
SWEA 5656: 벽돌 깨기 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo 가능한 구슬 투하 횟수만큼 중복 순열을 이용해서 구슬 투하 위치를 구한다. 구슬 투하 위치가 결정되면, BFS를 이용해서 폭탄들이 터지게 해준다. 이후에 중력에 의해서 공중에 있는 박스들이 내려오게 하는 처리는, 큐를 이용해서 바닥부터 빈 공간을 넣어주고, 이동해야할 블럭을 큐의 가장 상단에 있는 지점으로 결정해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656.. 공감수 0 댓글수 0 2019. 10. 14.
SWEA 2115: 벌꿀채취 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE 테스트 케이스 2번의 경우를 잘 처리해야 한다. 그냥 채집할 수 있는 가장 큰 꿀을 그리디하게 채집하게 되면, 7과 5,5 를 비교한다고 했을 때, 이윤이 5 두개를 채집했을 경우 더 크기 때문에, 결국 모든 경우에 대해서 이윤을 비교하기 위해 완전탐색이 필요함을 알 수 있다. 일단 사람이 1명이라고 생각하고, 조건에 따라 채집할 수 있는 벌꿀의 위치별 최대 이윤을 시작 지점과 함께 벡터에 저장했다. 이후에 그 벡터에서 두 개를 골라서 (두명이 채집하니까) .. 공감수 0 댓글수 0 2019. 10. 14.
SWEA 1953: 탈주범 검거 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE 통로를 통해서 이동을 하는데, 현재의 통로에서 목적지의 통로로 이동할 수 있는지 확인해가며 BFS를 구현해주면 된다. BFS의 특성상 가까운 지점을 무조건 먼저 방문하게 되므로, 임계 거리를 방문하는 순간 BFS를 종료해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686.. 공감수 0 댓글수 0 2019. 10. 13.
SWEA 5644: 무선 충전 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE 문제에서, 행과 열을 기존에 사용하던 방식과 다르게 사용하고 있기 때문에, 기존에 익숙한 방식으로 바꿔주었다. 남쪽으로 갈수록 행이 증가하고, 동쪽으로 가면 열이 증가하는 방식으로. 그리고 2차원 배열 안에 pair 벡터를 담았다. 벡터로 담은 이유는, 특정 지점에서 충전기 여러개의 영향을 받을 수 있기 때문이다. 그리고 벡터를 pair로 받은 이유는 충전세기와 함께 어떤 충전기의 영향을 받는지 확인할 수 있어야, 중복 충전때 충전 값 조절해주는 처리를 할 .. 공감수 0 댓글수 0 2019. 10. 9.
SWEA 4008번: 숫자 만들기 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE 사용할 수 있는 연산자의 개수를 하나씩 감소시켜보면서 DFS를 수행해주면된다. 사용중 처리를 연산자의 수를 조절해줌으로써 해준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include#include#i.. 공감수 0 댓글수 0 2019. 10. 8.
[오답] SWEA 4008: 숫자 만들기 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE 연산자의 수가 가령 1,5,0,3 이렇게 주어지면 나는 새로운 벡터에 0을 1개, 1을 5개, 3을 3개 추가하고, 그 백터를 이용해서 순열을 돌렸다. 이 과정에서 중복도 발생하고, set을 사용해서 중복을 처리해주더라도 연산 시간이 소모되기 때문에 시간초과가 나는 것 같다. 따라서, 그냥 1,5,0,3 상태에서, 내가 무언가를 뽑으면 그 원소에 1을 더하거나 빼주고, 양수일 경우에만 뽑을 수 있게 하는 방식으로 DFS를 구현해야 통과할 수 있을 것 같다. .. 공감수 0 댓글수 0 2019. 10. 8.
퀵, 머지, 힙 정렬 알고리즘 간단 정리 퀵소트: 평균 nlogn, 최악 n^2(데이터가 이미 거의 정렬되어 있는 경우) 머지소트: 평균: nlogn보장단점: 메모리 비효율적이라는 문제-> 힙소트로 해결 힙소트:일단 데이터를 가지고 힙구조를 만들어야함. 이 부분의 복잡도 == NlogN그리고, 루트의 값을 맨 뒤로 보내면서, 보낸 값을 제외하고 다시 힙을 만드는 비용이 logN. 이걸 N번 반복하니까 NlogN결국 합치면 총 시간 복잡도는 NlogN이 된다.장점: 메모리 효율적. 공감수 0 댓글수 0 2019. 10. 6.
SWEA 1952: 수영장 (C++) 모든 경우에 대해서 완전 탐색을 해주면 된다. 결정하는 달에 이용 내역이 없으면 비용 추가 없이(이용권 구매 없이) 다음 달로 넘어간다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include#define INF 987654321;using namespace std; int price[4], plan[15], Min = INF; void dfs(int month, int fee) { if (month >= 12) { if (fee > T; for (int tc = 1; tc price[i]; // 1일, 1달, 3달 1년 for (int i = 1; i > plan[i]; if (Min.. 공감수 1 댓글수 0 2019. 10. 4.
SWEA 4013번: 특이한 자석 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH&categoryId=AWIeV9sKkcoDFAVH&categoryType=CODE 백준에 있는 톱니바퀴 문제와 동일한 문제이다. 회전에 대한 구현은 다른 자석과 인접한 위치의 인덱스를 조절하는 것으로 처리할 것이다. 12시 방향의 인덱스를 0이라고 하면, 시계 방향으로 극들이 0~7의 인덱스를 가지고 주어진다. 초기에 왼쪽의 인덱스는 6, 오른쪽의 인덱스는 2, 12시 방향의 인덱스는 0이다. 가령 1번 톱니를 회전하면서 2번 톱니의 움직임을 확인한다고 하면, 1번의 right와 2번의 left를 비교해서 2번의 회전 여부를 결정해주는 방.. 공감수 0 댓글수 0 2019. 10. 3.
SWEA 4012번: 요리사 (C++) https://swexpertacademy.com/main/code/problem/problemList.do?problemTitle=SW&orderBy=PASS_RATE&select-1=&pageSize=10&pageIndex=1#none 음식 하나에 들어가는 재료는 n/2개이다. 조합을 이용해서 음식 하나에 들어갈 수 있는 재료를 뽑는다. 여기서 뽑힌 재료가 음식 하나에 들어가는 재료가 되는 것이고, 뽑히지 않은 재료는 나머지 음식에 들어가는 재료가 된다. 뽑은 재료들 사이에 시너지를 계산하기 위해서, 순열로 2개를 뽑는다. 나머지 음식에 대해서도 시너지를 계산해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142.. 공감수 0 댓글수 0 2019. 10. 3.
백준 17471번: 게리맨더링 (C++) https://www.acmicpc.net/problem/17471 선거구가 형성될 수 있는 조건은 선거구에 구역이 1개 이상 포함되는 것이다. 따라서 조합을 이용해서, 주어지는 n개의 구역 중에서 1개 이상 뽑는 경우에 대해서 처리해주면 된다. 단, n개를 뽑게 되면, 다른 선거구에 속하는 구역이 0개가 된다는 의미이므로 n개 뽑는 경우는 제외해준다. 구역을 적절하게 뽑았다면 다음과 같은 처리를 해준다. 우선 n 공감수 0 댓글수 0 2019. 10. 2.
프로그래머스: 단어 변환 (C++) https://www.welcomekakao.com/learn/courses/30/lessons/43163 단어의 철자를 바꿔가면서 목록에 있는 단어들 사이에서 차례로 변화가 일어날 수 있다는 것을 이용해서 인접행렬을 만들어준다. 초기 시작지점을 찾을 때, 단어를 바꾸고 시작하냐, 수정 없이 시작하냐를 따져준다. 목적 단어가 목록에 없으면 BFS를 수행할 필요도 없이 0을 반환해준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include #include #include#inclu.. 공감수 0 댓글수 0 2019. 9. 29.
프로그래머스: 네트워크 (C++) https://www.welcomekakao.com/learn/courses/30/lessons/43162 DFS혹은 BFS를 활용해서 연결되어 있는 정점들의 집합의 수가 몇개인지 구해주면 된다. 12345678910111213141516171819202122232425262728#include #include using namespace std;bool vis[201];void dfs(int here, vector &grp) { vis[here] = true; for (int i = 0; i 공감수 0 댓글수 0 2019. 9. 28.

문의안내

티스토리
로그인
고객센터

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