본문 바로가기

알고리즘/구현8

[백준 16988] Baaaaaaaaaduk2 (Easy) / 자바 / 구현 + bfs #문제         레벨: G3알고리즘; bfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/16988#문제 풀이         문제를 보는 순간 규칙이 없고 완전탐색(브루트 포스)로 해결해야겠다고 생각이 들었다. 시간복잡도를 구해보자면 2개의 바둑돌을 놓는 경우의 수(400 C 2) X 상대 바둑돌을 잡아먹는 수 구하기(400) = 400 x 399 % 2 X 400 = 대략삼천 이백만 정도 되므로 가능한 경우의 수이다. 이제 구현할 차례이다. dfs를 돌며 바둑 돌을 놓는 구현은 0인 자리에만 놓고 dfs 재귀 깊이가 2인 함수를 구현하면 된다. 여기서 막혔다. 어떻게 함수를 구현해야 겹치치 않고 400 C 2를 구현할 수 있을까? 정답은 이중 for문을 돌며 .. 2024. 8. 18.
[백준 14890] 경사로 / 자바 / 구현 #문제         레벨: G3알고리즘: 구현풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14890 #문제 풀이        문제를 보면 알겠지만 우리가 해야할 일은 명확하다. 모든 행을 검사하고 모든 열을 검사하면 된다. 그러나 조건이 많이 붙어있어 구현하는데 까다로울 수 있다. 해야 할 일이 명확하고 구현이 까다로운 경우는 밀고나가야한다. 이것은 구현문제이기 때문이다. dfs 혹은 bfs 혹은 dp 문제 같은 경우 해야 할 일이 명확하지는 않은데 구현이 지엽적인 것 같다고 느낄 때는 아이디어를 돌아볼 필요성이 있다.#풀이 코드      import java.util.*;import java.io.*;public class Main { static i.. 2024. 8. 6.
[백준 2504] 괄호의 값 / 자바 / 구현(괄호) #문제         레벨: G5알고리즘: 구현(괄호)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2504#문제 풀이         괄호문제가 보면 스택문제임을 깨달아야 한다. 근데 평상시 만났던 괄호가 올바른지 검사하는 문제가 아니라 괄호의 값을 계산하는 문제이다. 바로 문제 설명하겠다.( ()  () )    가장 안쪽에 있느 ()는 원래 2이다. 그런데 우린 () 앞에 (가 있었으므로 4라고 칠 거다.  그 옆에 있는 ()도 4라고 치자. 그럼 답이 8이 나오지 않은가?이게 어떻게 이렇게 될 수 있을까? 분배법칙 때문에 그렇다. ( ()  () )  는 (()) (()) 와 같다. 즉,  2x(2+2)  이나 (2x2 + 2x2)는 같다. 그러니 우리.. 2024. 8. 2.
[백준 17144] 미세먼지 안녕! / 자바 / 구현 #문제         레벨: G4알고리즘: 구현풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/17144#문제 풀이        제목이 상쾌하여 문제에 대한 호감도가 올라갔다. 풀면서 구현 문제에 적합한 것 같아 호감도가 더 올라갔다.이문제에서 우리가 구현할 것은1. 미세먼지 확산2. 공기청정기 바람 부는 것 3 . 토탈 먼지  수 구하기이 두가지이다. 1 ~ 2번을 T초 동안 반복 후 최종적으로 3번을 통해 답을 구하면 된다.  미세먼지 확산은 기존배열을 참조하여 temp(임시)배열에 값을 추가하거나 빼주면 된다................(1)기존 배열을 수정하면 다른 미세먼지 확산을 계산할 때 영향을 미치기 때문에 일단은 temp배열에 다 계산해주고 기존 배.. 2024. 8. 2.
[백준 20058] 마법사 상어와 파이어스톰 / 자바 / 구현 + bfs 조금 *** #문제         레벨: G3알고리즘: 구현 + bfs 조금풀이시간: 2시간힌트 참조 유무: 유 https://www.acmicpc.net/problem/20058#문제 풀이        이 문제는 bfs문제로 분류되어있지만, 사실상 구현문제라 생각한다. 이 문제에 핵심은 격자회전시키는 식을 잘 세울 수 있는지이다. 그 방법을 바로 말하겠다. 오른쪽으로 90도 회전한다고 하면 map[i][j]가 map [j][n-1-i]가 된다. 즉, i와 j를 바꿔주고 열은 n-1에다가 바꾼 i를 빼준다. (왼쪽으로 90도 회전한다고 하면 거꾸로 돼서 map[i][j]가 map[n-1-j][i]가 된다.) 우리는 덩어리 째 회전을 시켜야 하므로 이중 for문에서 i+=L 씩 증가시켜줘야 한다. 위 방식을 이해하고 .. 2024. 7. 29.
[백준 13458] 시험감독 / 자바 /그리드 문제         레벨: B2알고리즘: 구현 풀이시간: 10분힌트 참조 유무: 무https://www.acmicpc.net/problem/134581 번째 시도   삼성SW역량테스트인데도 말도 안되게 쉬워 푸는 내내 경계했다. 그러나 쉬운 문제가 맞았다. 단 주의해야 하는 건 입력값이다. 입력값의 최대값을 생각해보자.B =1, C= 1, 시험장의 개수 1,000,000 x 응시자수 1,000,000  = 1,000,000,000,000 1조이기 때문에 ans를 int형으로 쓰면 틀린다.import java.io.BufferedReader;import java.io.InputStreamReader;class Main { public static void main(String[] args) throw.. 2024. 7. 3.
[백준 3190] 뱀 / 자바 / 구현 문제         레벨: G5알고리즘: 구현 + 큐 풀이시간: 1:30힌트 참조 유무: 무https://www.acmicpc.net/problem/31901 번째 시도: 성공   [예제 그림]초에 해당하는 뱀의 머리 위치를 그림으로 그려봤다.x는 사과의 위치다.[알고리즘 설명]이 문제는 구현 문제이다.while 문 안에 있는 조건들을 어떻게 잘 구현했는지, 자료구조를 적절히 잘 사용했는지가 관건이다. 설명은 주석을 참조바란다. 뱀의 몸통을 담기 위해 snake큐명령을 담기 위한 moves큐  문제를 다 풀고 나서 한가지 생각해본 점은 명령을 담기 위한 자료구조를 큐 말고 HashMap을 썼다면 ntdir,ntsec를 안썼어도 됐다는 거다. 변수가 줄어들수록 코드의 유지보수가 쉽다고 생각하기 때문에 다음.. 2024. 7. 3.
항해 21일차 99 TIL (공원산책/프로그래머스) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1 번째 시도 구현 문제여서 아이디어는 설명 안하겠다. isWalk: 갈 수 있는 길인지 확인하는 함수 separate: 방향, 거리를 계산해 {x,y}로 반환하는 함수 import java.util.*; class Solution { public int[] solution(String[] park, String[] routes) { int xLength = park[0].length(); int yLength = park.length; int[] startInd = new int[2]; startInd.. 2024. 4. 18.

티스토리툴바