[프로그래머스] 1단계 - 과일 장수
2023. 12. 22. 20:58
Algorithm Study
문제 설명 과일 장수가 사과를 한 상자에 m개씩 담아 포장하고 있고, 상자에 담긴 사과 중 가장 낮은 점수가 p인 경우 사과 한 상자의 가격은 p * m이다 과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익은? (사과는 상자 단위로만 판매하며, 남는 사과는 버림) https://school.programmers.co.kr/learn/courses/30/lessons/135808 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 우선 사과 벡터를 오름차순으로 정렬을 한다 이후 for문을 돌며 사과의 가격이 제일 큰 순으로(즉, ..
[프로그래머스] 0단계 - 안전지대
2023. 12. 22. 19:25
Algorithm Study
문제 설명 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류할 때, 안전한 지역의 칸 수를 return https://school.programmers.co.kr/learn/courses/30/lessons/120866 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 우선 지역의 상, 하, 좌, 우, 대각선 총 8칸에 대한 배열 dy, dx를 생성한다 이중 for문을 돌며, 지뢰가 있는 지역이면 상, 하, 좌, 우, 대각선을 모두 위험 지역으로 -1로 표시해준다 이때, 상, 하, 좌, 우가 board의 ..
[프로그래머스] 0단계 - 겹치는 선분의 길이
2023. 12. 22. 18:09
Algorithm Study
문제 설명 선분 3개가 평행하게 놓여있을때, 두 개 이상의 선분이 겹치는 부분의 길이를 return https://school.programmers.co.kr/learn/courses/30/lessons/120876?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 선분이 그려지는 구간을 담는 배열 line[201]을 선언한다 이때 선분의 구간은 -100부터 100까지이지만 배열은 음수 인덱스를 가질 수 없으니 구간에서 100을 더한 값을 인덱스로 가진다 벡터를 돌면서 해당하는 구간에 +1을 한다 이때 선분이 겹쳐야하므로,..
[프로그래머스] 0단계 - 평행
2023. 12. 20. 19:30
Algorithm Study
문제 설명 4개의 점이 주어졌고, 점을 2개씩 이었을 때 두 직선이 평행이 되는 경우가 있으면 1 아니면 0을 return https://school.programmers.co.kr/learn/courses/30/lessons/120875 문제 풀이법 총 3가지 경우의 수가 주어진다 1. 0번째와 1번째, 2번째와 3번째를 이었을 때 2. 0번째와 2번째, 1번째와 3번째를 이었을 때 3. 0번째와 3번째, 1번째와 2번째를 이었을 때 평행인지 아닌지는 기울기를 통해서 알 수 있다 기울기가 같으면 평행이다 기울기는 "세로 / 가로"로 구한다 단순히 저 3개의 경우를 다 나열하면서 풀어도 되지만, 뭔가 for문을 가지고 풀고싶었다 따라서 list[3][4]라는 배열을 두어 for문을 3번씩 돌면서 각 기울..
[프로그래머스] 0단계 - 옹알이(1)
2023. 12. 20. 18:29
Algorithm Study
종강하고 너무 오랜만에 다시 푸는 알고리즘!! 다 까먹었지만 다시 처음부터 풀어봅시다~~~ 문제 설명 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩만 사용한 발음밖에 하지 못하는 조카가 발음할 수 있는 단어의 개수를 return https://school.programmers.co.kr/learn/courses/30/lessons/120956 문제 풀이법 우선 발음 가능한 단어들을 배열로 담아둔다 babbling[i]에서 발음이 가능한 단어의 총 길이 수를 담기 위한 변수 len 선언 babbling[i]의 총 길이인 변수 total_size 선언 발음은 최대 한 번씩만 사용 가능하니, 각 발음에 대하여 몇 번 사용했는지 알 수 있는 배열 used[4] 선언 해준다 이중 fo..
[백준] 10026 적록색약
2023. 3. 17. 19:23
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 적록색약이 아닌 사람이 보는 그림의 구역의 수와 적록색약인 사람이 보는 그림의 구역의 수를 구하기 문제 풀이법 모든 정점을 방문하는 문제이므로 dfs, bfs 모두 사용할 수 있다 그림을 입력 받으면서 R, G, B를 각각 다른 수로 대입하여 배열 arr를 만들어준다 여기서 나는 R을 1, G를 2, B를 3으로 넣어주었다 적록색약이 아닌 경우 R구역의 수를 담는 변수 r, G구..
[백준] 7562 나이트의 이동
2023. 3. 13. 20:00
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 체스판 위에 한 나이트가 놓여져있고, 나이트가 한 번에 이동할 수 있는 칸이 주어졌을 때 나이트는 몇 번 움직이면 해당 칸으로 이동할 수 있을지 구하기 문제 풀이법 최단 거리를 찾는 문제이므로 bfs를 사용하여 문제를 풀 수 있다 백준 1697번 숨바꼭질과 비슷한 문제로, 1차원인 숨바꼭질 문제와 달리 2차원인것만 다르다 우선 나이트는 움질일 수 있는 범위가 다음과 같다 (-2, -1),..
[백준] 1012 유기농 배추
2023. 3. 13. 19:32
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 배추가 심어져있는 곳은 1, 배추가 심어져 있지 않은 곳은 0으로 표시가 되어있는 땅이 있다 배추흰지렁이는 배추를 해충으로부터 보호하고, 인접해있는 다른 배추로도 이동할 수 있다 이따 필요한 총 지렁이의 개수 구하기 문제 풀이법 배추흰지렁이의 개수를 구한다는 뜻은, 배추가 이어져서 심어져있는 곳의 개수를 구하라는 말과 같다 모든 지점을 방문하는 문제이기에 bfs, dfs 모두 사용하여 문제를 풀 수..
[백준] 2667 단지번호붙이기
2023. 3. 13. 17:33
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 집이 있으면 1, 없으면 0을 나타내는 정사각형 모양의 지도가 있을 때, 연결된 집의 모임인 단지를 정의하고 단지에 번호를 붙이려한다 단지수와, 각 단지내 집의 수를 오름차순으로 정렬하기 문제 풀이법 모든 정점을 방문하는 문제이기에 dfs와 bfs 둘 다 사용할 수 있다 지도의 요소가 1이고 방문하지 않았으면 dfs와 bfs를 돌게된다 이때, 총 단지의 수는 + 1한다 dfs와 bfs를 ..
[백준] 12851 숨바꼭질 2
2023. 3. 10. 19:17
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 수빈이는 점 N(0 k; queue q; fill(arr, arr + 100001, 0); q.push({n, 0}); int min = 0; int cnt = 0; while (!q.empty()) { int x = q.front().first; int time = q.front().second; q.pop(); arr[x] = 1; if (cnt..