본문 바로가기

Algorithm🐰96

[백준] 13460 구슬 찾기2 BFS 문제 : www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 분석 : 이 문제는 삼성 어쩌구 역량 기출 문제였다. 아직 기출 문제에 대한 감이 없다. 기업 코딩테스트는 다 기업 코딩테스트 같아서 말이다 하하 어쩼든 그래프 이론을 복습하는 와중에 한번 풀어볼까 ? 해서 도전하게 되었다. 문제를 읽다가 이해가 되면 문제 포기를 못하겠다. input 받는것만 만들고 다른 블로그님들의 글을 참고하여 겨우 겨우 풀었다. .. 2021. 4. 22.

[백준] 2583 영역 구하기 DFS 문제: www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 분석 : 전 2667(단지 번호 붙이기)번와 비슷한 문제이나 주어지는 입력값이 조금 다르다 ! 문제를 보면 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표가 주어지고 이에따라 가지는 값의 범위를 구해 사각형을 1로 초기화 시켜 주었다. 그러면 남은 map의 좌표는 0이 될꺼고 dfs를 돌며 맵의 크기를 구하되 dfs_all로 끊어져 있는 곳들에 대해 반복적으로 수행하면 된다! c++ 코드.. 2021. 4. 22.

[백준] 1697 숨바꼭질 BFS 문제 : www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 분석 : 풀지 못했던 문제를 풀었다 🤭 처음엔 재귀로 접근하다 가까운 거리먼저 탐색 해야 한다는 것을 깨달았다. 최단 거리를 찾는 bfs 문제이므로 queue를 사용했고 수빈이의 움직임 moving 배열에 넣은 뒤 visit에 움직인 거리만큼을 +1 해줘서 누적시켰다. 그리고 k에 도달했을 때 누적된 값을 출력시키면 끝!! c++ 코드 : // // 1697_hide_seek.. 2021. 4. 21.

[백준] 9012 괄호 string 문제 : www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 분석: 유제를 본 적이 있어 어떻게 접근하면 효율적일까 고민하던 중 stack으로 푼 방식이 획기적이었다!! c++ 코드 : // // bracket.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/04/21. // #include #include #include using namespace std; int N; bool isBr.. 2021. 4. 21.

[백준] 1110 더하기 사이클 string 문제 : www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 분석 : 도움 없이 풀 수 있는거 보니 내 수준은 브론즈인가보다 ... 앞으로 더 발전해야지 주어진 예시만으로 조건을 생각한다면 규칙을 발견해 풀수 있는 문제였다. 풀이 : // // 1110_addCycle.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/04/21. // #include #include #include using namespa.. 2021. 4. 21.

[백준] 2309 일곱 난쟁이 backtracking 문제 : www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 분석 : 브론즈였음에도 어려웠다.. 앞으로 브루트 포스, 백트래킹쪽을 좀 더 공부해 보아야겠다. 종만북에서 보았던 아이디어를 가지고 문제 접근을 하였다. 각 난쟁이들은 100을 포함하는데 속하거나 안 속하거나 둘중 하나이다. 그러므로 모든 난쟁이들을 탐색하는데 return 문을 만나 재귀가 끝나게 되면 visit를 false로 해 속하지 않게끔 만들고 다른 원소들을 탐색하는 것이다. 이렇게 하여 속하는 원소들만.. 2021. 4. 6.

[백준] 1477 휴게소 세우기 문제 : www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 분석 : 풀땐 몰랐는데 예전 라우터 문제와 비슷한 방식의 문제다!! 생각한 틀린 방법 : for문을 한번씩 돌때마다 가장 간격이 큰 휴게소 지점을 반으로 나눠 그 지점에 휴게소를 세운다. // // 1477_rest.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/04/05. // #include #include #include #i.. 2021. 4. 5.

[백준] 치즈 2636 bfs 문제 : www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 분석 : 이 문제는 생각하기 복잡했지만 코드를 보니 단숨에 이해가 가는 듯 한 문제였다. 치즈의 겉면만 시간에 따라 어떻게 공기로 바꿀까 문제 그대로의 흐름을 따라 문제를 풀려 했지만 그렇게 되면은 안쪽의 공기와 바깥쪽의 공기가 구분이 되지 않아 순서가 엉망이 될 수도 있을 것 같았다. 같이 스터디 하는 언니의 코드 설명으로 치즈 입장에서가 아닌 공기 입장에서 다음 공기가 될 것인지 아닌지 판단하면 안쪽의 공기를 생각하지.. 2021. 4. 2.

[백준] 14502 연구소 bfs 문제 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 분석 : c++ 코드 : // // 14502_lab.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/02/07. // #include #include #include #include #include #include #include using namespace std; int arr[8][8]; int c_arr[8][8]; int N, M; int zero_cnt; in.. 2021. 4. 1.

[백준] 11779 최소 비용 구하기2 dijkstra 문제 : www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 분석 : 이번 문제는 전 문제 1916번 2021.03.10 - [Algorithm🐰/백준] - [백준] 1916 최소비용 구하기 dijkstra 에 거쳐간 노드를 출력할 수 있도록 추가하는 작업이 필요하다. 따라서 while 문 안 for 문에 t 배열을 하나 추가해 그 전 노드를 인덱스 값으로 현재 노드의 값을 넣어주고 그 전 pop해온 노드(now)를 값으로 받도록.. 2021. 3. 10.

