막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 백준 토마토 2단계(?)를 풀어봤습니다. ㅎㅎ youngest-programming.tistory.com/197 [알고리즘] 백준 7576 토마토 -bfs, dfs- https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2..

https://programmers.co.kr/learn/courses/30/lessons/43164#qna 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 프로그래머스 LEVEL3의 여행경로 문제를 풀어봤습니다.ㅎㅎ 이전 문제와 마찬가지로 탐색문제인데요. 이전 문제가 BFS 여서 그랬는지 BFS로도 풀 수 있겠다 싶어 처음에 BFS 로 접근했습니다. 솔직히 풀면서 너무 더러워져서 DFS 가 낫겟다 싶었는데 이왕 시작한거 끝을 볼려고 계속 풀었습니다...;; 코드는 다음과 같았는데요. 하지만 주어진 테스트케이스는 다 맞는데 제출시 ..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 프로그래머스 LEVEL3 단어 변환 문제를 풀어봤습니다. bfs 를 사용해서 풀이했습니다. 한 단어는 한 글자만 변경이 가능한 경우 변경할 수 변환할 수 있습니다. (탐색 조건) 1. 큐에 시작 단어를 넣습니다. 2. 단어들을(words) 불러오고 이미 사용한 단어가 아닌 경우 현재 단어와 한글자씩 비교하고 변환이 가능..

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20-bfs%2Cdfs- https://programmers.co.kr/learn/courses/30/lessons/43162?language=kotlin 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr BFS 를 사용하여 처음 연결된 ..

