문제 https://school.programmers.co.kr/learn/courses/30/lessons/181893 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 인덱스가 헷갈려서 노트에 적어가며 풀었다. 접근 방법 1 매 query 작업마다 배열을 갱신한다. 한 작업마다 O(N)의 시간이 소요된다. 시간이 오래 걸리고 코드가 복잡해진다. 접근 방법 2 단순하게 매 작업마다 시작점 포인터(start)와 끝점 포인터(end)를 갱신 한다. 한 작업마다 O(1)의 시간 이 소요된다. 시간 소요가 적고 코드도 간단하다. 이후 포인터를 이용해 필..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 "하노이의 탑"은 규칙이 존재하는 대표적인 재귀 문제다. 점화식을 세워서 설계하면 쉽게 구현할 수 있다. (출발지, 경유지, 도착지) 3개의 위치를 선언한다. "N개, 출발지 -> 도착지"의 경우 "N-1개, 출발지 -> 경유지" + "1개, 출발지 -> 도착지" + "N-1개, 경유지 -> 도착지"의 규칙을 가진다. 이를 점화식으로 표현하고 코드로 구현한다. 풀이 이동 정보를 저..
문제 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 접근 방법 무작정 구현을 시작했는데 해결하지 못했다. 이후 검색을 해보며 힌트를 얻었다. 비트마스킹을 이용한 풀이방법밖에 찾지 못했다. 나는 비트마스킹을 잘 모르기에 비트마스킹을 사용하지 않고 그냥 빡세게 구현했다. 원리는 이렇다. 같은 스위치를 여러 번 누르지 않는다. 같은 행위를 반복하면 최적의 해를 구할 수 없다. 완전 탐색으로 100개의 전구를 켜고 끄는 경우를 찾으면 O(..
문제 https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 접근 방법 비슷한 유형의 문제를 풀었던 기억이 있다. 처음에는 무지성으로 구현을 시도했고 실패했다. 이후 나름의 규칙으로 구현을 시도했으나 실패했다. 마지막으로, 이전에 정규식을 이용했던 것이 생각나 적용했더니 너무 간단하게 풀렸다. 풀이 문자열.matches() 내장 함수를 사용한다. matches의 인자로 정규식을 넣는다. "(100+1+|01)+"를 사용했다. A+ "반복"을 표현하며 ..
문제 160585번 : 혼자서 하는 틱택토 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 현재까지 진행한 게임의 결과가 주어지고, 규칙을 위반한 적이 있는지 판단하는 문제다. 간단한 구현 문제다. 규칙을 위반하지 않고 나올 수 없는 경우를 체크해주면 된다. 풀이 O 의 개수와 X 의 개수를 센다. - countChar() replace 함수를 사용하여 문자열의 길이 변화를 계산한다. 기존 문자열 길이와 replace한 문자열 길이의 차이만큼 O 또는 X가 존재한다. 4가지 경우의 규칙 위반을 검사한다. X 가 O 보다 많을 경우 O가 선공이므로..
문제 1802번: 종이 접기 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 접근 방법 분할 정복 문제 모음집을 따라 풀던 중 만난 문제다. 인덱스를 잘 구분하면 쉬운 문제다. 중간 값은 어느 방향으로 접어도 상관이 없다. 문자열의 길이 = 1 일 경우도 마찬가지 중간값을 기준으로 대칭되는 좌, 우의 값이 달라야 한다. 접었을 때 포개지는 곳은 다음 차례에 각각 서로 다른 방향으로 접히게 된다. 재귀 함수를 이용한다. 풀이 규칙을 만족하는지 판단하는 boolean 함수 check 선언 인자 : 문자열의 시..
문제 https://www.acmicpc.net/problem/2412 접근 방법 이분 탐색 문제집을 따라 풀던 중 만난 문제다. '알고리즘 분류' 란에 이분 탐색과 너비 우선 탐색이 있어 두 가지의 풀이가 존재한다고 생각했다. 그러나, 이분 탐색 방식으로 해결하지 못했다. 너비 우선 탐색을 사용하되, 다음 방문 노드를 찾을 때 이분 탐색을 이용하는 문제로 이해했다. (이 풀이는 이분탐색을 제대로 이용하지 못했다) 풀이 (0,0) 을 포함한 n + 1개 홈의 좌표를 저장할 Node[] graph 초기화 n + 1개의 홈에 대한 방문 횟수를 저장할 int[] visited 초기화 graph 배열을 정렬한다 (y를 기준으로 오름차순, 이후 동일한 y에 대해 x를 기준으로 오름차순) BFS 알고리즘 적용 (기..
