본문 바로가기

알고리즘

[프로그래머스] 72415번 - 카드 짝 맞추기 (Java) ⬛ 문제 https://programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr ⬛ 풀이 순열을 이용한 완전탐색(DFS) + BFS 문제였다. 예를 들어 아래와 같이 총 2개의 카드가 주어졌다고 가정했을 때 1번 카드: {0, 0}, {1, 1} 2번 카드: {2, 2}, {3, 3} 생성되는 순열은 아래와 같이 총 8가지이다. 1번 카드 뒤집기 - > 2번 카드 뒤집기 (4가지) {0, 0}, {1, 1}, {2, 2}, {3, 3}.. Algorithm/프로그래머스 2021. 10. 23.
[프로그래머스] 67259번 - 경주로 건설 (Java) ⬛ 문제 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr ⬛ 풀이 BFS 심화 문제였다. 한 칸씩 지나갈 때마다 비용이 증가하지만 방향.. Algorithm/프로그래머스 2021. 10. 23.
[프로그래머스] 60063번 - 블록 이동 (Java) ⬛ 문제 https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr ⬛ 풀이 BFS 심화 문제였다. 기존 BFS 문제들은 좌표 하나를 가지고 탐색을 하지만 이번 문제는 두 좌표를 가지고 탐색을 하는 문제였다. 또한 로봇은 가로 or 세로 타입을 가지기 때문에 방문탐색은 3차원 배열 boolean[2][][]을 통해 관리하였다. visited 배열에서 각 타입별로 체크할 때 두 좌표가 모두 방문을 했을 때만 방문했었다고 판단하고, 하나라도 방문하지 않.. Algorithm/프로그래머스 2021. 10. 7.
[백준] 21611번 - 마법사 상어와 블리자드 (Java) ⬛ 문제 https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net ⬛ 풀이 삼성 SW 역량 테스트 기출 문제이다. 구현량이 많은 시뮬레이션 문제라 풀다가 토나올 뻔 했다... 입력은 2차원 배열이지만 달팽이 모양을 일렬로 펼쳐 1차원으로 생각하고 풀었다. 프로그램 전체 로직은 다음과 같다. 1. 처음에 달팽이 모양으로 input을 탐색하여 map을 1차원 배열로 저장한다. 2. 4방향의 블리자드 인덱스들을 2차원 배열(bzIdx)로 계.. Algorithm/백준 2021. 10. 6.
[백준] 1194번 - 달이 차오른다, 가자 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net ⬛ 풀이 지난번 풀이한 백준 1600번 - 말이 되고픈 원숭이와 유사한 문제였다. 다만 6개의 키 보유 현황을 저장해야하기 때문에 비트마스킹이 추가로 필요했다. 프로그램 전체 로직은 다음과 같다. 1. BFS를 사용하며, 비트마스킹을 통해 현재 키 보유 상태를 관리한다. 2. 최대키 개수는 6개이므로 방문관리를 boolean[64][N][M] 3차원 배열로 .. Algorithm/백준 2021. 10. 6.
[프로그래머스] 64062번 - 징검다리 건너기 (Java) ⬛ 문제 https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr ⬛ 풀이 N은 최대 200,000이고 완전 탐색시 O(N^2)이므로 시간초과가 발생한다. 이전에 푼 무지의 먹방라이브 문제와 매우 비슷하다고 느꼈고 이 역시 우선순위큐를 활용하여 해결하였다. 프로그램 전체 로직은 다음과 같다. 1. 우선순위큐에 int[] {디딤돌 횟수, 인덱스}를 저장하고 디딤돌 횟수로 오름차순 정렬한다. 2. 거리를 저장하는 dist 배열을 선언하고 1로 초기화한다. (dist[i]는 stones[i]까지 필요한 거리, 마지막 도착지도 고려해야하므.. Algorithm/프로그래머스 2021. 9. 24.
[백준] 1600번 - 말이 되고픈 원숭이 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net ⬛ 풀이 BFS와 DP를 접목한 문제이다. 한 번쯤 익혀놓으면 좋은 문제였다. 프로그램 전체 로직은 다음과 같다. 1. 3차원 배열 visited를 사용해 방문 체크와 경로 거리를 저장한다. 2. visited는 [k+1][h][w] 크기로 생성하고 각각 말 이동을 0회~k회 한 H x W 크기의 배열로 볼 수 있다. 3. BFS를 사용해 목적지까지 최단 경로를 찾고 기존.. Algorithm/백준 2021. 9. 16.
[프로그래머스] 42891번 - 무지의 먹방 라이브 (Java) ⬛ 문제 https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr ⬛ 풀이 시간 k와 음식 배열 길이가 크기 때문에 완전탐색 시 시간 초과가 발생한다. 프로그램 전체 로직은 다음과 같다. 1. 음식 인덱스, 양을 저장한 int[]를 우선순위큐에 음식 양 오름차순으로 저장한다. 2. 1 Cycle을 현재 우선순위큐의 크기 즉, 남은 음식수로 생각한다. 3. 1 Cycle은 우선순위큐의 제일 앞 음식의 양(제일 적은 양)만큼 돌릴 수 있다.(=maxCycle) 4. maxCycle 만큼 반복하여 남은시간 k에서 Cycle을 뺀다. 5. 이때 음식 크기만큼 값을 가지는 boolean[]을 사용해.. Algorithm/프로그래머스 2021. 9. 15.
728x90
반응형

티스토리툴바