https://programmers.co.kr/learn/courses/30/lessons/49994?language=java 코딩테스트 연습 - 방문 길이 programmers.co.kr 프로그래머스 LEVEL3 의 방문 길이 문제를 풀어봤습니다 ㅎㅎ 처음에 별생각없이 좌표를 칸으로 취급하고 바로 2차원 배열의 map, isVIsisted 하고 bfs queue 로 접근해서 풀었는데 한문제만 맞고 나머지 한문제는 틀리고 오답이 나왔었습니다. 바로 위와 같이 7번처럼 방문이 안되야하는데 된걸로 되서 잘못풀었단거를 꺠달았습니다. 그래서 어디서 어디로 왔는지 알아야했습니다. 이를 4차원 배열을 이용해서 풀었습니다. 1,2 차원 지점에서 3,4차원지점으로 이동했다는 것을 기록합니다. 문제 풀이방법이 더 간단해..

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 프로그래머스 LEVEL2 의 타겟넘버를 풀어봤습니다. ㅎㅎ + 일떄와 - 일때 두가지 경우로 재귀를 돌려 결과값이 타겟넘버라면 개수를 1 증가시키게 풀었습니다. 문제풀이는 다음과 같습니다. [Java] class Solution { private static int target; pr..

https://programmers.co.kr/learn/courses/30/lessons/12952?language=kotlin 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 프로그래멋 LEVEL3 의 백트래킹 유형의 N-Queen 문제를 풀어봤습니다. 예전에 백준에서도 풀었었는데 아마 백트랙킹의 대표적인 문제라 프로그래머스에도 있는 것 같습니다. 복습할겸 다시한번 풀어봤습니다 ㅎㅎ 풀이는 다음과 같습니다. [Java] class Solution { public static int N; pu..

https://programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 프렌즈4 블록 문제를 풀어봤습니다. ㅎㅎ 처음에 기존의 단순 BFS 문제처럼 bfs 함수를 만들고 큐와 while 반복문을 통해 풀려고 했는데 풀다가 아닌 것 같아 지우고 다시 풀었네요. 그런데 블록을 재배치하는 함수인 arrange() 에서 queue.offer(j) 를 i로 바꿔써서 이거 못찾아서 시간을 많이 잡아먹었습니다. ㅠㅠ (신기한게 실행 테스트케이스는 맞는데 제출하기 테스트케이스가 3..

https://programmers.co.kr/learn/courses/30/lessons/1829?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 문제를 보고 BFS를 사용해서 큐로 풀어야겠다고 생각했고 테스트 통과도 잘 통과되었습니다. 하지만 제출을 하니 계속 실패가 뜨더라고요. 그래서 다른 케이스도 해봤으나 다 맞길래 질문하기에 들어가보니 이 문제는 테스트 실행이 아닌 제출하기에서는 전역변수를 전역변수에서 바로 초기화 해놓으면 안되고 solution 함수 내에서 초기화를 해줘야 한다더라고요. 옛날 문제라 그런가.. 왜....

https://programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 지인의 추천으로 풀어봤습니다. 완전탐색 옛날 알고리즘 시간에 배운거 같긴한데 따로 푸는건 처음이네요. 근데 완전탐색으로 푼건지는 잘 모르겠네요 ..ㅠ 처음에 레드카펫이 직사각형이나 정사각형 모양뿐만 아니라 기역자모양이라든가 니은자 모양 등도 되는줄 알고 그렇게 풀었다가 다시 문제보고 잘못푼걸 알았네요 ㅎㅎ 문제에 다써있는데 실수하는 습관을 줄여야할 것 같습니다. ㅠ 처음 메모장으로 다음과 같이 작성했더니 규칙..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [2020-04-02] 원래 row을 행 col을 열로 알고 있었는데 갑자기 햇갈려서 구글검색해서 풀었을 당시 밑처럼 나와서 row가 열이였다는 충격을 받고 row를 열이라 표현하고 풀었었네요... 밑은 잘못된거고 row는 행 col이 열 맞습니다. ㅎㅎㅎ 문제풀이에서 row col이 의미가 바뀌게 풀었으니 유의바랍니다. [2020-05-08] col, row 바껴있던거 코드 수정했습니다! 백트랙킹의 대표적인 예..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M 시리즈의 마지막 문제를 풀었습니다. (2) ~ (4)를 순식간에 푼 것 같습니다. 조금 익숙해져서 그런 것 같습니다. (1) 할 때는 도저히 안풀려서 답을 봤었거든요. 보통 하루에 알고리즘 한문제만 풀려했는데 허허 (3)과 비슷합니다. 대신 자신보다 작은 숫자는 다음에 오면 안됩니다. N과 M 문제 시리즈는 dfs를 사용하는 것 은 똑같지만 크게 3가지로 나뉘는 것 같습니다. ..

https://www.acmicpc.net/problem/1565115651번: N과 M (3)한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해www.acmicpc.net 백트랙킹 문제를 이어서 풀어봤습니다.이번에는 각 자리수에 중복된 숫자가 와도 되는 오름차순 출력 조건입니다.current로 재귀를 돌려야하고 isVisited 방문했는지 안했는지는 이번에는 필요없던게 포인트였습니다. 그리고 처음에 풀어서 제출했는데 시간초과가 났습니다.그래서 출력부분을 StringBuilder로 바꿔서 해결했습니다. (Writer 까지는 필요없는것 같습니다.) import java.u..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 저번에 N과 M (1) 백트랙킹에 이어서 그 다음단계의 백트랙킹 문제를 풀어보았습니다. 저번 문제와 차이점은 오름차순으로 안된 수는 출력하면 안되는 조건이 붙었습니다. (저번 문제는 모든 경우의 수를 오름차순으로 출력시키는 문제였습니다.) 함수에 이전 값을 전달해서 현재숫자와 비교를 하는 로직을 추가했습니다 저번 문제를 이해하고 푸니 이번에는 쉽게 풀린 것 같습니다. import jav..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트랙킹 문제를 처음 풀어봤습니다. 풀다가 도저히 안풀려서 백트랙킹 개념과 다른 사람의 풀이를 보았습니다. 백트랙킹 첫번째 문제인데도 저한테는 어렵네요 ㅜㅜ 백트랙킹 문제는 dfs 또는 bfs 를 사용할 수 있으며 개념은 다음을 보면 됩니다. 전 dfs를 재귀를 사용하는게 편한 것 같습니다. https://idea-sketch.tistory.com/29 [알고리즘] 되추적(Backtracking..