[백준] 1916 최소비용 구하기 dijkstra 문제 : www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 분석 : 이 문제 역시 대표적인 다익스트라 알고리즘 문제이다. 1753번 문제 2021.03.10 - [Algorithm🐰/백준] - [백준] 1753 최단 경로 dijkstra 에 가는 마지막 노드 end 만을 출력하게끔 변형하면 된다. c++ 코드 : // // 1916_min_cost.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong o.. 2021. 3. 10.

[백준] 1753 최단 경로 dijkstra 문제 : www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 분석 : 대표적인 다익스트라 알고리즘 문제이다. 다익스트라의 방향 그래프를 구현하기 위해서 배열 또는 우선순위 큐 자료구조를 사용한다. 배열로 사용 할 시 시작 노드와 끝나는 노드의 가중치를 넣기 위해 int v[in][to] = w 와 같이 사용해야 하는데 문제의 배열의 범위가 20000이라 시간 초과가 나 사용이 불가능 했다. 이는 모든 노드들에 대해 for문을 돌면서 또.. 2021. 3. 10.

[백준] 12865 평범한 배낭 knapsack 알고리즘 문제 : www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 분석 : 이 문제는 knapsack 알고리즘의 대표적인 문제이다. 🍙 knapsack 알고리즘 무게와 가치가 따로 있고 최대 가치를 구하는 문제 greedy론 최대 가치를 보장 할 수 없기 때문에 DP로 접근해야 한다. D[i][j] - j 만큼의 무게를 가진 i번째까지 물건들의 가치 V[i] - i 번째 물건의 가치 W[i] - i번째.. 2021. 3. 9.

[백준] 11000 강의실 배정 priority-queue, greedy 문제 : www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 분석 : 이 문제는 언뜻 보면 19598번 최소 회의실 개수 문제와 비슷해 보인다. 하지만 N의 범위가 200,000d으로 O(N^2)으로 풀면 시간 초과가 발생한다 😢 그래서 자동으로 강의 끝나는 시간이 짧은 친구 순으로 검색할 수 있게끔 우선순위 큐를 이용하였다. (처음 써본다 .. 하하) 우선 순위큐는 자료형 T, Container, 사용자 정의 비교 연산(struct, class - operator 연산자) 이 3가지를 정의해 줘야 하고 pq.. 2021. 3. 7.

[백준] 10974 모든 순열 백트래킹 문제 : www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 분석 : 사실 전혀 이해가 되지 않아서 블로그들을 참고하여 풀었다. dfs가 백트래킹이랑 관련이 깊다 했는데 이 문제가 바로 백트래킹 알고리즘 사용하는 고전적인 문제라고 한다. c++ 에선 next_permutation이라는 순열 찾는 함수가 에 있다고 한다. 이걸 이용하면 쉽게 풀 수 있을 것 같다. 하지만 백트랙킹 연습을 위해 백트랙킹 방식으로 완전 탐색 문제를 풀어보았다. dfs와 마찬가지로 visit (방문했는지 안했는지 검사하는 배열)이 필요로 된다. v vector에 넣어주는데 방.. 2021. 2. 27.

[백준] 2617 구슬 찾기 DFS 문제 : www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 분석 : 이 문제는 배열을 두개로 나눠서 쓸 생각을 못해서 배열을 어떻게 담아야 하는지 타입에 관해 고민이 많았다. 심지어 내가 잘 못쓰는 재귀함수까지 사용해서 감 잡기가 어려웠다 😅 문제에서 원하는 것은 무게가 중간이 될 수 없는 구슬의 수를 찾으라고 한다. 중간이 될 수 없으려면 각각 담은 light, heavy vector에 인접한 노드들이 많이 담겨 비교가 많이 되어야 한다. .. 2021. 2. 26.

[백준] 2003 수들의 합2 투 포인터 문제 : www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 분석 : 투 포인터란 1차원 배열에 대해 포인터를 양 끝단에 두고 값을 찾는 방식을 말한다. 조건(m)에 해당 되는 값을 찾으면 cnt를 증가 m 보다 작은 값이면 end 인덱스 위치의 값을 sum에 저장하고 end 하나 증가 m 보다 큰 값이면 start 인덱스의 값을 빼고 start를 하나 증가시킴 c++ 코드 : // // 2003_sum2.cpp // S.. 2021. 2. 26.

[프로그래머스] 두 개 뽑아서 더하기 문제 : programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 분석 : input vector : numbers output vector : answer ex> input output [2,1,3,4,1] [2,3,4,5,6,7] [5,0,2,7] [2,5,7,9,12] 가 주어질 때 첫번째 for 문 : inter 는 반복할 간격이다. 1 ~ size-1 범위를 가진다. 두번째 .. 2021. 2. 26.

[프로그래머스] 크레인 인형 뽑기 2019 카카오 개발자 겨울 인턴쉽 🎯 문제 : programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 🧩분석 : 2년전에 만났던 문제 ..! 지금은 코드 이해가 다행이 되었다. 약간의 블로그들을 참고했지만 2차원 board = vector board 크레인의 움직임 = vector moves 1. 크레인의 움직임이 끝날때 까지 check 할 인덱스를 -1하여 접근 2. borad의 한 행씩 검사하면서 움직일 열(check 인덱스 값)이 빈칸(0)이 아니면 stack에 쌓인 값이 없으면 pu.. 2021. 2. 24.

[프로그래머스] 2016년 basic 문제 : programmers.co.kr/learn/courses/30/lessons/12901? 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 분석 : 윤년과 7월에서 8월로 넘어갈 시 홀수 짝수 계산을 달리 해준다. c++ 풀이 : #include #include #include using namespace std; string solution(int a, int b) { string answer = ""; int sum = 0; //int day = {31, 29.. 2021. 2. 24.

이전 1 2 3 4 5 다음

티스토리툴바