https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 핵심 bfs를 안다면 매우 쉽게 풀 수 있는 문제이다. 기존에 다루었던 네 방향에서 조금 응용된 느낌이다. 하지만 똑같은 방식으로 풀 수 있다. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { ..
https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 문자열 배열이 들어오는데, 문자열의 첫 시작이 (I 숫자) 라면 큐에 숫자를 삽입하고, (D 1)이 들어오면 제일 큰 수를 삭제한다. (D -1) 일 경우 가장 작은 수를 삭제해야 한다. 핵심 큐에서 삭제순서를 정할 수 있지만, 중간에 바꿀 수는 없다. 따라서 우선순위 큐를 2개를 선언하여 사용하면 쉽게 풀 수 있다. 정답 코드 import java.util.Collections; im..
https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 문자열이 들어오고 그 문자열을 가지고 만들 수 있는 소수의 수를 찾는 것이다. 예를 들어 "17" 이 들어오면 만들 수 있는 수는 1, 7, 17, 71이 되고 소수는 7, 17, 71이므로 3개이다. 핵심 우선 완전탐색(bfs)을 사용하여 가능한 모든 경우를 찾는다. 이후 소수를 판별해야 하는데 에라스토테네스의 체를 사용하면 된다. 에라스토테네스의 체를 예전에도 설명한 적이 있는데, ..
https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 정렬 문제이다. 입력으로 int 배열이 들어오는데, 이때 이 배열을 조합해서 가장 큰 수를 만들면 되는 간단한 문제이다. 핵심 정렬 조건을 재정의하여 우리가 원하는 조건으로 정렬시키는 것이 중요하다. 정답 코드 import java.util.Arrays; import java.util.Comparator; class Solution { public String solution(int[]..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 이 문제를 해석해 보면, 육지에서 갈 수 있는 끝지점과 끝지점사이의 거리를 구하는 것이다. 단 이동할 때, 가장 빠른 방법으로 간다 즉 BFS를 사용하라는 것이다. 바로 풀어보자. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main{ static int[][] result; stat..
https://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 핵심 백트래킹을 사용하여 풀면 시간초과가 뜨게 된다. 따라서 이 문제는 DP를 사용해야 한다. 우선 물건 1개를 넣을 때 각 무게당 최대 가치는 어떻게 구할 수 있을까? 당연하게도 위와 같다. 1~5에는 6의 무게를 넣을 수 없기 때문이다. 저 자리에 0이 들어가는 것이 맞을까? 당연하게도 6이 들어가는 게 맞다. 3의 가치를 넣을..
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 핵심 이 문제는 LCS와 dp를 이용하여 풀 수 있다. 문자열 2개를 비교해 가며, 아래 테이블을 채워나간다. 만약 첫 줄에서 해당 문자가 다르면 0 같으면 1을 넣어준다. 이후 값은 이전의 값을 이어서 갖게 된다. 이후 다시 값을 비교하면 첫 번째에 1이 들어가고 두 번째도 1이 들어갈 것이다. 이후에 A와 A가 다시 겹치게 되는데, 무작정 1을 ..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 위 트리는 식 (9/(6-4))*3을 이진트리로 표현한 것이고 이를 계산한 값을 출력하면 된다. 사람들은 사칙 연산을 할 때(9/(6-4))*3식과 같은 중위 표기식으로 계산을 한다. 하지만 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위 표기식으로 변환해 계산해야 한다. 즉 (9/(64))*3 → 964-/3*으로 변환되고 이를 계산한다. 따라서 해당 문제에서는 트리를 입력받고 후위 순..
비트마스크란? - 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. - 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. - 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말한다. - 8 bits = 1byte 비트마스크를 사용하면 다음과 같은 이점을 얻을 수 있다. 수행시간이 빠르다. 코드가 짧다 메모리 사용량이 더 적다. 비트 연산자 AND연산 (&) 대응하는 두 비트가 모두 1일 때, 1을 반환 1010 & 1111 = 1010 OR연산(|) 대응하는 두비트가 모두 1 또는 둘 중 하나라도 1이면, 1을 반환 1010 | 1111 = 1111..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 핵심 이 문제는 DFS를 이용하면 쉽게 풀 수 있다. 또한 알파벳을 이미 방문했는지 판단해야 한다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int..
