본문 바로가기

HOME

 (207)
[백준/C++] 9663번 N-Queen 풀이 문제 설명 문제 풀이 처음 시도에는 N이 15밖에 되지 않으므로 브루트포스가 당연한 것은 알고 있었고 2차원 배열로 가로 세로 대각선에 있는 값을 true로 변경하며 dfs(재귀)로 풀어나가려고 했으나 코드를 작성하다보니 가로 세로 대각선의 값을 계속 변경하는 불편함이 있고 굳이 2차원으로 풀어나가는 비효율성을 유지할 필요가 없다고 느끼게 되었다. 이후 바로 가로배열, 세로배열을 생성하였고 대각선 값을 어떻게 변경할까 고민하게 되었다. 과거 수업에서 배운 자료를 참고하였고 / 방향 대각선은 현재 행과 열의 합이 같다는 것과 열과 행 중 하나의 값만 뒤에서부터 값을 세어보면 \ 방향 대각선도 해결되는 것을 알게 되었다. 위 그림과 같이 row와 col의 합이 대각선의 값임을 알 수 있다. 코 드 #incl..
[백준 / Python] 체스판 다시 칠하기 문제 설명 문제 풀이 우선 다른 알고리즘이 떠오르지 않아 무식하게 모든 경우의 수를 풀어내고자 했다. 체스판 사이즈만큼 모든 보드를 돌아보며 실행하면 (8 * 8) * (50 - 8 + 1) * (50 - 8 + 1)번이며 이는 1억번보다 작아 풀어낼 수 있겠다고 생각했다. 검은색으로 시작하는 경우와 흰색으로 시작하는 경우를 한 번에 확인하기 위해 black, white를 선언했고 row가 바뀔 때마다 색이 바뀌는 것을 보고 따로 코드로 작성해주었다. 이후 각 경우에서 색칠해야하는 횟수가 가장 적은 것을 최솟값으로 저장한 후 제출하였다. 코 드 import sys N, M = map(int,sys.stdin.readline().split()) board = [] for i in range(N): list..
[프로그래머스/Python] 행렬 테두리 회전하기 문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다. x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다. 다음은 6 x 6 크기 행렬의 예시입니다. 이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은..
[Git] error:does not have a commit checked out 기존에 연동되어 있던 로컬 repo가 꼬여서 레포를 지우고 같은 이름으로 새로 만들고 있었다. 그런데 아래와 같은 오류가 났었고 해결 방법을 기록해두려고 한다. 이유는 이미 존재하는 .git폴더가 있어 발생하는 문제이다. 윈도우의 경우 아래와 같이 보기 -> 숨긴 항목 표시를 통해 나타나는 .git 파일을 제거해주면되고 맥의 경우 cmd에서 ls-al을 통해 찾아내고 rm -rf로 제거해주었다. (여담: cmd+shift+. 으로 숨긴 폴더 표시가 가능하다.)
[프로그래머스] 숫자의 표현 수학적 풀이 및 증명 문제 해석 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다. 1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요. 제한사항 n은 10,000 이하의 자연수 입니다 문제 풀이 [풀이 1번: 투포인터] 숫자 1만까지를 1부터 N까지 합이 1만일 때, 2부터 N까지 합이 1만일 때... 모든 경우를 찾는 코드를 처음에 생각해냈다.시간이 너무 길어질 것 같아서 꼼수를 생각해..
백준 + 프로그래머스 500솔 자축 및 회고 사실 어디가서 자랑하고 축하할만한 수가 아닌 것을 스스로 너무 잘 알아서 지인들에게 말하지 못하고 혼자 일기처럼 작성해보는 중이다...ㅎㅎ 너무 나약한 피린이지만 한 번 나중에 내가 보면 어떤 기분일까 싶어 작성해보았다. 처음 대학교 2학년 때 코딩테스트를 미리 준비해야한다는 동기의 말에 조금씩 시작했던 PS였는데, 어느덧 500개다. 하다보니 매일 1문제를 풀겠다는 욕심도 생기고 재미도 있어서 흥미가 붙었던 것 같다. 그러다 어느 날 생각하지 않아도 되는 쉬운 문제를 계속해서 풀어나가면서 문제수를 불려나가는 것이 나에게 무슨 도움이 되는가? 라는 의문이 들기 시작했다. (이 때 브론즈~실4 문제를 참 선호했던 것 같다.) 어렵더라도 매일 풀지 못하더라도 주에 2문제는 골드를 풀자는 생각을 하게 되었고 ..
[백준/C++] 9935번 문자열 폭발 풀이 문제 해석 문제 풀이 우선 문자열은 100만 개라 O(N2)으로는 풀 수 없을 것 같았다. 문제에서 문자열을 찾아서 지워내면 되는 것이니 스택이나 정규식 풀이 방법이 먼저 떠올랐다. mirkovC4nizCC44 에서 C4를 추려내는 등의 과정을 고려했더니 문자열을 비교할 때 어디까지 겹치는 문자열을 보유했었는지 저장하도록 하였다. (전에 문자열 알고리즘 중에 이런 게 있었는데 까먹었다.ㅎㅎ) [로직] 문자열과 폭발 문자열을 한 문자씩 비교하며 정답 문자열에 추가한다. 문자가 같다면 폭발 문자열의 인덱스를 하나 증가시킨다. 다르다면 지금 인덱스를 스택에 넣어 저장하고 현재 문자열부터 다시 비교한다. 만약 인덱스가 폭발 문자열의 길이와 같다면 길이만큼 정답 문자열에서 제거한다. 만약 이전 인덱스 스택이 비었..
[백준/C++] 14003번 가장 긴 증가하는 부분 수열 5 풀이 문제 해석 문제 풀이 우선 수열의 크기가 100만이라서 O(N2) 풀이로는 해결할 수 없다. dp +이분탐색을 이용한 O(NlogN) 풀이 방법이 필요하다. 풀이 방법은 14002번을 풀어보면 알 수 있는데 DP 배열을 1차원으로 사용한다고 생각해보면 될 것 같다. 지금 숫자가 내가 가진 숫자 최대값보다 크다면 배열의 마지막 값으로 추가한다. (코드상 order 배열) 지금 숫자가 최대값보다 작다면 이분탐색을 통해 지금 숫자보다 큰 최소값과 교환해준다. 이 때 1차원 DP의 경우 값을 덮어 씌워가며 계산을 진행하는게 정석인데, 가장 긴 증가하는 부분 수열의 길이를 찾을 때 바뀌어나간 값들의 길이가 최대가 되지 않는 이상 길이 자체에는 영향을 미치지 않는다. 여기까지가 14002번의 문제 풀이다. 그러나 ..

티스토리툴바