본문 바로가기

알고리즘 문제풀이/추천 문제

(54)

[ 프로그래머스 Lv2] 멀쩡한 사각형 (Javascript) https://school.programmers.co.kr/learn/courses/30/lessons/62048 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제의 핵심은 최대공약수를 사용하는 것이다. 왜 최대공약수를 사용해야 하는지 그 이유를 살펴보자. 이 문제를 이해하기 위해서는 닮음비의 개념을 알아야 한다. 문제에서 사각형만 다루므로 사각형으로 예시를 들겠다. 닮음비란 두 도형이 닮음일 때, 거기서 대응하는 변의 길이의 비를 말한다. 좀 쉽게 말하면 가로, 세로 길이에 n을 곱한 것을 말한다. n을 곱함으로써 도형이 n배 커질 수 있고, 반대..

[ 백준 3197 ] 백조의 호수 (C++) https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 효율성을 고려해야 하는 문제다. 푸는데 꽤 오래 걸렸다... 문제를 읽어보면 알겠지만 얼핏 보면 어려운 문제로 보이지 않는다. 그냥 bfs 또는 dfs를 계속 사용하면 테스트 케이스는 통과한다. 그런데 그렇게 풀면 무조건 시간초과에 걸릴 것이다. 이 문제는 단 한번의 bfs로 해결해야 하는 문제다. 전체적인 알고리즘은 '경로탐색 -> 얼음 녹이기'를 반복하면 된다. 그..

[ 백준 2933 ] 미네랄 (C++) https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 내 수준에서는 좀 어려운 문제였다. 단순 구현 문제긴 하지만 머리를 좀 써야 한다. 우선 큰 그림부터 그려보자. 문제를 풀기 위한 큰그림과 사용하는 변수는 아래와 같다. 1. 막대기로 미네랄 캔다 2. 붕 뜬 클러스터가 있으면 내려준다 char map[101][101] -> 입력값 저장 int visit[101][101] -> 방문 배열 (dfs에서 사용) int sticks[100] -> 막대기 배열 int ..

[ 백준 11559 ] Puyo Puyo (C++) https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net dfs를 이용한 재밌는 구현 문제였다. 규칙을 만들고 그대로 구현하기만 하면 되는 문제라 크게 설명할 것은 없다. 인접한 동일 색깔의 개수를 count라고 했을때, dfs 결과 count가 4 이상인 것은 map에서 삭제해주고 붕 떠 있는 것을 아래로 내려주면 된다. 말로 하면 좀 헷갈리니 사진으로 확인하자. 아래는 문제의 테스트 케이스를 돌렸을때 첫 번째 연쇄 과정이다...

[ 백준 8911 ] 거북이 (C++) https://www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 단순 구현 문제다. Turtle 이라는 클래스를 만들어서 풀었다. 정답으로 출력해야 하는 직사각형의 넓이는 거북이의 이동경로에서 가로/세로 최대/최소값의 차이를 곱하면 된다. 문제에서 주어진 네 개의 함수는 그대로 구현했고, 여기에 init() 라는 함수를 추가했다. 이 함수는 거북이가 이동할때마다 x, y의 최대 최소값을 초기화해주는 함수다. 문제가 어렵지 않으므로 바로 정답 코드... #include #..

[ 백준 16113 ] 시그널 (C++) https://www.acmicpc.net/problem/16113 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 www.acmicpc.net 단순 구현 문제. dfs로 약간 꼼수를 썼다. 0행만 탐색하면서 검은색 칸을 만나면 연속된 검은색 칸의 개수를 구해 경우의 수를 나눴다. 0~9 까지의 숫자는 몇 개의 칸을 칠하는지로 분류할 수 있다. 아래 그림을 참고하자. 5칸 → 1 7칸 → 7 9칸 → 4 11칸 → 2, 3, 5 12칸 → 0, 6, 9 13칸 → 8 모든 숫자는 0행부터 시작한다. 따라서 (0행, 0열)부터 (..

[ 백준 2290 ] LCD Test (C++) https://www.acmicpc.net/problem/2290 2290번: LCD Test 첫째 줄에 두 개의 정수 s와 n이 들어온다. (1 ≤ s ≤ 10, 0 ≤ n ≤ 9,999,999,999)이다. n은 LCD 모니터에 나타내야 할 수 이며, s는 크기이다. www.acmicpc.net 단순 구현 문제. 한 번쯤 풀어보면 나중에 비슷한 문제를 만났을 때 훨씬 수월하게 풀 수 있는 유형의 문제라고 생각한다. 우선 0 ~ 9 까지 lcd 판에 그리는 규칙부터 정의하자. 나는 아래와 같이 정의했다. 0 ~ 9 까지 각 숫자마다 출력해줘야 하는 번호를 배열로 나타내면 아래와 같다. int rules[10][7] = { {1,1,1,1,1,1,0}, // 0 {0,1,1,0,0,0,0}, // 1 {..

[ 백준 16506 ] CPU (C++) https://www.acmicpc.net/problem/16506 16506번: CPU 디지털하드웨어설계 과목의 최종 프로젝트는 16-bit CPU를 설계하고 Verilog 언어로 구현하는 것이다. 본인이 구현한 CPU가 제대로 동작하는지 테스트하기 위해서는 기계어 코드를 입력으로 주어야 www.acmicpc.net 단순 구현 문제라 그냥 풀면 된다. 풀이 방법은 수없이 많을 것으로 생각된다. 나는 이 문제를 두 가지 함수를 이용해서 풀었다. 첫째로, 십진수를 이진수로 변환하는 함수가 필요하다. 이 과정에서 원하는 비트수만큼 0으로 채워주야 한다. 함수 입력값은 십진수 num과 비트수 크기에 해당하는 range다. 십진수를 이진수로 변환하는 알고리즘은 계속 2로 나눈 다음에 나머지를 더해주면 된다. /..

이전 1 2 3 4 ··· 7 다음

티스토리툴바