3019번: 테트리스 테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다. 블록을 떨어뜨리기 전에 www.acmicpc.net 풀이 문제 그대로 정직하게 구현하면 되는 문제! 블록 모양을 어떻게 판단할지가 가장 큰 고민이었다. 배열? 리스트? 그림 그려서 수동으로 해보니 바닥면 높낮이를 체크하면 됨을 알 수 있었다. 각 테트리스 블록별로 회전했을때 나올 수 있는 가능한 모양을 모두 저장할 수 있는 ArrayList 을 만들고, 처음 입력받은 모양 번호로 초기화되게 했다. (getBlockShape()) 블록 모양에 따라 올라와야 하는 바닥면의 높이를 저장했다. 그리고 바닥면에 대해 블록을 끝..
1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 풀이 이해가 안됐는데 이 블로그를 참고하여 겨우 이해할 수 있었다... 벨만-포드를 이렇게도 풀 수 있구나 했던 문제 특이하게 negative cycle이 아닌 positive cycle을 찾는 문제이다. 일반적인 벨만-포드는 N-1까지 최단 경로를 갱신한 후 마지막으로 한번 더 돌아다니면서 사이클 여부를 판정한다. 하지만 이 문제에선 사이클이 있는지 검사 뿐만 아니라 시작 지점부터 도착 지점까지의 경로가 있는지도 알아야 한다. 따라서 충분한 edge rela..
16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 혼자 일부러 더럽고 어렵게 푼 느낌? 🙄 암튼 오래걸림 문제에 나온 그대로 시뮬레이션 문제 풀듯 풀었다. 짜잘짜잘한 조건들이 많아서 테케 넣어보고 수정하고 하다보니 푸는데 오래걸렸다.. 고민거리와 삽질의 흔적들 두 동전은 어떻게 동시에 움직이지? 일차원 배열을 생성해서 반복문으로 변수 값을 할당했다. 0
9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 처음에 사이클 체크를 어떻게 해야 하는지 엄청 고민했다... 결국 구글링하여 솔루션들을 참고했다 ㅠ 내가 시도하려는 풀이에선 방문체크 배열이 두 개가 필요함을 알 수 있었다. 방문 체크를 할 배열, 완전히 방문이 끝났음을 알리는 배열 두 개의 visited를 확인할 배열이 필요 visited[n] = false: 아직 방문안한 곳이므로 DFS 다음 탐색 node는 n visited[n] = true & finished[n] = false 방문은 했으나 완전히 방..
1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 벨만-포드 알고리즘을 몰라서 구글링하며 풀이ㅠ 알고리즘 이해에 참고한 글 👍🏻👍🏻👍🏻 코드 작성에 참고한 글 벨만포드 알고리즘이란? 최단 경로를 찾는 알고리즘 중 하나 가중치가 음수일 경우 다익스트라 알고리즘을 사용하면 무한 루프에 빠지게 된다. 따라서 음수 가중치를 다룰 수 있는 벨만-포드 알고리즘을 사용해야 한다. 간단한 원리는 다음과 같다. 노드 수를 V라 하면 시작점에 대해 최대 연결된 간선 개수는 V-1개이다. 시작점을 기준으로 V-1..
완주하지 못한 선수 (level 1) 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 참가자 명단과 완주자 명단이 주어지는데 참가자 중 완주하지 못한 딱 한 명을 찾아내는 문제이다. 처음에 단순히 매칭만 하면 될 줄 알았으나 (당연히) 이중 for문으로 인해 시간초과가 났다 ㅎㅎ... 결국 풀이를 찾아보게 되었는데 단순히 정렬 후 인덱스를 하나씩 비교해가면서 다른 이름이 있다면 바로 그 값을 return하는 문제였다. 연습 겸 JavaScript로 풀었다. 풀면서 느낀 점은 JavaScri..
BFS지만 동시성을 생각해야 하는 문제 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 물과 고슴도치 각각 방문체크를 할 큐를 두고 물 → 고슴도치순으로 BFS탐색을 했다. Logic 데이터를 입력 받을때 고슴도치의 시작 위치를 hedgehog큐에 넣고 해당 map의 위치는 S에서 .으로 마킹한다. 물의 위치를 입력받을 경우 water 큐에 넣고 visited = true로 놓는다. BFS 탐색을 시작한다. while문은 더이상 고슴도치 무빙이 불가능할 때 까지 반복된다. 물부터 영역을 넓힌다. 큐 크기가 유동적이기..
문제에 나와있는 대로 구현하면 풀리는 정직한 시뮬레이션 문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 처음에 문제가 애매하다는 생각이 들었다. 이차원배열을 map이라 하면 map에 따로 떨어진 두 집단이 있을경우 이걸 각각 인구 이동횟수로 세야하는지 아니면 한 round당 횟수로 해야하는지 몰랐다. 그래서 질문게시판을 참고하니 후자인 한 round당으로 세는게 맞았다. 즉, map에서 인구 이동이 가능한 집단이 여러 개가 있어도 한 번으로 치는 것이다. 우선 BFS를 해야하므로 방문체..
- Total
- Today
- Yesterday
- 정규식
- 백트래킹
- matches
- regex
- 프로그래머스
- 알고리즘
- 그래프
- 다익스트라
- 해시
- REACT
- 이분탐색
- dfs
- BFS
- 시뮬레이션
- 문자열
- 삼성역테기출
- swea
- 우선순위큐
- vue.js
- form
- BigInteger
- dp
- 브루트포스
- Validation
- web
- java
- 백준
- 벨만포드
- 구현
- CustomHook
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |